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

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

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

这段代码应该打印出所有的解决方案，但它会在最后留下空板。如果您只想打印您能找到的第一个解决方案(并让棋盘上有皇后)，您需要将函数更改为返回一个值，指示是否找到了解决方案。然后递归代码可以传递成功报告，或者如果递归失败则回溯:

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