# 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 = [ * 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.