Algorithm Code
Time: O(N!) | Space: O(N)
1function solveNQueens(n) {
2 board = empty nxn board
3 return solve(board, 0, n)
4}
5
6function solve(board, row, n) {
7 if row == n: return true
8 for col = 0 to n-1:
9 if isSafe(board, row, col):
10 board[row][col] = Queen
11 if solve(board, row+1, n): return true
12 board[row][col] = Empty
13 return false
14}Algorithm Steps
Step 1 of 58
1
Start N-Queens
2
Trying (0, 0)
3
Placed queen at (0, 0)
4
Trying (1, 0)
5
Position (1, 0) is not safe
6
Trying (1, 1)
7
Position (1, 1) is not safe
8
Trying (1, 2)
9
Placed queen at (1, 2)
10
Trying (2, 0)
11
Position (2, 0) is not safe
12
Trying (2, 1)
13
Position (2, 1) is not safe
14
Trying (2, 2)
15
Position (2, 2) is not safe
16
Trying (2, 3)
17
Position (2, 3) is not safe
18
Backtrack: removed queen from (1, 2)
19
Trying (1, 3)
20
Placed queen at (1, 3)
21
Trying (2, 0)
22
Position (2, 0) is not safe
23
Trying (2, 1)
24
Placed queen at (2, 1)
25
Trying (3, 0)
26
Position (3, 0) is not safe
27
Trying (3, 1)
28
Position (3, 1) is not safe
29
Trying (3, 2)
30
Position (3, 2) is not safe
31
Trying (3, 3)
32
Position (3, 3) is not safe
33
Backtrack: removed queen from (2, 1)
34
Trying (2, 2)
35
Position (2, 2) is not safe
36
Trying (2, 3)
37
Position (2, 3) is not safe
38
Backtrack: removed queen from (1, 3)
39
Backtrack: removed queen from (0, 0)
40
Trying (0, 1)
41
Placed queen at (0, 1)
42
Trying (1, 0)
43
Position (1, 0) is not safe
44
Trying (1, 1)
45
Position (1, 1) is not safe
46
Trying (1, 2)
47
Position (1, 2) is not safe
48
Trying (1, 3)
49
Placed queen at (1, 3)
50
Trying (2, 0)
51
Placed queen at (2, 0)
52
Trying (3, 0)
53
Position (3, 0) is not safe
54
Trying (3, 1)
55
Position (3, 1) is not safe
56
Trying (3, 2)
57
Placed queen at (3, 2)
58
Solution found!
4-Queens Problem
Start N-Queens
Current try
Under attack
♛Queen
Step 0 of 570%
0.25x4x