Find a lesson, question or project

Start typing to search published content and planned structures.

↑ ↓ moveEnter openEsc close

N-Queens in Java: Place One Queen per Row, Then Undo

Generate all nonattacking queen boards with row-by-row backtracking, explain diagonal keys and undo, and trace the two solutions for n=4.

HardRecursion and backtrackingPattern: recursion, backtracking

Problem statement

Place n queens on an n×n chessboard so that no two attack each other. Return all distinct boards using Q for a queen and . for an empty square. Queens attack along rows, columns and both diagonal directions.

LeetCode N-Queens permits 1≤n≤9. For n=4 there are two boards; for n=2 and n=3 there are none. A failed size should return an empty list, not a partial board. This differs from N-Queens II, which asks only for the count.

Constraints & requirements

CONTRACT
LeetCode: 1≤n≤9. Queens may not share rows, columns or either diagonal. One queen per recursive row handles rows automatically; column and diagonal sets handle the other conflicts.

Examples 3 test cases

  1. Example 1 Case 1

    Input
    n=4
    Output
    [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

    There are two distinct boards, not just one successful placement.

  2. Example 2 Case 2

    Input
    n=1
    Output
    [["Q"]]

    The lone square is a complete valid board.

  3. Example 3 Case 3

    Input
    n=2
    Output
    []

    Every possible second queen attacks the first; no full board exists.

Solve on LeetCode ↗

Hints Optional

Hints become more specific one step at a time.
01Hint 1

Choose only a column in the current row, then recurse to the next row.

02Hint 2

Cells on the same diagonals share row−col or row+col.

03Hint 3

Remove the column and both diagonal reservations after every child so every board can be enumerated.

How to think before coding

Choose one row per call, so row conflicts disappear automatically. Column c, diagonal row−c and diagonal row+c are the three reservations to test. Reserve all three before descending, then remove all three afterward. Row==n means save a board snapshot, NOT return from the entire search, because every valid board is requested.

Brute force and the improvement

Place one queen in every row by trying all n column choices, without checking attacks until all rows are filled. That gives n^n assignments; pairwise attack checks cost O(n²) per complete assignment, for a loose O(n^(n+2)) bound. O(n) columns describe one candidate, excluding returned boards. Most candidates already fail after a few rows. Reserve occupied columns and diagonal keys as soon as a queen is placed. This cuts invalid prefixes early; enumeration still has output-sized work and an exponential search in the general case.

Intuition: one row makes one decision

If there are n nonattacking queens and n rows, each row must contain exactly one queen. Let a recursive call choose only the column for its row. This handles row conflicts automatically.

Three sets describe the other attacks:

  • columns stores occupied column numbers.
  • diagonal stores row−col.
  • antiDiagonal stores row+col.

Why these formulas? Cells (0,1) and (1,2) both have row−col=−1 and lie on one diagonal. Cells (0,3) and (1,2) both have row+col=3 and lie on the other. Negative diagonal keys are completely fine in a set.

The compact board array stores a column per row. [1,3,0,2] means queens at (0,1), (1,3), (2,0) and (3,2); it is not a list of four queens in one row.

Algorithm

  1. Start with row 0, an empty result and empty attack sets.
  2. Try each column in the current row.
  3. Skip occupied columns or diagonals.
  4. Reserve the board entry and all three keys, then recurse to row+1.
  5. When row equals n, build an independent board and save it.
  6. Undo the entry and every reserved key before trying the next column.

Unlike a yes/no search, finding one complete board must not stop the other branches.

Java solution

A fresh result list and fresh reservation sets belong to each invocation. Keeping a static result list would incorrectly mix answers from repeated calls, even if the search restores its sets.

Java
import java.util.*;

class Solution {
    public static List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>(); // Fresh per call, not a persistent static result.
        int[] board = new int[n]; Arrays.fill(board, -1); // board[row] records that row's chosen column.
        placeQueens(0, board, new HashSet<>(), new HashSet<>(), new HashSet<>(), result);
        return result; // Keep all distinct boards; do not stop after the first success.
    }
    private static void placeQueens(int row, int[] board, Set<Integer> columns,
            Set<Integer> diagonal, Set<Integer> antiDiagonal, List<List<String>> result) {
        if (row == board.length) { // Exactly one queen has been placed in every row.
            result.add(queenBoard(board)); // Build independent immutable row strings.
            return;
        }
        for (int col = 0; col < board.length; col++) {
            int diag = row - col, anti = row + col; // Equal values identify a shared diagonal.
            if (columns.contains(col) || diagonal.contains(diag) || antiDiagonal.contains(anti)) continue;
            board[row] = col; columns.add(col); diagonal.add(diag); antiDiagonal.add(anti); // Choose.
            placeQueens(row + 1, board, columns, diagonal, antiDiagonal, result); // Explore next row.
            board[row] = -1; columns.remove(col); diagonal.remove(diag); antiDiagonal.remove(anti); // Undo ALL state.
        }
    }
    private static List<String> queenBoard(int[] board) {
        List<String> rows = new ArrayList<>();
        for (int col : board) {
            char[] line = new char[board.length]; Arrays.fill(line, '.');
            line[col] = 'Q'; rows.add(new String(line)); // Snapshot before board choices change.
        }
        return rows;
    }

    public static void main(String[] args) {
        System.out.println(solveNQueens(4)); // Two boards: columns [1,3,0,2] and [2,0,3,1].
    }
}

Saved rows are independent Strings. Changing board[row] during later branches cannot change a completed answer.

Recursion tree and dry run

Numbered illustrated dry run for N-Queens; the text transcript explains the states.
Follow the numbered panels in order. Open full-size dry run ↗
Read the text transcript

Follow the Java, step by step

Example: n = 4

What to track: board[row] is that row’s chosen column. columns, diagonal (row−col), and antiDiagonal (row+col) reserve attacks. This traces an early failure, then the first solution; later siblings produce the second.

  1. Choose the first column in row 0

    Java operationboard[row] = col; columns.add(col); diagonal.add(diag); antiDiagonal.add(anti);
    Stateboard = [0,-1,-1,-1]; columns = {0}; diagonal = {0}; antiDiagonal = {0}

    All three reservations are added before entering row 1.

  2. Reject row-1 conflicts, then choose column 2

    Java operationif (columns.contains(col) || diagonal.contains(diag) || antiDiagonal.contains(anti)) continue;
    Staterow 1: col 0 is occupied; col 1 shares diagonal 0; col 2 is allowed; board = [0,2,-1,-1]

    This call must reject an attacked square before placing a queen, not after entering a child.

  3. Discover that row 2 has no legal column

    Java operationplaceQueens(row + 1, board, columns, diagonal, antiDiagonal, result);
    Staterow 2: col 0/2 are occupied; col 1 shares antiDiagonal 3; col 3 shares diagonal −1

    The loop creates no child for row 3 and returns without saving a board.

  4. Undo all row-1 reservations

    Java operationboard[row] = -1; columns.remove(col); diagonal.remove(diag); antiDiagonal.remove(anti);
    Stateboard restores to [0,-1,-1,-1]; column 2, diagonal −1 and antiDiagonal 3 are released

    The row-1 caller can now try col 3. That subtree also fails, so eventually the row-0 caller undoes col 0.

  5. Follow the next root branch to a complete board

    Java operationplaceQueens(row + 1, board, columns, diagonal, antiDiagonal, result);
    Statesuccessful choices: row0→1, row1→3, row2→0, row3→2; board = [1,3,0,2]

    Conflict checks still run at every row; this is not a hardcoded arrangement. The row-4 child has one queen in every row.

  6. Save rows that will not change on undo

    Java operationresult.add(queenBoard(board));
    Staterow = 4; result contains [".Q..","...Q","Q...","..Q."]

    queenBoard creates independent row strings, so later changes to board cannot alter this answer.

  7. Keep exploring after success

    Java operationboard[row] = -1; columns.remove(col); diagonal.remove(diag); antiDiagonal.remove(anti);
    Stateall waiting frames restore their choices; later root col 2 yields [2,0,3,1]; final board = [-1,-1,-1,-1]

    This is enumeration. Returning after the first solution would lose the second board; every success also unwinds and undoes.

Final result: two saved boards, with column arrays [1,3,0,2] and [2,0,3,1].

This is a pruned excerpt, not every attempted column:

Worked example · read from top to bottom
row 0
├─ col 0 → later rows run out of legal columns → undo
├─ col 1
│  └─ row 1 col 3
│     └─ row 2 col 0
│        └─ row 3 col 2 → save [1,3,0,2]
├─ col 2
│  └─ row 1 col 0 → row 2 col 3 → row 3 col 1
│     save [2,0,3,1]
└─ col 3 → later dead ends → undo
Chosen cell Column key row−col row+col
(0,1) 1 −1 1
(1,3) 3 −2 4
(2,0) 0 2 2
(3,2) 2 1 5

Every column key is different, and each diagonal column in the table also has distinct keys. The first saved board is:

Worked example · read from top to bottom
.Q..
...Q
Q...
..Q.

After saving it, row 3 removes its reservations; control returns to row 2. Undoing only board[row] would be insufficient: stale keys in the sets would falsely block later placements.

Why it works

Before row r, exactly rows 0 through r−1 have queens, and the sets contain precisely their attacks. Rejecting conflicting keys preserves nonattack. Every possible safe column is explored. Thus every valid row-to-column assignment is reached once, and only a complete n-row assignment is saved.

Undo restores all four pieces of shared state to the parent’s configuration, allowing independent sibling choices.

Complexity and alternative approaches

Ignoring diagonal pruning, distinct-column assignments resemble permutations. With expected constant-time set checks, a conservative search bound is O(n·n!), including scanning n columns at partial states. If P complete boards are returned, rendering them adds O(P·n²) character work and output storage.

Search-only auxiliary space is O(n) for the column array, three sets and stack. Do not include all returned boards and still call total memory O(n).

Boolean arrays or bitmasks can replace sets; diagonal arrays need offsets for negative row−col values. Scanning an entire board for every placement is simpler but adds avoidable checks. Counting-only search can avoid rendering, but would solve N-Queens II rather than this output contract.

Common mistakes

  • Checking columns but forgetting one diagonal direction.
  • Using row−col for both diagonal sets.
  • Removing only the queen entry, leaving attack keys behind.
  • Returning after the first saved board.
  • Sharing a result list across separate method calls.

Practice next

Next lessonSudoku Solver

Back to Recursion and backtracking →