1

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

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

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

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

4

1 回答 1

4

好问题！N-queens 也是一个很好的递归问题 :) 你实际上已经非常接近于得到你想要的，而且你不必过多地修改你的代码。

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

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

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

因此，修改当前方法的一种简单方法是修改基本情况，以便它在跟踪所有解决方案的变量中记录棋盘状态，即获胜状态，而不是返回 True。此外，现在在您的递归情况下，当您进行递归调用时，您不会检查它是否返回 True 或 False，而只是在 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] = '.'

我希望这有帮助！

于 2018-01-25T17:38:58.770 回答