Solving N-Queens With Backtracking
0 tries · 0 placed · 0 backtracks
- Queen
- Being tried
- Clash
- Attacked
- Solved
1/1201
Place 8 queens on a 8×8 board so that no two share a row, a column or a diagonal. One queen per row, starting at the top.
Settings
N-Queens
- 1
solve(row): - 2
if row == n: return true - 3
for col in 0..n-1: - 4
if safe(row, col): - 5
queen[row] = col - 6
if solve(row + 1): return true - 7
queen[row] = null // backtrack - 8
return false
How Big the Board Gets
| Board | Solutions | Tries to the first |
|---|---|---|
| 4×4 | 2 | 26 |
| 5×5 | 10 | 15 |
| 6×6 | 4 | 171 |
| 7×7 | 40 | 42 |
| 8×8 | 92 | 876 |
| 9×9 | 352 | 333 |
| 10×10 | 724 | 975 |
Scroll the table sideways for the rest of the columns.
A try is one square checked with safe(). There are 16,777,216 ways to put one queen in each row of an 8×8 board. Backtracking finds a solution after 876 tries because it drops a partial board the moment two queens clash.