我正在通过迭代(无递归)解决 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
您得到重复的原因是您还将皇后放置在放置第一个皇后的位置“之前”。因此,您的第一个皇后将在每个方格上获得其位置,但其他皇后可以在先前迭代中第一个皇后已经放置的方格上占据其位置。这意味着两个皇后被“交换”,但本质上是朝着相同的解决方案构建的。
我尝试重写您的解决方案,但后来决定也更改以下方面:
(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
。这是代码:
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()
您的算法遗漏了几种情况,并且纠正重复项的方法非常复杂。相反,我建议您模拟递归。
从一个简单的递归函数开始:
def is_safe(board, x, y, c):
for p in [board[i] for i in range(0, c)]:
if p[0] == x or p[1] == y or x + y == p[0] + p[1] or x - y == p[0] - p[1]:
return False
return True
def nqueen_rec(board, n, c):
if c == n:
print(board)
else:
for x in range(0, n):
if is_safe(board, x, c, c):
board[c] = (x, c)
nqueen_rec(board, n, c + 1)
深入递归时唯一发生变化的参数是
c
,因此我们可以轻松地将行为更改为递归的行为:
def nqueen_nrec(n):
c = 0
step = [0 for x in range(0, n + 1)]
board = [(x, x) for x in range(0, n)]
while c != -1:
if c == n:
print(board)
c -= 1
step[c] += 1
elif step[c] == n:
c -= 1
step[c] += 1
elif is_safe(board, step[c], c, c):
board[c] = (step[c], c)
c += 1
step[c] = 0
else:
step[c] += 1
该算法跟踪当前的部分解决方案和下一个可能的解决方案,并通过开始新的
while
循环运行而不是递归函数调用来模拟递归深度。