如何阻止我的棋盘回溯？

Question

我正在尝试找到一种方法将 4 个皇后放在 4x4 网格上，这样它们就不会互相攻击，我调用解决棋盘，它找到了解决方案，但不会停止回溯，最终我得到了 4x4 网格满是 0。我知道我需要发表一个声明，以便返回已解决的棋盘并结束回溯。 我知道板子可以解决。

我尝试添加一个 if 语句，当网格的总计数为 4 时，它会停止回溯。通过这个声明，我注意到它结束了董事会有 4 个 1 的第一个实例

这就是我现在拥有的：

def valid(board,x,y,n): 
    #Checks row
    if n in board[x]:
        return False
    #Checks columns
    for i in range(4):
       if(board[i][y] == n):
           return False
    #Checks diagonals from left to right
    for j in range(4):
        if board[j][j] == n:
            return False
    #Checks diagonal right to left
    while x >= 0 and y <= 3:
        if board[x][y] == n:
            return False
        x -= 1
        y += 1
    return True

def queen(board,n):
    for x in range(4):
        for y in range(4):
            if board[x][y] == 0:
                    if (valid(board,x,y,n)):
                        board[x][y] = n
                        result = queen(board,n)
                        print(np.matrix(result))
                        #time.sleep(2)
                        if():
                            return result                       
                        board[x][y] = 0
    return board

copy_board = queen(Board_four,1)
print(np.matrix(copy_board))

Answer 1

有几个问题：

• if ():

  计算的表达式（元组）永远不为真，因此嵌套的

  return

  永远不会执行。
• 相关：

  queen

  可以返回的唯一方法是使用最终的

  return

  语句，当所有移动都被收回时，因此

  queen

  的顶层调用将返回全零的棋盘。
• 成功后，递归应立即退出，而不收回移动。

  if

  应基于递归调用返回的内容。我建议

  queen

  返回一个布尔值而不是董事会，因为你已经拥有了董事会。

• queen

  不保证每一行都会收到一个皇后。如果一行上没有有效的单元格，它不会回溯，而是愉快地继续尝试将皇后放置在下一行。这是错误的。解决此问题的更好方法是不迭代行，而是使用递归通过更深层次的递归将皇后放置在下一行和后续行上。

• valid

  无法正确验证对角线。

  board[j][j]

  查看通常与

  x

  、

  y

无关的一条对角线
• 如果您逐行放置皇后，并且每行绝不放置两个皇后，则无需使用

  valid

  检查行。此外，其他检查不必查看尚未访问的行中的单元格。

• valid

  检查

  == n

  ，但

  queen

  假设空用 0 表示，所以实际上

  valid

  不需要知道

  n

  的值（作为参数），但可以用

  != 0

  检查.
• 不要硬编码 4，而是使用

  len(board)

  使代码更通用。

这是改编后的代码：

def valid(board, x, y): 
    # Not needed to check row, as `queen` already ensures rows are OK
    for i in range(x): # Only look in previous rows
        # Checks column
        if board[i][y] != 0:
           return False
        # Check / diagonal
        if y + x - i < len(board) and board[i][y+x-i] != 0:
           return False
        # Check \ diagonal
        if y - x + i >= 0 and board[i][y-x+i] != 0:
           return False
    return True

def queen(board, n, x=0):
    if x >= len(board):
        return True  # all rows done: success
    for y in range(len(board)):
        if board[x][y] == 0 and valid(board, x, y):
            board[x][y] = n
            if queen(board, n, x+1):
                return True  # return boolean
            board[x][y] = 0
    return False  # could not find a good place in this row


size = 4
board = [[0] * size for _ in range(size)]
if queen(board, 1):
    for row in board:
        print(row)
else:
    print("no solution found")

使用

any

，

valid

也可以写成：

def valid(board, x, y): 
    return not any(
        board[i][y] or 
            y + x - i < len(board) and board[i][y+x-i] or
            y - x + i >= 0 and board[i][y-x+i]
        for i in range(x)
   )