BacktrackingRecursion & Backtracking

Sudoku Solver (4×4)

Fill empty cells one by one with digits that do not conflict in their row, column, or 3×3 box, backtracking on dead ends.

Learn Sudoku Solver →
1
4
1
3
4
2
1/36Solve the 4×4 sudoku by filling empty cells left-to-right, top-to-bottom, trying digits 1..4 and undoing any choice that leads to a dead end.
Given cluePlaced by searchCell being triedConflicting cell
PseudocodeLearn Sudoku Solver →
1solve():
2  find next empty cell (r, c); if none: return true
3  for v in 1 .. N:
4    if valid(r, c, v):
5      board[r][c] = v
6      if solve(): return true
7      board[r][c] = 0        // backtrack
8  return false
Variables
placements0
backtracks0
Complexity
worst O(9^m)
space O(m)
Speed