N-Queen Problem

The N-queen problem is a puzzle in computer science and mathematics in which N queens are to be placed on an N*N chessboard in such a way that no queens attack each other. This problem also helps you to understand the backtracking algorithms, recursion, and bit masking techniques. Whether you are preparing for coding interviews or competitive programming, understanding how to solve the N-queens problem is important. In this article, we will discuss what the N-queen problem is, how to solve it using backtracking, time and space complexity, and practical applications of the N-queens problem.

Table of Contents:

• What is the N-Queen Problem?
• How to Solve the N-Queen Problem?
• What is Backtracking?
• N-Queen Problem Using Backtracking
• Solving the N-Queen Problem using Backtracking with Bit-Masking
• Complexity Analysis of the N-Queens Problem
• Practical Applications of the N-Queens Problem
• Conclusion

What is the N-Queen Problem?

The N-queen problem is a computer science and mathematics problem in which n chess queens are placed on an n*n chessboard in such a way that no two queens can attack each other.

Here are a few conditions that you must follow to position n queens on the chessboard so that:

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

This means that each queen must be placed where it cannot see or attack another queen using the rules of chess.

Example:

For n=4, you have to place 4 queens on a 4*4 board so that no one can attack each other. 

So, one of the valid solutions is

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

Where each “Q” represents a queen, and each “.” represents an empty square.

How to Solve the N-Queen Problem?

You can solve the N-queen problem by placing the N queens on an n*n chess board in such a way that no two queens can attack each other. Here is a simple and step-by-step explanation of how to solve it by using backtracking.

1. Understand the Constraints

You must have this basic knowledge of the chess game, that a queen moves vertically in the same column, horizontally in the same row, and diagonally in both directions, left and right. So, you must place queens so that no two share the same row, column, and diagonal.

2. Choose an Algorithm and Use it

The most common and effective way to solve the N-queens problem is by using a backtracking algorithm. By backtracking, try placing a queen in a row and one column at a time. If it is safe, then move to the next row, and if you reach a dead end, then backtrack and try the next possibility.

3. Visualize the Solution

You can visualize the board using a 2D array or print a formatted board to understand the queen placements.

What is Backtracking?

Backtracking is an algorithmic technique that is used to solve problems that involve searching through all possible combinations to find a solution that satisfies certain constraints. It can also be called the depth-first search with pruning. Backtracking makes a solution step-by-step. So, if it finds that any step cannot possibly lead to a valid solution, then it backtracks and tries a different option for the valid solution. This technique is used in the N-Queen Problem, Sudoku Solver, Maze Solving, Word Search, Combinatorics, and Graph problems.

How It Works

1. Start from an empty solution.
2. Now, try adding a value or choice.
3. Check if the current step is valid or not. 
4. If the current step is valid, then move forward. 
5. If the current step is invalid, then backtrack or undo the last choice and try another possibility.
6. Repeat the steps until you reach a solution or try all options.

General Backtracking Pseudocode

function BACKTRACK(solution, step):
    if solution is complete:
        process(solution)   // print, store, or count it
        return

    for each valid choice at current step:
        if the choice is valid:
            make the choice
            BACKTRACK(updated solution, step + 1)
            undo the choice (backtrack)

N-Queen Problem Using Backtracking Algorithm

Here is a brief description of how to solve the n-queen problem using a backtracking algorithm with examples in C++, JAVA, and Python.

Goal

The main goal is to place N queens on an n*n chessboard in such a way that no two queens attack each other.

Pseudocode for the N-Queen Problem using the Backtracking Algorithm

function SOLVE_N_QUEENS(row):
    if row == N:
        print(board) or store solution
        return

    for col from 0 to N-1:
        if placing a queen at (row, col) is safe:
            place queen at (row, col)
            SOLVE_N_QUEENS(row + 1)
            remove queen from (row, col) // backtrack

Explanation: 

• In this pseudocode, the function SOLVE_N_QUEENS tries to place a queen in each column of the current row.
• If it is a safe move, then it continues to the next row.
• If it reaches row N, it means a full, valid solution is found.
• If a placement of the queen seems to lead to an invalid solution, then it backtracks by removing the queen and trying the next column.

Implementing the N-Queen Problem using Backtracking in C++

Output:

Explanation: This C++ code finds and prints only the first solution to the N-Queens problem using a backtracking algorithm. Queens are placed row-by-row with safe positions (the column and two diagonals) checked for conflicts.  A global found flag makes sure that the recursion stops once the first valid arrangement is found, and that one or more additional valid solutions are not printed.

Implementing the N-Queen Problem Solution using Backtracking in JAVA

Output:

Explanation: This JAVA code shows how the N-queen problem is solved using backtracking, in which queens are placed row by row in such a way that no two queens attack each other. Also, a found flag is used to stop when the first solution is found and then printed to the console.

Implementing the N-Queen Problem Solution using Backtracking in Python

Output:

Explanation: This Python code shows how the N-queen problem is solved using a backtracking algorithm. It iteratively places the queens on the board and checks if each placement is safe. A mutable found flag signal is used for the recursion to immediately terminate and prevent further searches when a solution is found.

Implementing the N-Queen Problem Solution using Backtracking with Optimization in C++

Output:

Explanation: This C++ code illustrates the N-queen problem solving using backtracking, N queens on N*N chessboards, such that no two queens can attack one another. The isSafe() method checks if a queen can be placed at a particular position, and the solve method recursively calls all the possible placements, which prints every valid solution.

Implementing the N-Queen Problem Solution using Backtracking with Optimization in JAVA

Output:

Explanation: This JAVA code shows how a static counter, solutionCount, is used to count the number of N-queen solutions. The solutionCount is used to increment before each solution is printed by printSolution to display the “Solution X:”. Now, the solutionCount is set to 0 in the main function, which makes sure that the numbering starts from the first for each execution.

Implementing the N-Queen Problem Solution using Backtracking with Optimization in Python

Output:

Explanation: The Python code illustrates how the N-queen problem can be solved through the use of a backtracking technique, by trying to place the queens row by row on an N*N board recursively. The is_safe is used to confirm that the queens are indeed placed at the proper position. If the placement is valid, then it is marked as a “Q” and is simply moved to the next row, or it backtracks if the placement is invalid. Finally, once all the valid queens are printed on the board.

Solving the N-Queen Problem using Backtracking with Bit-Masking

Before understanding the implementation, let’s know the core concept of Bit-Masking in N-Queens.

Core Concept of Bit-Masking in N-Queens

In N-Queens, bit-masking can be used to track column and diagonal availability with integer bits, rather than an array/list. Each bit in an integer represents a column or a diagonal, where:

• 1 = blocked, which means the place is occupied by another queen
• 0 = free, which means the place is available to place a queen.

This allows us to check and operate in constant time and memory efficiency on placing the queens on the chessboard.

While placing a queen at position (row, column), we must make sure that:

• No queen exists in the same column.
• No queen exists on the same left diagonal ().
• No queen exists on the same right diagonal (/).

We use three integers for this:

Now, for an n*n board, we only need the lowest n bits of each integer. For example, when n=4, we only need 4 bits because we have 4 columns. The binary number 0b1111 (Decimal 15) represents all positions in a row or mask being active.

So if a queen is placed in column 2, the column mask will be updated as:

columns = 0b0100 

This shows that column 2 is now occupied.

Now, to find the safe columns where a queen can be placed in the current row, we use this formula:

int available = ~(columns | diags1 | diags2) & ((1 << n) - 1);

Explanation:

• columns | diags1 | diags2 gives all positions under threat.
• ~(…) inverts the mask to show available positions.
• & ((1 << n) – 1) ensures only the lowest n bits (within board size) are used.

Once we have available, we extract the rightmost set bit (the lowest available column):

int position = available & -available;

After choosing a position for a queen, we have to mark it as used in the next recursive step:

solve(row + 1,
      columns | position,
      (diags1 | position) << 1,
      (diags2 | position) >> 1);

Here, 

• columns | position marks the column as used.
• (diags1 | position) << 1 marks the / diagonal and shifts it for the next row.
• (diags2 | position) >> 1 marks the diagonal and shifts it for the next row.

Step-by-Step Bitmask Example for (n = 4)

We are going to solve the N-Queens problem for a 4×4 board using backtracking and bit-masking. The board is empty at the start.

So, at the initial state:

row = 0
columns = 0b0000   // No columns used
diags1  = 0b0000   // No / diagonals used
diags2  = 0b0000   // No  diagonals used

Now, calculate available positions:

available = ~(columns | diags1 | diags2) & ((1 << 4) - 1)
          = ~0b0000 & 0b1111
          = 0b1111  // All 4 columns are available

Now, try placing a queen in column 0:

position = available & -available = 0b0001

Then, update masks for the next row:

columns = columns | position = 0b0000 | 0b0001 = 0b0001
diags1  = (diags1 | position) << 1 = (0b0000 | 0b0001) << 1 = 0b0010
diags2  = (diags2 | position) >> 1 = (0b0000 | 0b0001) >> 1 = 0b0000

Now, move to row 1:

row = 1
columns = 0b0001
diags1  = 0b0010
diags2  = 0b0000
available = ~(0b0001 | 0b0010 | 0b0000) & 0b1111
          = ~0b0011 & 0b1111 = 0b1100

So, we get the available columns: 2 and 3

Now, try placing a queen in column 2:

position = available & -available = 0b0100

Then, update masks for row 2:

columns = 0b0001 | 0b0100 = 0b0101
diags1  = (0b0010 | 0b0100) << 1 = 0b0110 << 1 = 0b1100
diags2  = (0b0000 | 0b0100) >> 1 = 0b0100 >> 1 = 0b0010

Now, move to row 2:

row = 2
columns = 0b0101
diags1  = 0b1100
diags2  = 0b0010
available = ~(0b0101 | 0b1100 | 0b0010) & 0b1111
          = ~0b1111 & 0b1111 = 0b0000

Since there is no available position, thus, we will backtrack.

Now, we will remove the queen from column 2 at row 1, try column 3 instead, and repeat this process until we find a complete solution.

Implementing the N-Queen Problem Solution using Backtracking using Bit-Masking in C++

Output:

Explanation: This C++ program solves the N-queens problem using backtracking with bit-masking by keeping track of the columns and diagonals by applying bitwise operations. It stores the queen positions in a vector, and when the arrangement is valid, it prints the arrangement; otherwise, it will keep tracking and trying to see if there is a valid arrangement of the queens on the board. The function __builtin_ctz() also converts a bitmask into a column number. The program stops searching for arrangements after it finds the first valid one.

Implementing the N-Queen Problem Solution using Backtracking using Bit-Masking in Java

Output:

Explanation: This Java program solves the N-Queens problem using backtracking with bit-masking to track which columns and diagonals are available for queen placement. This bit-masking implementation uses the least amount of state possible and places the queens row-wise in an array, only printing the first valid solution it finds. It uses bitwise operations like &, |, and shifts to make near-constant-time availability checks. The program also uses Integer.numberOfTrailingZeros() to get the column index from a bitmask.

Implementing the N-Queen Problem Solution using Backtracking using Bit-Masking in Python

Output:

Explanation: This Python program solves the N-Queens problem using backtracking with bit-masking. It uses integers to track the occupied columns and diagonals, which allows constant-time checks, and once a valid solution is found, it prints the board with queens and stops further recursion. Also, the bitwise operation .bit_length()-1 is used to find the column index of the placed queen.

Complexity Analysis of the N-Queens Problem

Here is the time and space complexity of the N-queens problem in brief:

1. Time Complexity

The N-queens problem with backtracking has a general worst-case time complexity of O(N!), where we try to place a queen in N possible columns for each row we iterate  1 <= row <= N, and we will have eliminated some of the possibilities based on the placement of our previous row. 

And with bit-masking optimization constants improve substantially, the asymptotic complexity is still exponential.

2. Space Complexity

The space complexity is O(N) to store the queens array, the recursion stack (depth N), and 3 bitmasks (N-bit integers).

Here is the table for the time and space complexity of this problem for a better understanding:

Practical Applications of the N-Queens Problem

Here are a few practical applications of the n-queens problem:

1. Constraint Satisfaction Problems (CSPs)

The N-Queens problem can represent actual CSPs, which consist of multiple variables with multiple constraints, like task scheduling, register allocation in compilers, and allocating resources.

2. Parallel Processing / CPU Core Allocation

Just as placing queens on a board must be done without conflicts-assigning tasks to multiple processors (or CPU cores) can also be modeled as a constraint problem to prevent resource contention or data collision.

3. Placement and layout design

In VLSI chip design and circuit layout, you must place components in a manner that is equivalent to placing non-attacking queens on a board.

4. Artificial Intelligence and Robotics

The N-Queens problem is often used to train AI in search, decision-making, and reasoning under constraints. Examples include robotic path-planning and resolving dynamic resource conflicts.

5. Teaching Algorithm Design

The N-Queens problem is commonly used to teach backtracking, recursion, bit manipulation, and optimization; thus making it commonplace in algorithm and data structures courses.

Conclusion

The N-queens problem is not just a chessboard problem, but also a great illustration of how algorithms solve hard problems, and is useful for us to understand backtracking, recursion, and other helpful programming techniques like bit-masking. The problem is taught in education and used in processes such as AI development, chip designing, and task scheduling that help programmers solve problems where there are constraints.

N-Queen Problem – FAQs