所有可能的 N 皇后区

Question

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

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))

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

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

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

Answer 1

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

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

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

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

因此，修改您当前方法的一个简单方法是修改您的基本案例，而不是 returning True，它记录棋盘的状态，获胜状态，在一个变量中跟踪所有解决方案。此外，现在在您的递归情况下，当您进行递归调用时，您不会检查它 return 是真还是假，而是继续在 for 循环中继续前进并尝试所有动作。

我像这样修改了你的解决方案，得到了 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] = '.'

希望对您有所帮助！

所有可能的 N 皇后区

All possible N-Queens

python

algorithm

backtracking

recursive-backtracking