**Photo by VERPEX**

The **N-Queens problem** involves placing N queens on an N x N chessboard in such a way that no two queens threaten each other. This means no two queens should share the same row, column, or diagonal.

**Python Program to Solve the N-Queens Problem using Backtracking**

```
def is_safe(board, row, col, n):
# Check this row on the left side
for i in range(col):
if board[row][i] == 1:
return False
# Check the upper diagonal on the left side
for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
if board[i][j] == 1:
return False
# Check the lower diagonal on the left side
for i, j in zip(range(row, n), range(col, -1, -1)):
if board[i][j] == 1:
return False
return True
def solve_n_queens_util(board, col, n, solutions):
# Base case: If all queens are placed, add the solution to the list
if col >= n:
solution = []
for row in board:
solution.append(''.join(['Q' if x == 1 else '.' for x in row]))
solutions.append(solution)
return True
# Try placing this queen in all rows, one by one
res = False
for i in range(n):
if is_safe(board, i, col, n):
# Place this queen on the board
board[i][col] = 1
# Recur to place the rest of the queens
res = solve_n_queens_util(board, col + 1, n, solutions) or res
# If placing the queen doesn't lead to a solution, backtrack
board[i][col] = 0
return res
def solve_n_queens(n):
board = [[0 for _ in range(n)] for _ in range(n)]
solutions = []
solve_n_queens_util(board, 0, n, solutions)
return solutions
# Example usage
if __name__ == "__main__":
n = 4 # Change this value to solve for different sizes of N
solutions = solve_n_queens(n)
if solutions:
print(f"Number of solutions: {len(solutions)}")
for solution in solutions:
for row in solution:
print(row)
print()
else:
print("No solution exists.")
```

**Explanation:**

**is_safe(board, row, col, n)****Function:**- This function checks if placing a queen on the board at position (row, col) is safe.
- It checks the row on the left side, the upper diagonal, and the lower diagonal to ensure no other queens threaten the position.

**solve_n_queens_util(board, col, n, solutions)****Function:**- This is the core backtracking function that tries to place queens one column at a time.
- If a safe spot is found, it places the queen and recursively calls itself to place the next queen.
- If placing a queen leads to an invalid solution, it backtracks by removing the queen and tries the next possible position.
- If a solution is found (all queens placed), the current configuration is saved.

**solve_n_queens(n)****Function:**- This function initializes the board and calls the utility function to start the backtracking process.
- It collects all possible solutions in a list and returns it.

```
Example Output:
For n = 4, the program prints:
Number of solutions: 2
.Q..
...Q
Q...
..Q.
..Q.
Q...
...Q
.Q..
This represents the two valid ways to place 4 queens on a 4x4 chessboard, where each 'Q' denotes a queen, and '.' denotes an empty square.
```

**How Backtracking Works:**

- The program starts placing queens column by column.
- For each column, it tries placing a queen in each row, checking if it’s safe to place.
- If it finds a valid position, it places the queen and moves to the next column.
- If placing a queen in a column doesn’t lead to a solution, it backtracks by removing the queen and tries the next row.

**Time Complexity:**

- The worst-case time complexity for solving the N-Queens problem is approximately O(N!)O(N!)O(N!), where N is the number of queens. This is because there are NNN possibilities in the first row, N−1N-1N−1 in the second, and so on, which leads to N×(N−1)×(N−2)⋯=N!N \times (N-1) \times (N-2) \dots = N!N×(N−1)×(N−2)⋯=N!.

## Leave a Reply