Learn Programming and technology with ease @ developerpublish.com

HomePythonPython Program to Solve n-Queen Problem with Recursion

# Python Program to Solve n-Queen Problem with Recursion

This Python program uses a recursive approach to solve the n-Queens problem. It explores all possible combinations of queen placements on the chessboard while ensuring that queens do not attack each other. The N-Queen problem is a classic puzzle that asks you to place N chess queens on an NÃ—N chessboard so that no two queens threaten each other. In other words, no two queens can share the same row, column, or diagonal.

## Problem Statement

Write a Python program to find all possible solutions to the N-Queen problem for a given board size N.

## Python Program to Solve n-Queen Problem with Recursion

```def is_safe(board, row, col, N):
# Check if there is a queen in the same column
for i in range(row):
if board[i][col] == 1:
return False

# Check upper-left diagonal
for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
if board[i][j] == 1:
return False

# Check upper-right diagonal
for i, j in zip(range(row, -1, -1), range(col, N)):
if board[i][j] == 1:
return False

return True

def solve_n_queens(N):
def solve(board, row):
if row == N:
solutions.append(["".join(["Q" if x == 1 else "." for x in row]) for row in board])
return

for col in range(N):
if is_safe(board, row, col, N):
board[row][col] = 1
solve(board, row + 1)
board[row][col] = 0

solutions = []
chessboard = [[0] * N for _ in range(N)]
solve(chessboard, 0)
return solutions

def print_solutions(solutions):
for i, solution in enumerate(solutions):
print(f"Solution {i + 1}:")
for row in solution:
print(row)
print()

if __name__ == "__main__":
N = int(input("Enter the size of the chessboard (N): "))
solutions = solve_n_queens(N)
print_solutions(solutions)
```

## How it Works

1. The `is_safe` function checks whether it is safe to place a queen at a specific position on the chessboard by examining the column and diagonal positions.
2. The `solve_n_queens` function uses recursion to find all possible solutions to the N-Queen problem. It initializes an empty chessboard and starts the solving process with the first row.
3. The `print_solutions` function prints all the solutions found.

## Input/Output

### You May Also Like

#### Python Program to Remove Duplicates from a Linked List

In this Python program, we will create a singly linked list and remove duplicate elements from it. A linked list...

#### Python Program to Solve the Celebrity Problem

This Python program solves the Celebrity Problem by finding a person who is known by everyone but does not know...

#### Python Program to Find Intersection and Union of Two Linked Lists

In this Python program, we will be implementing the intersection and union operations on two linked lists. Linked lists are...