""" queens.py eight queens problem (See https://en.wikipedia.org/wiki/Eight_queens_puzzle) The approach here is to put one queen per column, and do a recursive depth-first search left-to-right looking for a row that works for each successive queen. The search stops once a successful position is found. Rather than try rows in the order (0,1,2,3,...), I use random.shuffle to mix them up, which means that the program will find different solutions when run repeatedly. The board coordinates are the (row, column) indices used for matrices, which look like this for n=4 case : +-----------+ | | | | | 0 |--+--+--+--| | | | | | 1 |--+--+--+-- | | | | | 2 |--+--+--+--| | | | | | 3 = row +-----------+ 0 1 2 3 = columns The guts of the algorithm is the search() method; the rest is mostly setting up the problem. I've tested n=4 up to n=40 or so; none of the searches took more than a second or two on my mac laptop. The value for n may be given on the command line; otherwise, the standard n=8 is used. Here are a few examples of what it looks like when it runs. $ python queens.py A solution to the n queens problem for n = 8. . . . . Q . . . . . Q . . . . . Q . . . . . . . . . . . . . Q . . Q . . . . . . . . . . . . . Q . . . . . Q . . . . . Q . . . . $ python queens.py 10 A solution to the n queens problem for n = 10. . . . . . . Q . . . Q . . . . . . . . . . . Q . . . . . . . . . . . . Q . . . . . . . . . . . Q . . . . . . . . . . . Q . . . . Q . . . . . . . . . . . . . Q . . Q . . . . . . . . . . . Q . . . . . . $ python queens.py 33 A solution to the n queens problem for n = 33. . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . Jim Mahoney | cs.bennington.college | MIT License | May 3 2021 """ import random import sys def is_diagonal(row1, col1, row2, col2): """ True if those two squares are on the same diagonal """ #print(f" is_diagonal({row1}, {col1}, {row2}, {col2}") return abs(row1 - row2) == abs(col1 - col2) # test is_diagonal() # (0,0) (0,1) (0,2) (row, column) # (1,0) (1,1) (1,2) so (1,0), (0,1) are on a digonal # (2,0) (2,1) (2,2) (1,0), (0,2) are not on a diagonal assert is_diagonal( 1,0, 0,1 ), "is_diagonal True works" assert not is_diagonal( 1,0, 0,2 ), "is_diagonal False works " def get_n(): """ Get the value for n from the command line, or just use 8""" # If the user runs this as "python queens.py 10", # then sys.argv will be ['queens.py', '10']. # And if so, set n to 10. if len(sys.argv) > 1: n = int(sys.argv[1]) else: n = 8 return n # Want lots of printing? debug = False class Board: """ n x n chess board for N queens problem""" def __init__(self, n=8): self.n = n self.solved = False # queens[col] is 0 to n-1, giving queen's row in that column. self.queens = [None for column in range(self.n)] def symbol(self, row, column): """ Return 'Q' if there's a queen at (row,column), else '.' """ return 'Q' if self.queens[column] == row else '.' def __str__(self): """ n-line string containing current queen positions """ result = '' for row in range(self.n): for col in range(self.n): result += self.symbol(row, col) + ' ' result += '\n' return result def is_ok(self, row, col): """ True if a queen at (row,col) cannot see those to its left. """ for col2 in range(col): row2 = self.queens[col2] if debug: print(f" is_ok(row={row},col={col}); col2={col2}, row2={row2}") print(f" queens = {self.queens}") # This (row,col) is not OK if it conflicts # with a previous queen in the same row or the same diagonal. if row2 == row or is_diagonal(row, col, row2, col2): return False # No conflicts found with previous queens, so this (row,col) is OK. return True def search(self, col): """ recursive depth-first search by columns, looking for a row to put the queen that does not conflict with earlier columns. This returns nothing, but when it is finished, the board should be in a solved state. """ if debug: print(f" ** _search col={col} ** ") print(self) if col == self.n: # All rows finished? self.solved = True # Then we're done. else: rows = list(range(self.n)) # Shuffling the rows [0,1,2,3,...] random.shuffle(rows) # makes the search order random. for row in rows: if debug: print(f" trying col={col} row={row}") if self.is_ok(row, col): # Can a queen be put here? self.queens[col] = row # Yes; set the row for this column. self.search(col + 1) # ... and search next column. if self.solved: return # Found one? Then stop. def start_search(self): """ Start the recursive search from row 0. Return the solved state. """ self.search(0) return self # -- some tests of the Board() class -- b4 = Board(4) # Create a 4x4 board. assert b4.queens == [None, None, None, None], "no queens placed yet" assert b4.symbol(0,0) == '.', "(0,0) is empty" b4.queens[0] = 1 # put a queen at leftmost column 0, row 1 assert b4.symbol(0,0) == '.', "(0,0) is empty" assert b4.symbol(1,0) == 'Q', "(1,0) has a queen" assert str(b4) == '. . . . \nQ . . . \n. . . . \n. . . . \n', "board string" # . . . . That test board with one placed queen looks like this : # Q . . . # . . . . # . . . . # ... now check where a queen can go in column 1. assert not b4.is_ok(1,1), "can't put a queen at row=1, col=1" # horizontal hit assert not b4.is_ok(2,1), "can't put a queen at row=2, col=1" # diagonal hit assert b4.is_ok(3,1), "can put a queen at row=3, col=1" # knight's move # -- end tests -- def main(): """ Solve the n x n queens problem """ n = get_n() print(f"A solution to the n queens problem for n = {n}. ") print(Board(n).start_search()) if __name__ == '__main__': main()