姬長信(Redy)

算法-在N个皇后区迭代解决方案中避免重复…


我正在迭代解决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()方法在板上放置女王可能安全的地方.

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