所有可能的N-皇后

Question

经典的no问题找到了一种将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))

这个问题的扩展声明，找到所有可能的解决方案，并以列表的形式返回它们。我试图通过向helper方法中添加一个列变量来扩展我的解决方案，该方法从0开始，以跟踪一个完整的解决方案和下一个解决方案的开始。这样，大小写就变成了

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

但是，这种方法并不有效，因为每个连续的递归调用最终都会出现在错误的列中。有人能帮助扩展此解决方案以找到所有可能的解决方案吗？

Answer 1

问得好！N也是一个很大的递归问题:)您实际上已经接近得到您想要的东西了，并且您不必修改代码太多。

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

在当前的设置中，如果基本大小写返回True，则父调用将短路并返回True。这是理想的，当我们试图找到任何一个单一的解决方案，因为一旦我们找到一个有效的，我们知道我们可以停止寻找。然而，结果是，我们不再继续探索其他的道路。

考虑回溯的一种方法是，您基本上是在创建一棵由可能的移动所产生的可能板组成的树。要找到第一个解决方案，一旦到达叶节点或获胜状态，就会一直返回回原来的位置。然而，您想要做的是继续遍历所有其他路径的树，并继续寻找叶子获奖的状态，并记录他们的过程中。

因此，修改当前方法的一个简单方法是修改您的基本大小写，这样它就可以在跟踪所有解决方案的变量中记录董事会的状态，即获胜状态，而不是返回True。另外，在递归的情况下，当您进行递归调用时，您不会检查它返回的是真还是假，而只是在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] = '.'

我希望这能帮到你!