This is a Python program to solve the n-queen problem without recursion.
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.
1. Create a class QueenChessBoard.
2. The board configuration is stored in a list called columns where if c = columns[r], then a queen is at column c and row r.
3. The class provides methods to place a queen in the next row given the column, remove the queen from the last row where a queen is present, check whether a given column is safe to place a queen in the next free row and to display the board.
4. Define the function solve_queen that takes the size of the board as argument.
5. It creates a QueenChessBoard object with that size.
6. A while loop is created with condition True.
7. In each iteration, it is checked to see in which column a queen can be placed in the first available row of the board. This is done using another loop inside the while loop.
8. If such a column is there, the queen is placed there and the inner loop is stopped.
9. After the inner loop, if a column was not found or the board became full, then we need to backtrack.
10. If the board is full, then before backtracking, we need to display the board.
11. Backtracking is done by removing the queen from the last filled row and making the next iteration try column values above the column values of the queen just removed.
12. If it is found that no more queens can be removed, then we are finished.
13. The number of solutions is kept track of and printed at the end.
Here is the source code of a Python program to solve the n-queen problem using an iterative solution. The program output is shown below.
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), (columns, 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)
1. The user is prompted to enter n where n is the number of queens to place and the size of the board.
2. solve_queens is called on n to display all possible board configurations and the number of solutions.
Case 1: Enter n: 4 . Q . . . . . Q Q . . . . . Q . . . Q . Q . . . . . . Q . Q . . Number of solutions: 2 Case 2: Enter n: 1 Q Number of solutions: 1 Case 3: Enter n: 2 Number of solutions: 0
Sanfoundry Global Education & Learning Series – Python Programs.
To practice all Python programs, here is complete set of 150+ Python Problems and Solutions.