Sudoku Solver
2026-03-21
Elliot Lichtman did a great job in explaining algorithms through puzzles and strategy games in his book The Computer Always Wins [1]. He tells you not only the how but also the why, and he does it in a fun way!
In one of the chapters, he says recursion is a good choice to solve certain kind of puzzle like sudoku. One of the reasons is that the states are inherently kept in the recursive call flow, hence no need for an explicit state management structure.
I coded a sudoku solver [2] in the Go programming language loosely based on his algorithm. Below is the key routine. Notice solveSudoku() is recursively calling itself to solve the puzzle.
func solveSudoku() bool {
iterations++
depth++
if flagGraph {
fmt.Printf("%s\n", strings.Repeat("*", depth))
}
if depth > maxdepth {
maxdepth = depth
}
for i := 0; i < 9; i++ {
for j := 0; j < 9; j++ {
if board[i][j] == 0 {
for num := 1; num <= 9; num++ {
if isValid(i, j, num) {
board[i][j] = num
if solveSudoku() {
depth--
return true
}
board[i][j] = 0
}
}
depth--
return false
}
}
}
depth--
return true
}
If you have the Go toolchain installed, you can install the sudoku solver and play around with it:
$ go install github.com/davidfung/sudoku@latest