Introduction​

The N-Queens problem is a classic example of constraint satisfaction problems and explores ways to place n queens on an n×n chessboard such that no two queens can attack each other. This challenge is often solved using backtracking techniques and has various applications in algorithm design and artificial intelligence.

Video Explanation​

Watch

Problem Statement​

The goal is to place n queens on an n×n chessboard so that:

• No two queens are in the same row, column, or diagonal.

Approach​

Backtracking builds the solution step-by-step, eliminating configurations that violate constraints.

Algorithm​

1. Place Queen in Row: Place queens one by one in different rows, beginning with the leftmost column.
2. Check Safety: For each cell in the current row, check if placing the queen will not conflict with previously placed queens.
3. Recursive Backtracking: If a placement is safe, proceed to place the next queen in the following row.
4. Backtrack: If placing a queen in a column leads to no solution, remove the queen and try the next cell in the row.

Python Code Implementation​

# Function to check if a queen can be placed on the board at [row][col]
def is_safe(board, row, col, n):
    # Checking the left side of the row
    for i in range(col):
        if board[row][i] == 1:
            return False
    
    # Checking 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

    # Checking 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

# Function to solve N-Queens using backtracking
def solve_n_queens(board, col, n):
    # If all queens are placed, return True
    if col >= n:
        return True
    
    # Try placing a queen in each row for this column
    for i in range(n):
        # Check if it's safe to place the queen
        if is_safe(board, i, col, n):
            # Place the queen
            board[i][col] = 1

            # Recur to place the rest of the queens
            if solve_n_queens(board, col + 1, n):
                return True
            
            # If placing queen at board[i][col] doesn't lead to a solution, remove queen (backtrack)
            board[i][col] = 0

    return False

# Function to initialize the board and call solve_n_queens
def n_queens(n):
    # Initialize an n x n chessboard with all positions set to 0
    board = [[0 for _ in range(n)] for _ in range(n)]
    # Attempt to solve the N-Queens problem
    if solve_n_queens(board, 0, n):
        # If solution exists, print the board
        for row in board:
            print(row)
    else:
        # If no solution exists, print message
        print("No solution exists")

# Driver code to test the above functions
n = int(input("Enter the number of queens (and board size): "))
n_queens(n)

Explanation of Functions​

• is_safe(board, row, col, n): Checks if it is safe to place a queen at position [row][col] by ensuring no other queens threaten the position from the left side, upper-left diagonal, or lower-left diagonal.
• solve_n_queens(board, col, n): Solves the problem by placing queens one column at a time. If placing a queen in a specific cell doesn’t lead to a solution, it backtracks.
• n_queens(n): Initializes the board and starts the recursive process by calling solve_n_queens. If a solution is found, it prints the board configuration; otherwise, it outputs that no solution exists.

Complexity​

• Time Complexity: The time complexity is O(N!) due to the combinatorial nature of queen placements.
• Space Complexity: The space complexity is 𝑂(N²) because an n×n board is used to store the board configuration.

Example Walkthrough​

For a 4x4 board, the algorithm would place the queens row by row, backtracking as necessary until it finds a valid solution:

1. Initial Placement: The algorithm places the first queen in the top-left cell.
2. Row-by-Row Backtracking: As it tries to place each subsequent queen, it checks for safety, backtracks when conflicts arise, and adjusts placements until a valid configuration is found.

Visual Representation with Mermaid Diagram​

Here's a conceptual flow of the backtracking process in the N-Queens algorithm:

Note: This algorithm is adapted from GeeksforGeeks.