Backtracking
Decision Tree Visualizer
Step through choose, explore, reject, and undo moments while the path, board state, result count, time, and space complexity update.
O(4^empty) time / O(empty) space
Board
1,1
1
1,2
-
1,3
-
1,4
4
2,1
-
2,2
4
2,3
1
2,4
-
3,1
-
3,2
1
3,3
2
3,4
-
4,1
2
4,2
-
4,3
-
4,4
1
Current Path
14411221
Results
No result yet
Results
0
Time
O(4^empty)
Space
O(empty)
Step Note
Solve a compact 4 x 4 Sudoku board.
function solveSudoku(board: number[][]) {
const empty = findEmpty(board)
if (!empty) return true
for (const value of [1, 2, 3, 4]) {
if (!isSafe(board, empty, value)) continue
board[empty.row][empty.col] = value
if (solveSudoku(board)) return true
board[empty.row][empty.col] = 0
}
return false
}