Understanding N-Queens in Java

Introduction & Problem Explanation

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 chess, a queen is the most powerful piece; it can attack any other piece located in the same row, column, or along either of its two diagonals (primary and secondary). To solve this puzzle, we must find all unique grid layouts where N queens coexist in absolute peace. For example, for a 4 × 4 board, there are exactly 2 unique solutions.

The Algorithmic Approach

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

Since we must place exactly one queen per row, we can simplify our search space by traversing the board row-by-row. Starting at row 0:

• Base Case: If the current row matches N, we have placed all queens successfully. We copy the current board state and add it to our results list.
• Column Iteration: For the current row, we try to place a queen in each column col from 0 to N - 1.
• Safety Check: Before placing a queen at board[row][col], we check if it is safe. Since we build the board top-to-bottom, we only check for threats above:
  1. Vertically upwards in the same column col.
  2. Diagonally upwards to the left (primary diagonal direction).
  3. Diagonally upwards to the right (secondary diagonal direction).
• Explore and Backtrack: If safe, we place the queen (board[row][col] = 'Q'), recurse to row + 1, and then backtrack by removing the queen (board[row][col] = '.') before trying the next column.

Step-by-Step Execution Walkthrough

Let's trace the backtracking search for N = 4. We start with an empty board:

1. Step 1 (Row 0):
   • Place queen at col = 0. Row 0: [Q, ., ., .]. Recurse to row 1.
2. Step 2 (Row 1):
   • col = 0 (attacks (0,0) column).
   • col = 1 (attacks (0,0) diagonal).
   • col = 2 is safe! Place queen. Row 1: [., ., Q, .]. Recurse to row 2.
3. Step 3 (Row 2):
   • col = 0 (attacks (0,0) column).
   • col = 1 (attacks (1,2) diagonal).
   • col = 2 (attacks (1,2) column).
   • col = 3 (attacks (1,2) diagonal).
   • No columns are safe in Row 2! Backtrack to Row 1.
4. Step 4 (Backtrack to Row 1):
   • Remove queen from col = 2. Try col = 3 (safe!). Row 1: [., ., ., Q]. Recurse to row 2.
5. Step 5 (Row 2):
   • col = 1 is safe! Place queen. Row 2: [., Q, ., .]. Recurse to row 3.
6. Step 6 (Row 3):
   • All columns are under attack! col = 0, 1, 2, 3 are invalid. Backtrack to Row 2.
7. Step 7 (Backtrack recursively):
   • 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 col = 1: Row 0: [., Q, ., .]. This branch eventually finds a valid solution:
     Row 0: [., Q, ., .], Row 1: [., ., ., Q], Row 2: [Q, ., ., .], Row 3: [., ., Q, .].

Key Code Snippets & Explanations

Here is why the main logic in the solution is important:

• if (row == board.length): The base case confirming a complete board solution. We build a list of strings representing the board and add it to our answers.
• if (isSafe(board, row, col)): The pruning helper that stops recursion on invalid paths early, preventing unnecessary operations.
• board[row][col] = 'Q'; backtrack(row + 1, ...); board[row][col] = '.';: The choose-explore-unchoose backtracking pattern. Setting the cell back to '.' is crucial so that adjacent column scans starting at this row see an empty board.

Java Implementation Code

Below is the complete, self-contained Java source code that solves this problem. It also includes a main method that traces the execution with console outputs.

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

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.