# Python Program to Solve n-Queen Problem with Recursion

This is a Python program to solve the n-queen problem with recursion.

Problem Description

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.

Problem Solution

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.

Program/Source Code

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], 0), (columns[1], 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)```
Program Explanation

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.

Runtime Test Cases
```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.

Note: Join free Sanfoundry classes at Telegram or Youtube

If you find any mistake above, kindly email to [email protected]