What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 13 patterns and 225 practice problems is 100% free to access with no credit card required. New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins. Each AI coach question costs 1-5 coins, priced by the server according to its size. AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK). Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1). Nothing on the site is sold for money: coins can only be earned, never bought.

What is the refund and cancellation policy?

Hi👋SpeedAlgo sells nothing for money: there are no subscriptions, renewals or charges, so there is nothing to cancel or refund. Nothing on the site is sold for money: coins can only be earned, never bought.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo uses deliberate practice for each pattern: learn the loop invariant, Big-O proof and edge cases from a side-by-side template and a step-by-step debugger, rebuild the template from memory, then solve a new problem on your own against a graded test suite.

12. N-Queens • Invariant Proof & Speed-Run

Theory Context•Backtracking & State Search

HardLC 51

N-Queens (LeetCode 51)

Target Frequency:MetaGoogleAmazon

Placing n chess queens on an n x n board so that no two queens share a row, column, or diagonal is the classic n-queens puzzle.

Given n, return every distinct board arrangement that solves the puzzle, in any order.

Represent each solution as a list of row strings, where 'Q' marks a queen and '.' marks an empty square.

Worked Examples

Example 1

Input:n = 4

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

Explanation: A 4x4 board has exactly two safe queen arrangements: one places queens at columns 1,3,0,2 (row by row), and the other at columns 2,0,3,1 -- both leave no queen sharing a row, column, or diagonal with another.

Example 2

Input:n = 1

Output:[["Q"]]

Explanation: One queen on a 1x1 board attacks nothing.

⚖️Formal Constraints & Bounds

1 <= n <= 9

Deep-Dive & Conceptual Insights

Core Insight

Main diagonal coordinates share a constant difference (r - c) and anti-diagonals share a constant sum (r + c). Using three O(1) lookup sets replaces full board scans with instant collision tests.

Real-World Scenario & Production Applications

Automated theorem proving, FPGA routing conflict resolution, register allocation in optimizing compilers.

Subproblems & Recurrence Decomposition3 Phases

🧩Subproblem 1: Row-by-Row Placement Decision

Since no two queens can ever share a row, place exactly one queen per row and backtrack column-by-column within that row -- this alone cuts the search space from placing N queens anywhere to just choosing N column indices.

Mathematical Recurrence / Code Invariant

def backtrack(row):
    if row == n:
        record_solution()
        return
    for col in range(n):
        if is_safe(row, col):
            place(row, col)
            backtrack(row + 1)
            remove(row, col)  # undo before trying next col

Step-by-Step Execution Trace Table

Step	Row	Candidate Col `c`	Conflict Check (`cols`, `r-c`, `r+c`)	Action	Placed Queens	Next State / Backtrack
1	`0`	`c=1`	All clear: `1 ∉ cols`, `-1 ∉ diag1`, `1 ∉ diag2`	Place Queen	`[(0,1)]`	Recurse `row=1`
2	`1`	`c=3`	All clear: `3 ∉ cols`, `-2 ∉ diag1`, `4 ∉ diag2`	Place Queen	`[(0,1), (1,3)]`	Recurse `row=2`
3	`2`	`c=0`	All clear: `0 ∉ cols`, `2 ∉ diag1`, `2 ∉ diag2`	Place Queen	`[(0,1), (1,3), (2,0)]`	Recurse `row=3`
4	`3`	`c=2`	All clear: `2 ∉ cols`, `1 ∉ diag1`, `5 ∉ diag2`	Place Queen	`[(0,1), (1,3), (2,0), (3,2)]`	Recurse `row=4`
5	`4`	—	Base case reached (`r == 4`)	✅ Record Solution 1	`[".Q..", "...Q", "Q...", "..Q."]`	Backtrack to `row=3`
6	`3`	`c=2`	Un-choose: remove `c=2`, `r-c=1`, `r+c=5`	Revert `.`	`[(0,1), (1,3), (2,0)]`	Try next candidate

Trace Inputn = 4

Expected[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

Step	Row	Candidate Col `c`	Conflict Check (`cols`, `r-c`, `r+c`)	Action	Placed Queens	Next State / Backtrack
1	`0`	`c=1`	All clear: `1 ∉ cols`, `-1 ∉ diag1`, `1 ∉ diag2`	Place Queen	`[(0,1)]`	Recurse `row=1`
2	`1`	`c=3`	All clear: `3 ∉ cols`, `-2 ∉ diag1`, `4 ∉ diag2`	Place Queen	`[(0,1), (1,3)]`	Recurse `row=2`
3	`2`	`c=0`	All clear: `0 ∉ cols`, `2 ∉ diag1`, `2 ∉ diag2`	Place Queen	`[(0,1), (1,3), (2,0)]`	Recurse `row=3`
4	`3`	`c=2`	All clear: `2 ∉ cols`, `1 ∉ diag1`, `5 ∉ diag2`	Place Queen	`[(0,1), (1,3), (2,0), (3,2)]`	Recurse `row=4`
5	`4`	—	Base case reached (`r == 4`)	✅ Record Solution 1	`[".Q..", "...Q", "Q...", "..Q."]`	Backtrack to `row=3`
6	`3`	`c=2`	Un-choose: remove `c=2`, `r-c=1`, `r+c=5`	Revert `.`	`[(0,1), (1,3), (2,0)]`	Try next candidate

Code Shape

Archetype Code Shape

Python

1	cols, diag, anti = set(), set(), set()
2	for c in range(n):
3	if c in cols or (r - c) in diag or (r + c) in anti:
4	continue
5	place a queen at (r, c) and add c, r - c and r + c to the three sets
6	backtrack(r + 1)
7	remove the queen and remove c, r - c and r + c from the three sets

Conceptual Narrative

🧭 Conceptual Foundation & Pattern Intuition

The N-Queens puzzle places $N$ non-attacking queens on an $N \times N$ chessboard such that no two queens share the same row, column, or diagonal. A brute force that tests all $\binom{N^2}{N}$ placements is computationally impossible ( $N=8$ gives $4.4$ billion configurations). Backtracking drastically reduces this space by placing queens row by row: since every row must contain exactly one queen, we only ever test one queen per row. The challenge is checking diagonal attacks. Rather than scanning across the board in $O(N)$ time for each placement, we use an instant $O(1)$ coordinate hashing trick:

Columns: Indexed directly by column $c$ .
Major Diagonals ( $\backslash$ ): Every square on a top-left to bottom-right diagonal shares the invariant $(r - c = \text{constant})$ .
Minor Diagonals ( $/$ ): Every square on a top-right to bottom-left diagonal shares the invariant $(r + c = \text{constant})$ .

🏟️ The Analogy: Air Traffic Controllers on Runway Coordinates

Imagine an airport with $N$ intersecting runways laid out on a grid. You need to land $N$ airplanes simultaneously. To avoid radar collisions, no two planes can share the same horizontal latitude (row), vertical longitude (column), or flight paths tilted at $45^\circ$ (diagonals). An automated transponder assigns each landing plane three radio beacons: their column $c$ , their down-diagonal code $r - c$ , and their up-diagonal code $r + c$ . If any incoming plane's transponder matches an already occupied beacon, that landing site is instantly rejected.

🔑 Why It Works

By storing occupied coordinates in three small hash sets, the attack conflict check drops from $O(N)$ board scans to one $O(1)$ set lookup per line.

$O(N)$ directional ray scanning trap: Scanning 8 directions across the 2D board on every placement ( $O(N)$ per square). Using hash sets or bitmasks for cols, diag1 (r - c), and diag2 (r + c) reduces conflict checks to $O(1)$ .
Unnecessary 2D grid cell iteration: Iterating over both rows and columns simultaneously in the recursion loop ( $N^2$ branching). Because each row must contain exactly one queen, iterating row-by-row reduces the branching tree strictly to $N!$ .
Asymmetric state cleanup on backtrack: Removing the column marker from cols but forgetting to remove r - c from diag1 or r + c from diag2, so later sibling branches are blocked by a queen that is no longer on the board.

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

Pattern Recognition Signals

The 10-second spot

Place N queens on an N×N board so that no two attack each other: a row/column/diagonal constraint problem. Queens on one down-right diagonal share r - c, and queens on one down-left diagonal share r + c, so each line has a single number to track.

Formulating the Predicate & Invariants

Turning intuition into a boolean rule

Invariant: rows 0 to r - 1 each hold one queen, no two of them attack each other, and cols, diag and anti hold exactly their columns and diagonals.

Silent Failure Traps & Edge Cases

Where confident candidates still lose points

Forgetting to undo diagonal sets on backtrack: Both the column and both diagonal sets must remove the current position when backtracking out of a branch.

The 60-Second Interview Pitch

Say this out loud before you type a single line

I'd use Constraint Backtracking. Since each row must have exactly one queen, I place queens row-by-row from r = 0 to n - 1. I maintain three sets to detect attacks in O(1): cols for column collisions, diag storing (r - c) for down-right diagonals, and anti storing (r + c) for down-left diagonals. For each column c in row r, if c, r - c and r + c are not in the sets, I place the queen, add to all three sets, recurse on r + 1, and undo every mark on return. When r == n, I save a copy of the board. Runs in O(N!) time, with O(N^2) for the board and O(N) for the sets and the stack.

Big-O Invariant Derivation

Complexity & Mathematical Proof

TIME COMPLEXITY

O(N!)

Look at the recursion tree: In row 0, we have N placement choices. Placing a queen eliminates 1 column and at least 1 diagonal direction from the next row. Thus, in row 1, at most N-1 candidate positions remain; in row 2, at most N-2 positions; down to row N-1 which has at most 1 position. The upper bound on tree nodes visited is strictly bounded by N · (N-1) · (N-2) ... 1 = O(N!). At each valid leaf solution (r = N), constructing the N x N string representation takes O(N^2) time. Multiplying the search space by board reconstruction yields O(N!) upper bounded search time.

SPACE COMPLEXITY

O(N^2) board + O(N) sets and recursion stack, output not counted

Look at our memory allocations: We explore row-by-row from r = 0 to r = N, so the call stack consumes at most N frames: O(N). We maintain three hash sets (cols, diag, anti), each storing at most N integers: O(N) auxiliary space. The working 2D board matrix uses O(N^2) memory during search. Storing all S(N) solutions in the output list requires O(S(N) · N^2) space.

Formal Recurrence Relation

$T(N) \le \sum_{r=0}^{N-1} \frac{N!}{(N-r)!} \approx O(N!)$

Derivation Progression

Row-by-Row Branching Bounds

$W_r \le N - r \text{ choices at row } r$

Placing a queen in row r removes its column and diagonal trajectories from subsequent rows, bounding branch width to N - r.

O(1) Collision Lookups

$O(1) \text{ set tests for } (c \in \text{cols}, r-c \in \text{diag}, r+c \in \text{anti})$

Mathematical invariants along diagonals avoid linear ray casting across the board on every step.

Factorial Tree Convergence

$\prod_{r=0}^{N-1} (N - r) = N! \implies O(N!)$

The permutation branching tree is strictly bounded by N!, eliminating over 99.999% of invalid grid combinations.

Variable Definitions

$N$

Dimension of the N x N chessboard and total number of queens to place

$S(N)$

Total count of distinct valid non-attacking solutions (S(4)=2, S(8)=92, S(9)=352)

Memory Architecture & Bounds

🟣 Call Stack

O(N) Recursion frames bounded by board height N

🔵 Auxiliary Heap

O(N) For attack lookup sets (cols, diag, anti) + O(N^2) for working character grid

🟢 Output Space

O(S(N) · N^2) To store all distinct string board configurations

Boundary Best / Worst Cases

Best Case

$O(1)$ for N = 1 (instant placement).

Average Case

$O(N!)$ .

Worst Case

$O(N!)$ exhaustive state tree traversal to find all valid placements.

Decision & State-Space Search Tree

Synthesizing vector architecture diagram...

Staff+ Engineering Perspective

Senior SWE Deconstruction & Hardware Caveats

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

Triggers: "n queens on n x n chessboard", "no two queens attack each other". Grid Constraint Satisfaction: row-by-row placement with $O(1)$ diagonal conflict testing using mathematical invariants: - Column invariant: $c$ - Main diagonal invariant: $r - c$ is constant along $\searrow$ - Anti-diagonal invariant: $r + c$ is constant along $\swarrow$ .

CONSTRAINTS & BOUNDS

$1 \le n \le 9$ . The search visits 2,057 calls of backtrack for $n = 8$ (92 solutions), so the limit is tiny; the output grows with the number of solutions.

FAANG PRODUCTION TRAPS & EDGE CASES

Scanning diagonals via loops costs $O(N)$ per check; the sets make each check $O(1)$ instead.

Theory Context•Backtracking & State Search

HardLC 51

N-Queens (LeetCode 51)

Target Frequency:MetaGoogleAmazon

Placing n chess queens on an n x n board so that no two queens share a row, column, or diagonal is the classic n-queens puzzle.

Given n, return every distinct board arrangement that solves the puzzle, in any order.

Represent each solution as a list of row strings, where 'Q' marks a queen and '.' marks an empty square.

Worked Examples

Example 1

Input:n = 4

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

Example 2

Input:n = 1

Output:[["Q"]]

Explanation: One queen on a 1x1 board attacks nothing.

⚖️Formal Constraints & Bounds

1 <= n <= 9

Deep-Dive & Conceptual Insights

Core Insight

Main diagonal coordinates share a constant difference (r - c) and anti-diagonals share a constant sum (r + c). Using three O(1) lookup sets replaces full board scans with instant collision tests.

Real-World Scenario & Production Applications

Automated theorem proving, FPGA routing conflict resolution, register allocation in optimizing compilers.

Subproblems & Recurrence Decomposition3 Phases

🧩Subproblem 1: Row-by-Row Placement Decision

Mathematical Recurrence / Code Invariant

def backtrack(row):
    if row == n:
        record_solution()
        return
    for col in range(n):
        if is_safe(row, col):
            place(row, col)
            backtrack(row + 1)
            remove(row, col)  # undo before trying next col

Step-by-Step Execution Trace Table

Step	Row	Candidate Col `c`	Conflict Check (`cols`, `r-c`, `r+c`)	Action	Placed Queens	Next State / Backtrack
1	`0`	`c=1`	All clear: `1 ∉ cols`, `-1 ∉ diag1`, `1 ∉ diag2`	Place Queen	`[(0,1)]`	Recurse `row=1`
2	`1`	`c=3`	All clear: `3 ∉ cols`, `-2 ∉ diag1`, `4 ∉ diag2`	Place Queen	`[(0,1), (1,3)]`	Recurse `row=2`
3	`2`	`c=0`	All clear: `0 ∉ cols`, `2 ∉ diag1`, `2 ∉ diag2`	Place Queen	`[(0,1), (1,3), (2,0)]`	Recurse `row=3`
4	`3`	`c=2`	All clear: `2 ∉ cols`, `1 ∉ diag1`, `5 ∉ diag2`	Place Queen	`[(0,1), (1,3), (2,0), (3,2)]`	Recurse `row=4`
5	`4`	—	Base case reached (`r == 4`)	✅ Record Solution 1	`[".Q..", "...Q", "Q...", "..Q."]`	Backtrack to `row=3`
6	`3`	`c=2`	Un-choose: remove `c=2`, `r-c=1`, `r+c=5`	Revert `.`	`[(0,1), (1,3), (2,0)]`	Try next candidate

Trace Inputn = 4

Expected[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

Step	Row	Candidate Col `c`	Conflict Check (`cols`, `r-c`, `r+c`)	Action	Placed Queens	Next State / Backtrack
1	`0`	`c=1`	All clear: `1 ∉ cols`, `-1 ∉ diag1`, `1 ∉ diag2`	Place Queen	`[(0,1)]`	Recurse `row=1`
2	`1`	`c=3`	All clear: `3 ∉ cols`, `-2 ∉ diag1`, `4 ∉ diag2`	Place Queen	`[(0,1), (1,3)]`	Recurse `row=2`
3	`2`	`c=0`	All clear: `0 ∉ cols`, `2 ∉ diag1`, `2 ∉ diag2`	Place Queen	`[(0,1), (1,3), (2,0)]`	Recurse `row=3`
4	`3`	`c=2`	All clear: `2 ∉ cols`, `1 ∉ diag1`, `5 ∉ diag2`	Place Queen	`[(0,1), (1,3), (2,0), (3,2)]`	Recurse `row=4`
5	`4`	—	Base case reached (`r == 4`)	✅ Record Solution 1	`[".Q..", "...Q", "Q...", "..Q."]`	Backtrack to `row=3`
6	`3`	`c=2`	Un-choose: remove `c=2`, `r-c=1`, `r+c=5`	Revert `.`	`[(0,1), (1,3), (2,0)]`	Try next candidate

Code Shape

Archetype Code Shape

Python

1	cols, diag, anti = set(), set(), set()
2	for c in range(n):
3	if c in cols or (r - c) in diag or (r + c) in anti:
4	continue
5	place a queen at (r, c) and add c, r - c and r + c to the three sets
6	backtrack(r + 1)
7	remove the queen and remove c, r - c and r + c from the three sets

Conceptual Narrative

🧭 Conceptual Foundation & Pattern Intuition

Columns: Indexed directly by column $c$ .
Major Diagonals ( $\backslash$ ): Every square on a top-left to bottom-right diagonal shares the invariant $(r - c = \text{constant})$ .
Minor Diagonals ( $/$ ): Every square on a top-right to bottom-left diagonal shares the invariant $(r + c = \text{constant})$ .

🏟️ The Analogy: Air Traffic Controllers on Runway Coordinates

🔑 Why It Works

By storing occupied coordinates in three small hash sets, the attack conflict check drops from $O(N)$ board scans to one $O(1)$ set lookup per line.

$O(N)$ directional ray scanning trap: Scanning 8 directions across the 2D board on every placement ( $O(N)$ per square). Using hash sets or bitmasks for cols, diag1 (r - c), and diag2 (r + c) reduces conflict checks to $O(1)$ .
Unnecessary 2D grid cell iteration: Iterating over both rows and columns simultaneously in the recursion loop ( $N^2$ branching). Because each row must contain exactly one queen, iterating row-by-row reduces the branching tree strictly to $N!$ .
Asymmetric state cleanup on backtrack: Removing the column marker from cols but forgetting to remove r - c from diag1 or r + c from diag2, so later sibling branches are blocked by a queen that is no longer on the board.

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

Pattern Recognition Signals

The 10-second spot

Formulating the Predicate & Invariants

Turning intuition into a boolean rule

Invariant: rows 0 to r - 1 each hold one queen, no two of them attack each other, and cols, diag and anti hold exactly their columns and diagonals.

Silent Failure Traps & Edge Cases

Where confident candidates still lose points

Forgetting to undo diagonal sets on backtrack: Both the column and both diagonal sets must remove the current position when backtracking out of a branch.

The 60-Second Interview Pitch

Say this out loud before you type a single line

I'd use Constraint Backtracking. Since each row must have exactly one queen, I place queens row-by-row from r = 0 to n - 1. I maintain three sets to detect attacks in O(1): cols for column collisions, diag storing (r - c) for down-right diagonals, and anti storing (r + c) for down-left diagonals. For each column c in row r, if c, r - c and r + c are not in the sets, I place the queen, add to all three sets, recurse on r + 1, and undo every mark on return. When r == n, I save a copy of the board. Runs in O(N!) time, with O(N^2) for the board and O(N) for the sets and the stack.

Big-O Invariant Derivation

Complexity & Mathematical Proof

TIME COMPLEXITY

O(N!)

SPACE COMPLEXITY

O(N^2) board + O(N) sets and recursion stack, output not counted

Formal Recurrence Relation

$T(N) \le \sum_{r=0}^{N-1} \frac{N!}{(N-r)!} \approx O(N!)$

Derivation Progression

Row-by-Row Branching Bounds

$W_r \le N - r \text{ choices at row } r$

Placing a queen in row r removes its column and diagonal trajectories from subsequent rows, bounding branch width to N - r.

O(1) Collision Lookups

$O(1) \text{ set tests for } (c \in \text{cols}, r-c \in \text{diag}, r+c \in \text{anti})$

Mathematical invariants along diagonals avoid linear ray casting across the board on every step.

Factorial Tree Convergence

$\prod_{r=0}^{N-1} (N - r) = N! \implies O(N!)$

The permutation branching tree is strictly bounded by N!, eliminating over 99.999% of invalid grid combinations.

Variable Definitions

$N$

Dimension of the N x N chessboard and total number of queens to place

$S(N)$

Total count of distinct valid non-attacking solutions (S(4)=2, S(8)=92, S(9)=352)

Memory Architecture & Bounds

🟣 Call Stack

O(N) Recursion frames bounded by board height N

🔵 Auxiliary Heap

O(N) For attack lookup sets (cols, diag, anti) + O(N^2) for working character grid

🟢 Output Space

O(S(N) · N^2) To store all distinct string board configurations

Boundary Best / Worst Cases

Best Case

$O(1)$ for N = 1 (instant placement).

Average Case

$O(N!)$ .

Worst Case

$O(N!)$ exhaustive state tree traversal to find all valid placements.

Decision & State-Space Search Tree

Synthesizing vector architecture diagram...

Staff+ Engineering Perspective

Senior SWE Deconstruction & Hardware Caveats

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

CONSTRAINTS & BOUNDS

$1 \le n \le 9$ . The search visits 2,057 calls of backtrack for $n = 8$ (92 solutions), so the limit is tiny; the output grows with the number of solutions.

FAANG PRODUCTION TRAPS & EDGE CASES

Scanning diagonals via loops costs $O(N)$ per check; the sets make each check $O(1)$ instead.

def backtrack(row): if row == n: record_solution() return for col in range(n): if is_safe(row, col): place(row, col) backtrack(row + 1) remove(row, col) # undo before trying next col

Step

Row

Candidate Col c

Conflict Check (cols, r-c, r+c)

Action

Placed Queens

Next State / Backtrack

0

c=1

All clear: 1 ∉ cols, -1 ∉ diag1, 1 ∉ diag2

Place Queen

[(0,1)]

Recurse row=1

1

c=3

All clear: 3 ∉ cols, -2 ∉ diag1, 4 ∉ diag2

Place Queen

[(0,1), (1,3)]

Recurse row=2

2

c=0

All clear: 0 ∉ cols, 2 ∉ diag1, 2 ∉ diag2

Place Queen

[(0,1), (1,3), (2,0)]

Recurse row=3

3

c=2

All clear: 2 ∉ cols, 1 ∉ diag1, 5 ∉ diag2

Place Queen

[(0,1), (1,3), (2,0), (3,2)]

Recurse row=4

4

—

Base case reached (r == 4)

✅ Record Solution 1

[".Q..", "...Q", "Q...", "..Q."]

Backtrack to row=3

3

c=2

Un-choose: remove c=2, r-c=1, r+c=5

Revert .

[(0,1), (1,3), (2,0)]

Try next candidate

Step

Row

Candidate Col c

Conflict Check (cols, r-c, r+c)

Action

Placed Queens

Next State / Backtrack

0

c=1

All clear: 1 ∉ cols, -1 ∉ diag1, 1 ∉ diag2

Place Queen

[(0,1)]

Recurse row=1

1

c=3

All clear: 3 ∉ cols, -2 ∉ diag1, 4 ∉ diag2

Place Queen

[(0,1), (1,3)]

Recurse row=2

2

c=0

All clear: 0 ∉ cols, 2 ∉ diag1, 2 ∉ diag2

Place Queen

[(0,1), (1,3), (2,0)]

Recurse row=3

3

c=2

All clear: 2 ∉ cols, 1 ∉ diag1, 5 ∉ diag2

Place Queen

[(0,1), (1,3), (2,0), (3,2)]

Recurse row=4

4

—

Base case reached (r == 4)

✅ Record Solution 1

[".Q..", "...Q", "Q...", "..Q."]

Backtrack to row=3

3

c=2

Un-choose: remove c=2, r-c=1, r+c=5

Revert .

[(0,1), (1,3), (2,0)]

Try next candidate

🧭 Conceptual Foundation & Pattern Intuition

Columns: Indexed directly by column $c$ .
Major Diagonals ( $\backslash$ ): Every square on a top-left to bottom-right diagonal shares the invariant $(r - c = \text{constant})$ .
Minor Diagonals ( $/$ ): Every square on a top-right to bottom-left diagonal shares the invariant $(r + c = \text{constant})$ .

🏟️ The Analogy: Air Traffic Controllers on Runway Coordinates

🔑 Why It Works

By storing occupied coordinates in three small hash sets, the attack conflict check drops from $O(N)$ board scans to one $O(1)$ set lookup per line.

def backtrack(row): if row == n: record_solution() return for col in range(n): if is_safe(row, col): place(row, col) backtrack(row + 1) remove(row, col) # undo before trying next col

Step

Row

Candidate Col c

Conflict Check (cols, r-c, r+c)

Action

Placed Queens

Next State / Backtrack

0

c=1

All clear: 1 ∉ cols, -1 ∉ diag1, 1 ∉ diag2

Place Queen

[(0,1)]

Recurse row=1

1

c=3

All clear: 3 ∉ cols, -2 ∉ diag1, 4 ∉ diag2

Place Queen

[(0,1), (1,3)]

Recurse row=2

2

c=0

All clear: 0 ∉ cols, 2 ∉ diag1, 2 ∉ diag2

Place Queen

[(0,1), (1,3), (2,0)]

Recurse row=3

3

c=2

All clear: 2 ∉ cols, 1 ∉ diag1, 5 ∉ diag2

Place Queen

[(0,1), (1,3), (2,0), (3,2)]

Recurse row=4

4

—

Base case reached (r == 4)

✅ Record Solution 1

[".Q..", "...Q", "Q...", "..Q."]

Backtrack to row=3

3

c=2

Un-choose: remove c=2, r-c=1, r+c=5

Revert .

[(0,1), (1,3), (2,0)]

Try next candidate

Step

Row

Candidate Col c

Conflict Check (cols, r-c, r+c)

Action

Placed Queens

Next State / Backtrack

0

c=1

All clear: 1 ∉ cols, -1 ∉ diag1, 1 ∉ diag2

Place Queen

[(0,1)]

Recurse row=1

1

c=3

All clear: 3 ∉ cols, -2 ∉ diag1, 4 ∉ diag2

Place Queen

[(0,1), (1,3)]

Recurse row=2

2

c=0

All clear: 0 ∉ cols, 2 ∉ diag1, 2 ∉ diag2

Place Queen

[(0,1), (1,3), (2,0)]

Recurse row=3

3

c=2

All clear: 2 ∉ cols, 1 ∉ diag1, 5 ∉ diag2

Place Queen

[(0,1), (1,3), (2,0), (3,2)]

Recurse row=4

4

—

Base case reached (r == 4)

✅ Record Solution 1

[".Q..", "...Q", "Q...", "..Q."]

Backtrack to row=3

3

c=2

Un-choose: remove c=2, r-c=1, r+c=5

Revert .

[(0,1), (1,3), (2,0)]

Try next candidate