The N-Queens problem is a classic algorithmic problem that involves placing N queens on an N×N chessboard so that no two queens threaten each other. This means that no two queens can be in the same row, column, or diagonal. Below is a Python implementation to solve this problem using backtracking.

Python Program

def print_solution(board):
    """Print the chessboard configuration."""
    for row in board:
        print(" ".join("Q" if col else "." for col in row))

def is_safe(board, row, col, N):
    """Check if it's safe to place a queen at board[row][col]."""
    # Check the column
    for i in range(row):
        if board[i][col]:
            return False

    # Check the upper diagonal on the left side
    for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
        if j < 0: break if board[i][j]: return False # Check the upper diagonal on the right side for i, j in zip(range(row, -1, -1), range(col, N)): if j >= N: break
        if board[i][j]:
            return False

    return True

def solve_n_queens_util(board, row, N):
    """Utilize backtracking to solve the N-Queens problem."""
    if row >= N:
        print_solution(board)
        print()
        return

    for col in range(N):
        if is_safe(board, row, col, N):
            board[row][col] = True  # Place the queen
            solve_n_queens_util(board, row + 1, N)  # Recur to place the next queen
            board[row][col] = False  # Backtrack

def solve_n_queens(N):
    """Main function to solve the N-Queens problem."""
    board = [[False for _ in range(N)] for _ in range(N)]
    solve_n_queens_util(board, 0, N)

# Example usage
N = 4
solve_n_queens(N)

Program Structure

The program consists of several functions that work together to solve the N-Queens problem:

• print_solution(board): This function takes the chessboard as input and prints its current configuration, displaying queens as ‘Q’ and empty squares as ‘.’.
• is_safe(board, row, col, N): This function checks if placing a queen at a given position (row, col) is safe. It checks the column, and both upper diagonals for any threats from other queens.
• solve_n_queens_util(board, row, N): This function uses backtracking to place queens row by row. If a solution is found, it prints the board configuration.
• solve_n_queens(N): This is the main function that initializes the board and starts the backtracking process. It creates an N×N board filled with False values, representing empty squares.

Documentation

Here’s a breakdown of how the N-Queens solver works:

1. The solve_n_queens function initializes the board and starts the recursive backtracking process.
2. The solve_n_queens_util function attempts to place queens on the board. For each row, it checks each column to see if placing a queen is safe using the is_safe function.
3. If a queen is placed successfully, the function calls itself recursively for the next row.
4. If a solution is found (all queens are placed), the print_solution function is called to display the current board configuration.
5. After exploring all possibilities, the function backtracks by removing the last placed queen and tries the next column in the current row.

Conclusion

The N-Queens problem is an excellent way to understand backtracking algorithms. This Python implementation demonstrates how recursion can efficiently explore possible configurations and find solutions to a complex problem.

Further Reading

For more information on the N-Queens problem and algorithms, consider checking:

• Wikipedia – Eight Queens Puzzle
• GeeksforGeeks – N-Queens Problem