N-Queens

Free with account Updated Nov 19, 2026 · 6 min read
On this page

    Problem statement

    Place n queens on an n × n chessboard so that no two queens attack each other: no two may share a row, a column or a diagonal. Return every distinct arrangement, each as a list of n strings where Q marks a queen and . an empty square.

    The classic backtracking problem. It tests whether you can turn "try everything" into a search that rules out bad choices early, and whether you can express "same diagonal" in one line. Original problem: LeetCode 51.

    Example

    The two ways to place 4 queens safely on a 4 × 4 board; each is the mirror image of the other.
    The two ways to place 4 queens safely on a 4 × 4 board; each is the mirror image of the other.
    Input:  n = 4
    Output: [[".Q..",
              "...Q",
              "Q...",
              "..Q."],
             ["..Q.",
              "Q...",
              "...Q",
              ".Q.."]]
    Input:  n = 3
    Output: []        # no arrangement exists for n = 2 or 3

    Constraints (assumed)

    • 1 ≤ n ≤ 9 (the number of solutions grows fast: 92 for n = 8, 352 for n = 9).

    What this question tests

    • Structuring a backtracking search: one decision per row, recurse, undo.
    • Encoding the constraints so each safety check is O(1): a column set and two diagonal sets keyed by r − c and r + c.
    • Building the output cleanly without copying the whole board at every step.

    Questions to ask first

    1. All solutions, or just how many? (Here: all boards. Counting is the N-Queens II follow-up.)
    2. Does the order of solutions matter? (Here: no.)
    3. Do rotations and reflections count as different solutions? (Here: yes.)
    4. How big can n get? Exponential search is fine up to about 12–14.