How to Code a Sudoku Solver With Backtracking

Why backtracking fits Sudoku

A Sudoku grid has 81 cells, and each empty cell can hold a symbol from 1 to 9. The rules are simple to verify: no repeat in a row, no repeat in a column, and no repeat in a 3 by 3 box. That mix of a small choice set and a fast legality test is exactly what backtracking loves, because a bad partial board can be rejected long before the grid is full. Represent the board as a 9 by 9 array of integers where 0 means empty, and index a cell as grid[r][c]. To make the legality check fast, keep three sets of used symbols, one per row, one per column, and one per box, where the box index is (r / 3) * 3 + (c / 3). With bitmasks, testing whether a symbol is allowed becomes a single bitwise operation, and marking or unmarking it is just as cheap. Getting this representation right is most of the work when you code a sudoku solver.

How to code a sudoku solver: the core loop

1. Find the next empty cell. If there is none, the board is solved, so return true.
2. For each symbol from 1 to 9, check whether it is legal using the row, column, and box records.
3. If it is legal, place it and mark it in the row, column, and box.
4. Recurse into the rest of the board.
5. If the recursive call returns true, propagate true upward and stop.
6. If every symbol fails, undo the last placement and return false so the caller can backtrack.

That short loop is the whole engine, and it is why you can code a sudoku solver in only a screen of code. The recursion depth never exceeds the number of empty cells, and every path ends either in a full valid grid or a rejected branch. Because you undo each failed choice, the same arrays are reused instead of copying the board at every step, which keeps memory flat. A naive version always fills the first empty cell it finds, but a much faster one uses the minimum remaining values heuristic: scan for the empty cell with the fewest legal symbols and fill that first. If a cell has only one candidate, you commit with no risk; if a cell has zero candidates, you fail immediately and prune a dead branch early. That single change can cut the search for hard puzzles dramatically and costs only a few extra lines once you already track candidates. A common bug is forgetting to clear a bitmask on backtrack, which silently blocks symbols later in the search, so always pair every mark with a matching unmark.

Testing that your solver is correct

• Feed it a known easy puzzle and confirm the output matches the published answer.
• Feed it an already solved grid and confirm it returns that grid unchanged.
• Feed it a puzzle with two identical symbols in one row and confirm it reports no solution.
• Count solutions by not stopping at the first answer; a proper puzzle should have exactly one.

From numbers to shapes

Sudoku does not care what the nine symbols are, because the solver works on internal indices from 1 to 9. Replace those numbers with nine shapes and the code is identical, which is the idea behind Shapedoku: nine glowing shapes stand in for the digits, and the same backtracking logic that solves a numeric grid solves a shape grid. A working solver is a reusable tool. You can use it to confirm a puzzle you invented has a unique answer, to grade difficulty by how much backtracking it needs, or as the backbone of a generator. The lesson worth keeping is that a clear board representation, a fast legality test, and disciplined undo are enough to solve every valid Sudoku. If you want to see a polished version, the free solver at shapedoku.com uses this same family of techniques, and you can play the shape version at app.shapedoku.com. Once you can code a sudoku solver from scratch, the rest of Sudoku software feels approachable.