python - 所有可能的 N 皇后区

Question

经典的 N 皇后问题找到了一种方法，将 n 个皇后放在 n×n 的棋盘上，使得没有两个皇后互相攻击。这是我对 N 皇后区问题的解决方案。

class Solution(object):
    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        grid = [['.' for _ in range(n)] for _ in range(n)]
        solved = self.helper(n, 0, grid)
        if solved:
            return ["".join(item) for item in grid]
        else:
            return None

    def helper(self, n, row, grid):
        if n == row:
            return True
        for col in range(n):
            if self.is_safe(row, col, grid):
                grid[row][col] = 'Q'
                if self.helper(n, row + 1, grid):
                    return True
                else:
                    grid[row][col] = '.'
        return False

    def is_safe(self, row, col, board):
        for i in range(len(board)):
            if board[row][i] == 'Q' or board[i][col] == 'Q':
                return False
        i = 0
        while row - i >= 0 and col - i >= 0:
            if board[row - i][col - i] == 'Q':
                return False
            i += 1
        i = 0
        while row + i < len(board) and col + i < len(board):
            if board[row + i][col - i] == 'Q':
                return False
            i += 1
        i = 1
        while row + i < len(board) and col - i >= 0:
            if board[row + i][col - i] == 'Q':
                return False
            i += 1
        i = 1
        while row - i >= 0 and col + i < len(board):
            if board[row - i][col + i] == 'Q':
                return False
            i += 1
        return True


if __name__ == '__main__':
    solution = Solution()
    print(solution.solveNQueens(8))

此问题的扩展说明，找到所有可能的解决方案并以列表的形式返回它们。我试图通过向辅助方法添加一个列变量来扩展我的解决方案，该变量从 0 开始以跟踪一个完整的解决方案和下一个的开始。因此，基本情况变为

if row == n and col == n:
   return True

但这种方法行不通，因为每次连续的递归调用都会在错误的列中结束。有人可以帮助扩展此解决方案以找到所有可能的解决方案。

Answer 1

好问题! N-queens 也是一个很好的递归问题 :) 你实际上真的很接近你想要的，你不必修改你的代码太多。

思考它的一个好方法是理解您正在研究的两个不同问题。您当前的方法是使用回溯法找到可能的第一个解决方案。您想要做的是找到所有解决方案，类似的问题只需要您以不同的方式思考您的基本情况。

在您当前的设置中，如果您的基本案例返回 True，则父调用将短路并返回 True。这在试图找到任何单一解决方案时是理想的，因为一旦我们找到一个可行的解决方案，我们就知道我们可以停止寻找。但是，因此，我们不会继续探索其他路径。

考虑回溯的一种方法是，您基本上是在创建一棵由可能的移动产生的可能棋盘的树。要找到第一个解决方案，一旦到达叶节点或获胜状态，就一路返回。然而，您想要做的是继续遍历树的所有其他路径并继续寻找叶子获胜状态并沿途记录它们。

因此，修改您当前方法的一种简单方法是修改您的基本案例，以便它不返回 True，而是在跟踪所有解决方案的变量中记录棋盘状态，即获胜状态。此外，现在在您的递归情况下，当您进行递归调用时，您不会检查它是否返回 True 或 False，而是继续在 for 循环中继续前进并尝试所有 Action 。

我像这样修改了你的解决方案，得到了 92 个解决方案，互联网证实这是真的:)

class Solution(object):
    def __init__(self):
        self.solutions = []

    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        grid = [['.' for _ in range(n)] for _ in range(n)]
        solved = self.helper(n, 0, grid)
        print len(self.solutions)
        if solved:
            return ["".join(item) for item in grid]
        else:
            return None

    def helper(self, n, row, grid):
        if n == row:
            print "wooo"
            self.solutions.append(copy.deepcopy(grid))
            return
        for col in range(n):
            if self.is_safe(row, col, grid):
                grid[row][col] = 'Q'
                self.helper(n, row + 1, grid)
                grid[row][col] = '.'

希望对您有所帮助!