Solving the N-Queen Problem Using Backtracking in Java

Let’s imagine you’re staring at a chessboard. It’s a standard N×N grid, and you need to place N queens on this board. But here’s the catch: No two queens can threaten each other. As you know, queens can move vertically, horizontally, and diagonally across the board. So, how do we place them on the board without them coming into conflict?

This is exactly what the N-Queen problem is all about. It's a classic example of a problem where we can apply backtracking, an algorithmic technique that tries all possible configurations but abandons those that don’t lead to a solution.

In this blog, we’ll dive deep into solving the N-Queen problem using backtracking in Java. I’ll explain how it works, why backtracking is a perfect fit for this, and walk you through a full Java code example that will help you visualize the process.

Get data science certification from the World’s top Universities. Learn Executive PG Programs, Advanced Certificate Programs, or Masters Programs to fast-track your career.

What Exactly is the N-Queen Problem?

Before we jump into the code, let's make sure we fully understand the N-Queen problem. The N-Queen problem is all about placing N queens on an N×N chessboard. The twist is that no two queens can attack each other. This means that:

1. No two queens can share the same row (which is kind of obvious since we’re placing one queen per row).
2. No two queens can share the same column.
3. No two queens can share the same diagonal.

For example:

• In a 4x4 chessboard, you need to place 4 queens in such a way that no two queens share a row, column, or diagonal.
• In an 8x8 board, you’d place 8 queens. This is often called the classic 8-Queens problem, and the solutions are popular examples of how backtracking can solve complex problems efficiently.

Must Explore: What are Data Structures & Algorithm

Why Backtracking is the Perfect Fit for N-Queen Problem

When you think about it, backtracking is an incredibly effective approach to solving the N-Queen problem. Here's why:

• Exploring the search space: You’re essentially trying different configurations of queens on the board, and if you hit a dead end, you backtrack and try a different path.
• Incremental construction: As you place each queen row by row, you’re progressively building up a potential solution. If you encounter a conflict, you backtrack and undo your choice, exploring a different possibility.
• Efficient pruning: One of the beauties of backtracking is that it allows you to prune the search space. If a queen placement is invalid (e.g., it attacks another queen), you immediately stop further exploration down that path. This dramatically reduces the number of configurations to check.

In the N-Queen problem, this means:

• We try placing queens in each row.
• For each row, we test each column to see if it’s a valid place for a queen (i.e., not under attack from another queen).
• If we get stuck (i.e., if no valid position exists for the queen in the current row), we backtrack to the previous row and try a different column.

This way, backtracking ensures that we explore all possible configurations but avoid checking invalid ones, saving a ton of time and effort.

Also Explore: Top 14 Most Common Data Mining Algorithms You Should Know

How Do We Solve N-Queen Problem? 

The approach to solving the N-Queen problem can be broken down into three main steps:

1. Place a Queen: Try to place a queen in a row and column where it doesn't conflict with any previously placed queens.
2. Backtrack if Invalid: If placing a queen leads to a conflict (same column, same diagonal), backtrack to the previous row and try another column.
3. Repeat Until Done: Repeat this process for every row until the entire board is filled with queens without conflicts. Once a valid configuration is found, we output the solution.

The Key Constraints to Check:

• Column Conflict: We need to ensure no two queens are placed in the same column. We can track this using a boolean array.
• Diagonal Conflicts: Diagonals are trickier, but we can track them with two arrays:
  • One for diagonals that go from top-left to bottom-right.
  • One for diagonals that go from top-right to bottom-left.

Time Complexity:

• The time complexity of backtracking for the N-Queen problem is O(N!) in the worst case because we try to place queens in every column of each row. However, with backtracking, we prune many paths early, so it’s much faster than brute force.

 Also Read: Top 10 Data Structures & Algorithm Interview Questions & Answers

The Java Code Solution

Now, let’s look at the Java code for solving the N-Queen problem using backtracking. Here’s how you can implement it:

Java Code:

public class NQueen {
 
// Function to solve the N-Queen problem using backtracking
public static boolean solveNQueens(int n) {
     // Create a 2D board of size n x n
     int[][] board = new int[n][n];
 
     // Arrays to keep track of columns and diagonals under attack
     boolean[] cols = new boolean[n]; // Columns
     boolean[] diag1 = new boolean[2 * n - 1]; // Diagonals with positive slope
     boolean[] diag2 = new boolean[2 * n - 1]; // Diagonals with negative slope
 
    // Start the backtracking process to solve the N-Queen problem
     if (placeQueens(board, 0, n, cols, diag1, diag2)) {
         printSolution(board);
         return true;
     } else {
         System.out.println("Solution does not exist.");
         return false;
     }
}
 
// Function to place queens using backtracking
private static boolean placeQueens(int[][] board, int row, int n, boolean[] cols, boolean[] diag1, boolean[] diag2) {
     // If all queens are placed, return true
     if (row == n) {
         return true;
     }
 
     // Try placing a queen in each column for the current row
     for (int col = 0; col < n; col++) {
         // Check if the queen can be placed at (row, col)
         if (cols[col] || diag1[row - col + n - 1] || diag2[row + col]) {
             continue; // Skip if the position is under attack
         }
 
         // Place the queen
         board[row][col] = 1;
         cols[col] = true;
        diag1[row - col + n - 1] = true;
         diag2[row + col] = true;
 
         // Recur to place queens in the next row
         if (placeQueens(board, row + 1, n, cols, diag1, diag2)) {
             return true; // If a valid configuration is found, return true
         }
 
         // Backtrack if placing queen at (row, col) doesn't lead to a solution
         board[row][col] = 0;
         cols[col] = false;
         diag1[row - col + n - 1] = false;
         diag2[row + col] = false;
     }
 
     // If no position is found for the queen in this row, return false
     return false;
}
 
// Function to print the solution
private static void printSolution(int[][] board) {
     System.out.println("Solution:");
     for (int i = 0; i < board.length; i++) {
         for (int j = 0; j < board[i].length; j++) {
             System.out.print(board[i][j] == 1 ? "Q " : ". ");
         }
         System.out.println();
     }
}
 
public static void main(String[] args) {
     int n = 8; // Change the size of the board here
     solveNQueens(n);
}
}

Explanation of the Code:

1. Data Structures:
   • cols[]: A boolean array to keep track of whether a column is under attack.
   • diag1[]: A boolean array to track diagonals that go from top-left to bottom-right.
   • diag2[]: A boolean array to track diagonals that go from top-right to bottom-left.
2. Backtracking Logic:
   • We try to place a queen in each column of the current row and check if it’s a valid position (i.e., no conflict with other queens).
   • If we find a valid position, we place the queen and recursively try to place queens in the next row.
   • If we get stuck (i.e., no valid positions for a queen in the current row), we backtrack by removing the queen and trying a different column in the previous row.
3. Solution Printing: When a valid configuration is found, we print the solution as a board, where "Q" represents a queen and "." represents an empty space.

Must Explore: Selection Sort Algorithm in Data Structure: Code, Function & Exampleed Certificate Programs, or Masters Programs to fast-track your career.

Example Output

Let’s say we run this code with n = 8 (the classic 8-Queen problem). The output might look something like this:

Solution:

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

Conclusion

The N-Queen problem is a fantastic example of how backtracking can be used to solve complex problems efficiently. By trying different configurations, pruning invalid options, and backtracking when necessary, backtracking algorithms can explore huge solution spaces in a smart way.

In this blog, I walked you through the entire process of solving the N-Queen problem using Java and backtracking. Hopefully, this gave you a solid understanding of both the problem and the algorithm, along with the logic behind how the backtracking technique works.

The N-Queen problem is a classic puzzle, and solving it can be both fun and insightful. It’s also a great way to deepen your understanding of recursive algorithms, backtracking, and optimization techniques in computer science.

If you have any questions or want to explore more variations of the problem, feel free to ask!

Unlock the power of data with our popular Data Science courses, designed to make you proficient in analytics, machine learning, and big data!

Explore our Popular Data Science Courses

Elevate your career by learning essential Data Science skills such as statistical modeling, big data processing, predictive analytics, and SQL!

Top Data Science Skills to Learn

Stay informed and inspired with our popular Data Science articles, offering expert insights, trends, and practical tips for aspiring data professionals!

Read our popular Data Science Articles