Problem context and objectives
Mission briefing
Puzzle systems engineer · A game mechanic is behaving incorrectly
Guard columns and both diagonal families: The Queen Citadel.
Brute force may pass the demo but fail when the world fills with players.
How you win
- 1Recognize when N-Queens backtracking matches the clues
- 2Keep this true after every move: the partial board has one queen per completed row and no shared column or diagonal
- 3Reach the result within O(n!) search with constant-time conflict checks
Rules and pressure
- Target cost: O(n!) search with constant-time conflict checks
- State rule: the partial board has one queen per completed row and no shared column or diagonal
Lesson 1 of 3
Live algorithm trace
N-Queens backtracking
Complete execution1 of 5
.Q..
row
...Q
Q...
..Q.
cols
diags
The first row may try every column.
1
search(row)2
if row == n: record board3
for each column4
skip occupied column or diagonal5
place queen and mark three sets6
recurse, then remove queen and marksrow = 0available = 0,1,2,3
Truth to preserve / Cost target
Truth to preserve
the partial board has one queen per completed row and no shared column or diagonal
Cost target
O(n!) search with constant-time conflict checks
Place one queen per row. Sets for columns, row-minus-column diagonals, and row-plus-column diagonals reject every attacked square in constant time.
Your call · What should guide every step of this algorithm?