Pattern visualizer
Sudoku Solver
There is no way to compute a cell's digit directly; the only information is which digits are already ruled out. So the solver guesses: find the next empty cell, try 1 through 9, and keep the first digit that is absent from the cell's row, column and box. That digit is not a decision, it is a hypothesis. The search recurses to the next empty cell, and if some later cell has no legal digit at all, the hypothesis was wrong: the recursive call returns false, the caller erases its digit and tries the next one. The board is mutated in place and restored on the way back, so a single board carries the whole search. The scan order is left to right, top to bottom, which is why the trace can follow just one row and still show every kind of move. Animated on: The 9x9 board from the statement, 51 cells empty. Shown: row 0 = [5, 3, ., ., 7, ., ., ., .] which must become [5, 3, 4, 6, 7, 8, 9, 1, 2]. Fill every '.' so each row, column and 3x3 box holds 1-9 exactly once..
Try a digit, check three units, undo on a dead end
The board has 51 empty cells. The trace follows row 0 only: [5, 3, ., ., 7, ., ., ., .]. Given digits are fixed; each '.' must take a digit that is absent from its row, its column AND its 3x3 box. There is no formula for this — the only tool is try, check, and undo.
1FUNCTION solve(board)2 FOR r <- 0 TO 83 FOR c <- 0 TO 84 IF board[r][c] != '.' CONTINUE5 FOR d <- 1 TO 96 IF d IN row r OR d IN column c OR d IN box(r, c) CONTINUE7 board[r][c] <- d8 IF solve(board) = TRUE9 RETURN TRUE10 board[r][c] <- '.'11 RETURN FALSE12 RETURN TRUE
← / → step · space play · Home restart