This is a Python program to solve the n-queen problem with 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. In addition, getter methods to get the size of the board and the number of queens on the board are also provided.
5. Define the function print_all_solutions_to_n_queen that takes the size of the board as argument.
6. Create a QueenChessBoard object of that size and call print_all_solutions_helper on the board to print all solutions.
7. The return value of the above call is the number of solutions. This is then displayed.
8. Define the function print_all_solutions_helper that takes the board object as argument.
9. The function returns the number of possible board configurations on the board object and also displayed each configuration.
9. The helper function first checks if the board is full. If it is, the board is displayed and 1 is returned.
10. If not, then each column is tried to see if a queen can be placed in the next available row.
11. If a column is found, a queen is placed there, the helper function is called again and then the piece is removed.
12. A count variable sums the number of solutions from each call of the helper function.
13. This count is then returned.
Here is the source code of a Python program to solve the n-queen problem using recursion. 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 get_size(self): return self.size def get_queens_count(self): return len(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 print_all_solutions_to_n_queen(size): """Display a chessboard for each possible configuration of placing n queens on an n x n chessboard where n = size and print the number of such configurations.""" board = QueenChessBoard(size) number_of_solutions = print_all_solutions_helper(board) print('Number of solutions:', number_of_solutions) def print_all_solutions_helper(board): """Display a chessboard for each possible configuration of filling the given board with queens and return the number of such configurations.""" size = board.get_size() # if board is full, display solution if size == board.get_queens_count(): board.display() print() return 1 number_of_solutions = 0 # place queen in next row for column in range(size): if board.is_this_column_safe_in_next_row(column): board.place_in_next_row(column) number_of_solutions += print_all_solutions_helper(board) board.remove_in_current_row() return number_of_solutions n = int(input('Enter n: ')) print_all_solutions_to_n_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. print_all_solutions_to_n_queens is called on n to display all possible board configurations and the number of solutions.
Case 1: Enter n: 6 . Q . . . . . . . Q . . . . . . . Q Q . . . . . . . Q . . . . . . . Q . . . Q . . . . . . . . Q . Q . . . . . . . . Q . Q . . . . . . . . Q . . . . . Q . . Q . . . . . . . . . Q . . Q . . . . . . . . . Q . . Q . . . . . . . Q . . . Q . . . Q . . . . . . . . . . Q . . . Q . . . Q . . . . Number of solutions: 4 Case 2: Enter n: 3 Number of solutions: 0 Case 3: Enter n: 4 . Q . . . . . Q Q . . . . . Q . . . Q . Q . . . . . . Q . Q . . Number of solutions: 2
Sanfoundry Global Education & Learning Series – Python Programs.
To practice all Python programs, here is complete set of 150+ Python Problems and Solutions.