algorithm - 避免 N Queen 迭代解决方案中的重复项(不允许递归)

Question

我正在通过迭代(非递归)解决 N 皇后问题。我现在面临的问题是重复的解决方案。例如 4 x 4 板有 2 个解决方案，我正在打印 4 个解决方案，也就是说我找到了两次相同的解决方案。

让我进入代码以获得更好的概述:

def solution(self):
        queen_on_board = 0
        for row in range(self.N):
            for col in range(self.N):
                self.board[row][col] = 'Q'
                queen_on_board = queen_on_board + 1
                print ("(row,col) : ", row, col)
                squares_list = self.get_posible_safe_squares(row,col)
                for square in squares_list:
                    for x,y in square.items():
                        if self.isTheQueenSafe(x,y):
                            self.board[x][y] = 'Q'
                            queen_on_board = queen_on_board + 1
                print ("Queen on board", queen_on_board)
                if queen_on_board == 4:
                    self.print_the_board()
                self.reset_the_board()
                queen_on_board = 0

如您所见，我遍历了每一行和每一列。这个特定的实现给了我 4 个相同的解决方案 2。

(row,col) :  0 1
Queen on board 4
['.', 'Q', '.', '.'] 

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

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

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

(row,col) :  0 2
Queen on board 4
['.', '.', 'Q', '.'] 

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

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

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

(row,col) :  1 0
Queen on board 4
['.', '.', 'Q', '.'] 

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

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

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

(row,col) :  2 0
Queen on board 4
['.', 'Q', '.', '.'] 

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

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

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

我想避免重复。如果有人能指出我正确的方向，那就太好了。

get_posible_safe_squares() 方法在棋盘中寻找皇后可能安全的可能方 block 。

def get_posible_safe_squares(self, row, col):
        ret = []
        for i in range(self.N):
            for j in range(self.N):
                if i != row and j !=col:
                    if i + j != row + col and i - j != row - col:
                        d = { i:j }
                        ret.append(d)
        return ret 

Answer 1

您得到重复项的原因是您还在放置第一个皇后的位置“之前”放置了皇后。因此，您的第一个皇后将在每个方 block 上找到自己的位置，但其他皇后可以在先前迭代中第一个皇后已经放置的方 block 上占据自己的位置。这意味着两个皇后被“交换”，但本质上是朝着相同的解决方案构建的。

我尝试重写您的解决方案，但后来决定也更改以下方面:

• 很遗憾，放置第一个皇后的代码与放置其他皇后的代码不同。应该可以为此重用相同的代码。
• 我不会使用单例字典来表示正方形。元组 (i, j) 似乎比 { i:j } 更自然。
• 当您唯一需要的信息是棋盘大小和 - 当放置皇后时 - 皇后的位置时，存储整个棋盘可能有点矫枉过正。由于同一行不能有两个皇后，因此您可以将其设为列索引列表。所以 queens[2] == 3 意味着第 2 行和第 3 列有一个皇后。有了这个列表后，您也不需要 queens_on_board，因为len(queens) 将返回该值。 print_the_board 可以根据该信息轻松生成点和“Q”。
• 因为您拥有函数 isTheQueenSafe，所以您实际上并不需要 get_posible_safe_squares。在放置第一个皇后之后调用它已经很随意了，但在放置任何其他皇后之后就不会调用它。
• 您混合了两种命名约定:驼峰式和下划线，所以我会选择后者并使用 is_queen_safe。

查看它在 repl.it 上运行

代码如下:

class Board:
    def __init__(self, size):
        self.N = size
        self.queens = [] # list of columns, where the index represents the row

    def is_queen_safe(self, row, col):
        for r, c in enumerate(self.queens):
            if r == row or c == col or abs(row - r) == abs(col - c):
                return False
        return True

    def print_the_board(self):
        print ("solution:")
        for row in range(self.N):
            line = ['.'] * self.N
            if row < len(self.queens):
                line[self.queens[row]] = 'Q'
            print(''.join(line))

    def solution(self):
        self.queens = []
        col = row = 0
        while True:
            while col < self.N and not self.is_queen_safe(row, col):
                col += 1
            if col < self.N:
                self.queens.append(col)
                if row + 1 >= self.N:
                    self.print_the_board()
                    self.queens.pop()
                    col = self.N
                else:
                    row += 1
                    col = 0
            if col >= self.N:
                # not possible to place a queen in this row anymore
                if row == 0:
                    return # all combinations were tried
                col = self.queens.pop() + 1
                row -= 1

q = Board(5)
q.solution()