A Sudoku Solver (Backtracking)
Sudoku is an excellent example of backtracking: we fill the empty cells one by one, and as soon as some number causes a conflict, we go back and try the next one. At the end of the lesson there is also an improvement that makes the solver several hundred times faster.
How to learn: type in and run every example, and solve the tasks at the end on your own first; open the hint and the solution only after that. All programs are in C++.
The rules and representing the board
The board is 9 × 9, divided into nine 3 × 3 boxes. The numbers from 1 to 9 have to be written into every row, column and box, each exactly once. We keep the board as a matrix int board[9][9], and an empty cell as 0. The input is 9 lines of 9 digits.
The box that the cell (r, c) belongs to has the number (r / 3) * 3 + c / 3 (from 0 to 8).
The solver
For a fast check we keep three occupancy tables: inRow[r][d], inCol[c][d] and inBox[b][d] – whether the digit d has already been used. The function solve(p) fills the cells in order (p = 0 … 80) and returns true as soon as the board is full.
#include <iostream>
#include <string>
using namespace std;
int board[9][9];
bool inRow[9][10], inCol[9][10], inBox[9][10];
int box(int r, int c) { return (r / 3) * 3 + c / 3; }
void mark(int r, int c, int d, bool value) {
inRow[r][d] = inCol[c][d] = inBox[box(r, c)][d] = value;
}
bool solve(int p) {
if (p == 81) return true; // all the cells are filled
int r = p / 9, c = p % 9;
if (board[r][c] != 0) return solve(p + 1); // the cell is given
for (int d = 1; d <= 9; d++) {
if (inRow[r][d] || inCol[c][d] || inBox[box(r, c)][d]) continue;
board[r][c] = d; mark(r, c, d, true); // choose
if (solve(p + 1)) return true; // explore – a solution has been found
board[r][c] = 0; mark(r, c, d, false); // undo
}
return false; // no number fits
}
int main() {
for (int r = 0; r < 9; r++) {
string row;
cin >> row;
for (int c = 0; c < 9; c++) {
board[r][c] = row[c] - '0';
if (board[r][c] != 0) mark(r, c, board[r][c], true);
}
}
if (!solve(0)) {
cout << "No solution" << endl;
return 0;
}
for (int r = 0; r < 9; r++) {
for (int c = 0; c < 9; c++) cout << board[r][c];
cout << "\n";
}
return 0;
}
Example
Input
530070000
600195000
098000060
800060003
400803001
700020006
060000280
000419005
000080079Output
534678912
672195348
198342567
859761423
426853791
713924856
961537284
287419635
345286179A speed-up: the cell with the fewest options first
The solver above fills the cells in order. For hard sudokus it is much faster to choose, in every step, the empty cell with the fewest allowed numbers: if a cell has only one option, there is no branching, and if it has none – we go back immediately. This heuristic (called "MRV – minimum remaining values" in the literature) shrinks the search tree by several orders of magnitude.
// Instead of "the next cell in order", in the function solve() we choose the best cell:
int bestR = -1, bestC = -1, fewest = 10;
for (int r = 0; r < 9; r++)
for (int c = 0; c < 9; c++) {
if (board[r][c] != 0) continue;
int options = 0;
for (int d = 1; d <= 9; d++)
if (!inRow[r][d] && !inCol[c][d] && !inBox[box(r, c)][d]) options++;
if (options < fewest) { fewest = options; bestR = r; bestC = c; }
}
if (bestR == -1) return true; // there are no empty cells – solved
if (fewest == 0) return false; // a dead end
// ... the rest is the same as before, but for the cell (bestR, bestC)
- Before the recursive call update both the board and the occupancy tables, and after an unsuccessful call restore both.
- A function that returns
booland exits immediately when it finds a solution is much faster than one that looks for all the solutions. - For a 3 × 3 box use integer division:
r / 3andc / 3. - Always check an input without a solution too – the program should report it, not run endlessly.
Check your knowledge
Open the quiz
Mini quiz: Sudoku
1. What is the number of the box of the cell (4, 7) (indexes from 0)?
2. What should the function solve() do when no number fits a cell?
