N Queen Problem – GeeksforGeeks

The N Queen problem is a famous puzzle where the goal is to place N queens on an N×N chessboard such that no two queens threaten each other. This means that no two queens can share the same row, column, or diagonal.

Problem Statement:

Given an integer N, the task is to place N queens on an N×N chessboard such that no two queens attack each other. For example, if N = 4, one possible arrangement of queens is:

. Q . .
. . . Q
Q . . .
. . Q .

In this arrangement:

• There is exactly one queen in each row.
• There is exactly one queen in each column.
• No two queens share the same diagonal.

Approach:

The N Queen problem can be solved using Backtracking. The main idea is to place queens one by one in different rows, starting from the first row. For each row, you try all columns to place the queen and check if placing the queen leads to a safe configuration.

Here are the steps:

1. Place a queen in a column of the current row.
2. Check if placing the queen leads to any conflict (check column and diagonals).
3. If no conflict, move to the next row and repeat the process.
4. If all queens are placed successfully, the solution is found.
5. If a conflict occurs at any point, backtrack by removing the queen and trying the next column in the current row.

Solution in Python (Backtracking):

def is_safe(board, row, col, N):
    # Check the column
    for i in range(row):
        if board[i] == col or abs(board[i] - col) == abs(i - row):
            return False
    return True

def solve_nqueen_util(board, row, N):
    # If all queens are placed
    if row == N:
        print_board(board, N)
        return True

    res = False
    for col in range(N):
        if is_safe(board, row, col, N):
            board[row] = col
            res = solve_nqueen_util(board, row + 1, N) or res
            # Backtrack
            board[row] = -1

    return res

def print_board(board, N):
    for i in range(N):
        row = ['Q' if j == board[i] else '.' for j in range(N)]
        print(' '.join(row))
    print()

def solve_nqueen(N):
    board = [-1] * N  # Initialize the board with -1, which means no queens are placed
    if not solve_nqueen_util(board, 0, N):
        print("Solution does not exist")

# Test with N = 4
solve_nqueen(4)

Explanation:

1. is_safe(board, row, col, N): This function checks if it’s safe to place a queen at position (row, col). It checks for conflicts in the same column and diagonals.
2. solve_nqueen_util(board, row, N): This function places queens row by row using backtracking. If a solution is found, it prints the board.
3. print_board(board, N): This function prints the board configuration, where ‘Q’ represents a queen and ‘.’ represents an empty space.
4. solve_nqueen(N): This function initializes the board and starts the backtracking process.

Example Output (for N = 4):

. Q . .
. . . Q
Q . . .
. . Q .

Time Complexity:

• Worst-case time complexity: O(N!), since you are trying N positions for each row, and there are N rows to place the queens.

If you’d like further explanation on any part or need help with a different approach, feel free to ask!