I am solving the N queen problem with iteration (no recursion). Problem I am facing right now is duplicate solutions. For example 4 x 4 board has 2 solutions I am printing 4 solutions, so to say I am finding same solution twice.
Let me get into the code for a better overview:
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
so as you can see I am going over every rows and cols. This particular implementation gives me 4 solution 2 being identical.
(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', '.']
I want to avoid getting duplicates. Would be great if someone can point me to the right direction.
The get_posible_safe_squares() method looks for possible squares in the board where the queen might be safe.
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
The reason you get duplicates is that you also place queens "before" the position where you place the first queen. So your first queen will get its position on each square, but other queens can take their position on a square where in an earlier iteration the first queen had already been put. This means two queens were "swapped", but essentially build towards the same solution.
I tried to rewrite your solution, but then decided to also change the following aspects:
(i, j) seems more natural than { i:j }.queens[2] == 3 means that there is a queen on row 2 and column 3. Once you have this list, you don't need queens_on_board either, as len(queens) will return that value. The print_the_board can easily produce the dots and "Q"s based on that information.isTheQueenSafe, you don't really need get_posible_safe_squares. It was already quite arbitrary that you called it after placing the first queen, but not after placing any other queen.is_queen_safe.Here is the code:
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()