The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other; thus, a solution requires that no two queens share the same row, column, or diagonal. The eight queens puzzle is an example of the more general n queens problem of placing n non-attacking queens on an n×n chessboard, for which solutions exist for all natural numbers n with the exception of n = 2 and n = 3.
Problem Statement:
The n-queen problem is the problem of placing n queens on an n x n chessboard such that no queen can attack another queen.
Solution:
Python Program to Solve n-Queen Problem without Recursion
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 |
class QueenChessBoard: def __init__(self, size): # board has dimensions size x size self.size = size # columns[r] is a number c if a queen is placed at row r and column c. # columns[r] is out of range if no queen is place in row r. # Thus after all queens are placed, they will be at positions # (columns[0], 0), (columns[1], 1), ... (columns[size - 1], size - 1) self.columns = [] def place_in_next_row(self, column): self.columns.append(column) def remove_in_current_row(self): return self.columns.pop() def is_this_column_safe_in_next_row(self, column): # index of next row row = len(self.columns) # check column for queen_column in self.columns: if column == queen_column: return False # check diagonal for queen_row, queen_column in enumerate(self.columns): if queen_column - queen_row == column - row: return False # check other diagonal for queen_row, queen_column in enumerate(self.columns): if ((self.size - queen_column) - queen_row == (self.size - column) - row): return False return True def display(self): for row in range(self.size): for column in range(self.size): if column == self.columns[row]: print('Q', end=' ') else: print('.', end=' ') print() def solve_queen(size): """Display a chessboard for each possible configuration of placing n queens on an n x n chessboard and print the number of such configurations.""" board = QueenChessBoard(size) number_of_solutions = 0 row = 0 column = 0 # iterate over rows of board while True: # place queen in next row while column < size: if board.is_this_column_safe_in_next_row(column): board.place_in_next_row(column) row += 1 column = 0 break else: column += 1 # if could not find column to place in or if board is full if (column == size or row == size): # if board is full, we have a solution if row == size: board.display() print() number_of_solutions += 1 # small optimization: # In a board that already has queens placed in all rows except # the last, we know there can only be at most one position in # the last row where a queen can be placed. In this case, there # is a valid position in the last row. Thus we can backtrack two # times to reach the second last row. board.remove_in_current_row() row -= 1 # now backtrack try: prev_column = board.remove_in_current_row() except IndexError: # all queens removed # thus no more possible configurations break # try previous row again row -= 1 # start checking at column = (1 + value of column in previous row) column = 1 + prev_column print('Number of solutions:', number_of_solutions) n = int(input('Enter n: ')) solve_queen(n) |
If you like FreeWebMentor and you would like to contribute, you can write an article and mail your article to [email protected] Your article will appear on the FreeWebMentor main page and help other developers.
