Every Way to Place N Non-Attacking Queens on a Board

Hard30–35 min

Topics

BacktrackingRecursionMatrix

Companies

AmazonGoogleMicrosoft

Place n chess queens on an n×n board so that no two attack each other — no shared row, column, or diagonal — and return every distinct arrangement that achieves this. Since two queens on the same row always attack each other, placing exactly one queen per row and choosing its column is enough to describe any candidate arrangement. Checking whether a candidate column is safe by re-examining every queen placed in an earlier row works, but repeats that examination from scratch at every single column tried, at every row. Maintaining directly which columns and which diagonals are currently occupied turns that repeated re-derivation into a single lookup — the search explores the exact same tree either way, but each conflict check along the way is answered immediately instead of recomputed.

Test Case 1:

Input:n = 4

Output:[["..Q.", "Q...", "...Q", ".Q.."], [".Q..", "...Q", "Q...", "..Q."]]

Explanation:The two ways to place 4 mutually non-attacking queens on a 4×4 board.

Test Case 2:

Input:n = 1

Output:[["Q"]]

Explanation:A single queen on a 1×1 board trivially doesn't attack anything.

Test Case 3:

Input:n = 2

Output:[]

Explanation:No arrangement of 2 queens on a 2×2 board avoids all of them attacking each other.

Constraints

◆1 ≤ n ≤ 8
◆A queen attacks any square sharing its row, column, or either diagonal
◆Each board is returned as n strings of length n, using 'Q' for a queen and '.' for an empty square
◆Results are returned sorted (each board compared row by row) for a stable, checkable answer

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Re-Scan Every Placed Queen at Each Attempt

Brute

Place one queen per row. Before trying a column at the current row, walk every queen placed at an earlier row and check directly whether it shares that column or either diagonal — an O(row) scan repeated for every column tried, at every row. This is correct (only column-per-row placements avoid same-row conflicts by construction), but re-deriving "is this column or diagonal already taken" by re-examining every earlier queen, over and over, is exactly the same fact recomputed many times over the course of the search.

TimeO(n! · n)

SpaceO(n)

Java

Try it out

class Solution {
    public String[][] nonAttackingQueenBoards(int n) {
        List<String[]> result = new ArrayList<>();
        int[] queenCol = new int[n];
        backtrack(n, 0, queenCol, result);
        result.sort((a, b) -> {
            for (int i = 0; i < a.length; i++) {
                int cmp = a[i].compareTo(b[i]);
                if (cmp != 0) return cmp;
            }
            return 0;
        });
        return result.toArray(new String[0][]);
    }

    private void backtrack(int n, int row, int[] queenCol, List<String[]> result) {
        if (row == n) {
            result.add(buildBoard(n, queenCol));
            return;
        }
        for (int c = 0; c < n; c++) {
            if (isSafe(row, c, queenCol)) {
                queenCol[row] = c;
                backtrack(n, row + 1, queenCol, result);
            }
        }
    }

    private boolean isSafe(int row, int col, int[] queenCol) {
        for (int r = 0; r < row; r++) {
            int c = queenCol[r];
            if (c == col || Math.abs(c - col) == Math.abs(r - row)) {
                return false;
            }
        }
        return true;
    }

    private String[] buildBoard(int n, int[] queenCol) {
        String[] board = new String[n];
        for (int r = 0; r < n; r++) {
            StringBuilder sb = new StringBuilder();
            for (int c = 0; c < n; c++) sb.append(c == queenCol[r] ? 'Q' : '.');
            board[r] = sb.toString();
        }
        return board;
    }
}

Optimal — Track Used Columns and Diagonals Directly

Optimal

Instead of re-examining every earlier queen to answer "is this column or diagonal free," maintain that fact directly: one set for occupied columns, and one each for the two diagonal directions (identified by row−col and row+col, which stay constant along a diagonal). Placing a queen adds one entry to each set; removing one on backtrack deletes them again. Checking whether a column or diagonal is available becomes a single O(1) lookup instead of an O(row) walk over every previously placed queen.

TimeO(n!)