n Queen backtracking 迭代所有位置

Question

我正在尝试在没有任何第 3 方库的情况下解决 n Queen 问题。所以我只使用普通的 python 数组和循环。这是 nQueen 函数

 def nQueenBackTrack(self, row, n):
        for i in range(n):
            if self.isTheQueenSafe(row , i):
                print(row,i)
                self.board[row][i] = "Q"
                self.print_the_board()
                if row == n:
                    self.print_the_board()
                else:
                    self.nQueenBackTrack(row + 1, n)

非常简单。现在对于我的 isQueenSafe 功能，我检查来自其他皇后的水平和对角线攻击。

def isTheQueenSafe(self, row,col):
        for i in range(self.N):
            # check horizontal Queens
            if self.does_board_has_a_queen_at(row,i) or self.does_board_has_a_queen_at(i, col):
                return False
            # check diagonal Queens
            s = row + col
            k = row - col
            for x in range(self.N):
                for y in range(self.N):
                    if x + y == s and self.board[x][y] == "Q":
                        return False
                    if x - y == k and self.board[x][y] == "Q":
                        return False

这是我遇到问题的功能。我相信我是为了正确检查条件。我将其作为 4 x 4 板的输出得到。

['Q', '.', '.', '.'] 

['.', '.', 'Q', '.'] 

['.', '.', '.', '.'] 

['.', '.', '.', '.']

谁能告诉我正确的方向

Answer 1

当你不能把女王放在任何地方时，你就不是在处理这个案子。

让我们考虑一下：

你调用函数 starting 并将第一个皇后放在 (0,0)
女王被安置是因为你可以
你不在最后一行，因此你进入递归将皇后放在下一行
您尝试将皇后放在第二行的 (0,1)，然后放在 (1,1)，这两者都是不可能的。
然后你尝试把它放在 (2,1) 处，成功了，你就进入了递归的第三层
您现在不能将皇后放在该行的任何位置。
您没有放置皇后就到达了数组的末尾
递归return到第二行
然后您（可能）甚至尝试将另一个皇后放在第二排，但您做不到。到达第二行的末尾，此递归调用也 returns
然后您（可能）甚至尝试将另一个皇后放在第一排，但您还是做不到。到达第一行的末尾，第一次调用 nQueenBackTrack returns.
程序终止，只有两个皇后完全放在输出中可以看到的位置。

我建议您调试调试您的程序 (Python debugging tips) 或者您也可以添加一些额外的打印语句（例如在进入方法调用时和 returning 之前）这样您真能看出是怎么回事。

我假设一些东西：

我假设您在打印时旋转了板，因为...通常 x 是列，y 是行。 x 在水平方向，y 在垂直方向。
我还假设您确实正确地实施了 isTheQueenSafe 方法。你在评论中提到你实际上 return true 在某些时候。
我假设您的 nQueenBackTrack 方法中没有更多代码。

Answer 2

回溯算法需要能够撤销它对游戏状态所做的更改。在您的代码的情况下，它应该在找到有效位置时删除它放置的皇后：

def nQueenBackTrack(self, row, n):
    for i in range(n):
        if self.isTheQueenSafe(row , i):
            self.board[row][i] = "Q"  # this will need to be reversed later
            if row == n:
                self.print_the_board()
            else:
                self.nQueenBackTrack(row + 1, n)
            self.board[row][i] = "."  # backtrack: reset the modified square

此代码应打印出所有解决方案，但最后会使棋盘留空。如果你只想打印你能找到的第一个解决方案（并让棋盘上有皇后），你需要将函数更改为 return 一个指示是否找到解决方案的值。然后递归代码可以传递成功报告，或者如果递归失败则回溯：

def nQueenBackTrack(self, row, n):
    for i in range(n):
        if self.isTheQueenSafe(row , i):
            self.board[row][i] = "Q"
            if row == n:
                self.print_the_board()
                return True               # success!
            result = self.nQueenBackTrack(row + 1, n)
            if result:
                return True               # pass on report of success
            self.board[row][i] = "."      # otherwise, backtrack
    return False                          # if no solution was found, report failure

n Queen backtracking 迭代所有位置

n Queen backtracking for iterating all the position

algorithm

python-3.x

n-queens