Published by Dimitris Kougioumtzis · Updated
Place one queen per row; undo placements that block later rows. Stops at the first solution.
Place one queen per row, reject attacked columns or diagonals, and backtrack as soon as a row has no legal continuation.
When to use N-Queens
Learning constraint search on a small board.
Choosing an alternative
A greedy row choice cannot revise a dead end; backtracking can.
Worked example: input and state changes
Example input
4
These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.
Step 0: Empty chessboard.
State at this checkpoint
{ "values": [ -1, -1, -1, -1 ], "active": [ -1 ], "kind": "queens", "size": 4 }Step 3: Backtrack from row 2.
State at this checkpoint
{ "values": [ 0, -1, -1, -1 ], "active": [ 1 ], "kind": "queens", "size": 4 }Step 7: Backtrack from row 2.
State at this checkpoint
{ "values": [ 0, -1, -1, -1 ], "active": [ 1 ], "kind": "queens", "size": 4 }Step 10: Place queen at row 2, column 4.
State at this checkpoint
{ "values": [ 1, 3, -1, -1 ], "active": [ 1 ], "kind": "queens", "size": 4 }Step 13: Solution: no two queens attack each other.
State at this checkpoint
{ "values": [ 1, 3, 0, 2 ], "active": [ -1 ], "kind": "queens", "size": 4 }
Expected final state
Solution: no two queens attack each other.
Complexity and input bounds
Family: Backtracking. Time complexity: O(n!) search bound.
Space complexity: O(n) board and backtracking state.
Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.
Board size from 4 to 6.
The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.
Common mistakes and limitations
The reference returns one solution, not a count of all solutions; search remains deliberately bounded.
Further reading
For background on algorithm analysis and the JavaScript function interface:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | // board[row] receives the queen column. Returns 1 if solved; n is 4–6 here. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation. function algorithm(board, n) { for (let i = 0; i < n; i++) { board[i] = -1; } let row = 0; while (row >= 0 && row < n) { board[row]++; while (board[row] < n) { let valid = 1; for (let i = 0; i < row; i++) { let diff = board[row] - board[i]; if (diff < 0) { diff = -diff; } if (board[i] == board[row] || diff == row - i) { valid = 0; } } if (valid == 1) { break; } board[row]++; } if (board[row] < n) { row++; } else { board[row] = -1; row--; } } if (row == n) { return 1; } return 0; } |
Source
Knuth studies backtracking, including queens problems. This is a research source for the method, not an attribution of the original chess puzzle.
- Estimating the efficiency of backtrack programs
Donald E. Knuth (1975). Related research paper.