Understanding N-Queens in Java

What We're Solving & Chessboard Rules

Solving geometric placement challenges under strict threat boundaries is a cornerstone of constraint programming. The N-Queens puzzle is a classic constraint satisfaction problem in computer science. The goal is to place N chess queens on an N × N chessboard such that no two queens can attack each other.

In the rules of chess, a queen is the most versatile and powerful piece on the board: it can strike horizontally along its row, vertically along its column, or diagonally in all four directions. To solve this puzzle, we must determine all valid configurations where N queens can coexist without any overlap of their paths of attack. For a standard 8 × 8 board, there are 92 unique solutions; for a smaller 4 × 4 board, there are exactly 2.

The Strategy

Recursive Backtracking with Pruning (Time O(N!), Space O(N))

Let's look at the implementation details of this recursive search strategy:

• Row-by-Row Search: Since we know each row must contain exactly one queen, we can structure our search space to traverse the chessboard row-by-row, starting at row 0. This reduces the problem complexity.
• Base Case: If our current row variable equals N, we have successfully placed a queen in every row without conflicts. We convert the current board state into a list of strings and add it to our results collection.
• Column Exploration: At the current row, we loop through each column col from 0 to N - 1 and check if placing a queen at board[row][col] is safe.
• Safety Verification: Since we build the board top-to-bottom, we only need to verify if there are existing queens in the rows above the current row. Specifically:
  1. Vertically upwards in the same column.
  2. Diagonally upwards to the left (primary diagonal).
  3. Diagonally upwards to the right (secondary diagonal).
• State Restoration: If the position is safe, we mark it (board[row][col] = 'Q') and recurse to row + 1. Once that recursive path completes, we restore the board cell (board[row][col] = '.') to clean up the state before evaluating the next column.

Detailed Trace Walkthrough

Let's trace the backtracking execution path for a 4 × 4 board (N = 4):

1. Step 1 (Row 0):
   • Place a queen at column 0. Row 0: [Q, ., ., .]. Recurse to row 1.
2. Step 2 (Row 1):
   • Column 0: Under attack from (0,0).
   • Column 1: Under attack diagonally from (0,0).
   • Column 2: Safe! Place queen → Row 1: [., ., Q, .]. Recurse to row 2.
3. Step 3 (Row 2):
   • Column 0: Attacks column 0 of Row 0.
   • Column 1: Attacks diagonally from Row 1 (1,2).
   • Column 2: Attacks column 2 of Row 1.
   • Column 3: Attacks diagonally from Row 1 (1,2).
   • Dead-End: No column is safe in Row 2. Backtrack to Row 1.
4. Step 4 (Row 1 Backtrack):
   • Remove queen from Column 2. Try Column 3 (safe) → Row 1: [., ., ., Q]. Recurse to row 2.
5. Step 5 (Row 2):
   • Column 1 is safe! Place queen → Row 2: [., Q, ., .]. Recurse to row 3.
6. Step 6 (Row 3):
   • Column 0, 1, 2, 3 are all under attack.
   • Dead-End: Backtrack to Row 2.
7. Step 7 (Recursive Retreat):
   • Remove queen from Row 2 col = 1. Backtrack to Row 1.
   • Remove queen from Row 1 col = 3. Backtrack to Row 0.
   • Move Row 0 queen to column 1 → Row 0: [., Q, ., .].
   • This branch eventually finds a valid solution: Row 0: [., Q, ., .], Row 1: [., ., ., Q], Row 2: [Q, ., ., .], Row 3: [., ., Q, .].

Code Highlights & Explanations

Key sections of our Java implementation:

• board[row][col] = 'Q'; backtrack(row + 1); board[row][col] = '.' implements state choice and restoration.
• isSafe(board, row, col) implements early pruning, preventing the algorithm from exploring branches that are already invalid.

Full Code Solution

Below is the complete, self-contained Java source code that solves the N-Queens problem, including a main driver to print the board layouts.

package io.practise.dsa;
 
import java.util.*;
 
public class NQueens {
 
    // Backtracking - O(n!) Time, O(n) Space
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        char[][] board = new char[n][n];
        for (char[] row : board) {
            Arrays.fill(row, '.');
        }
        backtrack(0, board, res);
        return res;
    }
 
    private void backtrack(int row, char[][] board, List<List<String>> res) {
        // Base case: If all rows are filled, we found a valid placement
        if (row == board.length) {
            List<String> list = new ArrayList<>();
            for (char[] r : board) {
                list.add(new String(r));
            }
            res.add(list);
            return;
        }
 
        // Try placing a queen in each column of the current row
        for (int col = 0; col < board.length; col++) {
            if (isSafe(board, row, col)) {
                // 1. Choose: Place the queen
                board[row][col] = 'Q';
 
                // 2. Explore: Recurse to place the queen in the next row
                backtrack(row + 1, board, res);
 
                // 3. Unchoose: Backtrack by removing the queen
                board[row][col] = '.';
            }
        }
    }
 
    private boolean isSafe(char[][] board, int row, int col) {
        // Check vertical column above
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') {
                return false;
            }
        }
 
        // Check top-left diagonal
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }
 
        // Check top-right diagonal
        for (int i = row - 1, j = col + 1; i >= 0 && j < board.length; i--, j++) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }
 
        return true;
    }
 
    public static void main(String[] args) {
        NQueens solver = new NQueens();
        int n = 4;
 
        System.out.println("--- N-Queens Demonstration ---");
        System.out.println("Chessboard Size: " + n + "x" + n);
        List<List<String>> solutions = solver.solveNQueens(n);
        System.out.println("Number of solutions found: " + solutions.size());
        
        System.out.println("\nAll Solutions:");
        for (int i = 0; i < solutions.size(); i++) {
            System.out.println("Solution #" + (i + 1) + ":");
            for (String row : solutions.get(i)) {
                System.out.println(row);
            }
            System.out.println();
        }
    }
}

Conclusion & Takeaways

The N-Queens problem is a beautiful showcase of the power of backtracking. By recursively placing queens row by row and checking constraints on the fly, we skip millions of invalid chess layouts, finding the valid layouts efficiently.