Minimal sudoku solver using DFS in C++

6 April 2026

Sometimes I take the time to sit down and solve some sudoku puzzles. I never got into more advanced techniques, such as X-wings, so as I was staring at a seemingly impossible sudoku passage, I wondered; How hard can it be to write an algorithm for this?

While the internet is full of sudoku solvers, the potential thrill of finding a solution myself made me refrain from looking up known techniques. Admittedly, I did get stuck at one point attempting to traverse all possible paths towards a solution, which is a much larger search space than filling in cells sequentially. A quick look at a video of the backtracking algorithm in action got me back on track, but now I can’t claim to have solved it fully on my own.

Board representation #

The first step is parsing the board from an input string. The board is stored as an array of size 9 * 9 of unsigned char, because we need to store values 0-8 in each cell:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
constexpr static std::size_t BOARD_SIZE = 9 * 9;
constexpr static unsigned char EMPTY_CELL = std::numeric_limits<unsigned char>::max();

using Board = std::array<unsigned char, BOARD_SIZE>;

int to_index(int row, int column) {
  return row * 9 + column;
}

std::pair<int, int> to_row_column(int index) {
  int row = index / 9;
  int column = index % 9;
  return std::make_pair(row, column);
}

Note that we store values 0-8 instead of 1-9, because this simplifies converting from and to a bitmask flag. Empty cells are represented by the maximum value of an unsigned char (255).

Find valid candidates for a cell #

The next step is to determine for a given cell which candidate numbers are still possible for that cell. This is dictated by the following rule:

A number is allowed to occur only once in a 1) row, 2) column and 3) box.

Thus, in order to find the candidates for a given cell, we iterate over all numbers in the row, column and box of a given cell, and remove found numbers from the candidate mask.

The candidate mask is a bitmask with 9 bits. A bit is set to 1 if that numbers can be filled into the cell.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
unsigned short cell_get_candidates(const Board& board, int row, int column) {
  unsigned short mask = 0b111111111; // start with all  bits still possible

  auto remove_from_mask = [](const Board& board, unsigned short& mask, int row, int column) {
    const int index = to_index(row, column);
    const unsigned char value = board[index];
    
    // skip empty cells
    if (value != EMPTY_CELL) { 
      const unsigned short flag = 1u << value;
      mask &= ~flag;
    }
  }

  // iterate over row
  for (int c = 0; c < 9; ++c) {
    remove_from_mask(board, mask, row, c);
  }

  // iterate over column
  for (int r = 0; r < 9; ++r) {
    remove_from_mask(board, mask, r, column);
  }

  // iterate over box
  const int i = row / 3;
  const int j = column / 3;

  for (int r = i * 3; r < (i * 3) + 3; ++r) {
    for (int c = j * 3; c < (j * 3) + 3; ++c) {
      remove_from_mask(board, mask, r, c);
    }
  }

  return mask;
}

Depth-first search (DFS) #

It helps to visualize the problem of solving a sudoku as a tree.

One important observation is that the order in which numbers are filled in does not matter.

For example, it doesn’t matter whether you fill in 1 in cell A and then 3 in cell B, or first 3 in cell B and then 1 in cell A.

Because this order does not matter for getting to the final solution, we can constrain the order in which we solve the cells to be in order from the lowest to the highest cell index: from 0 to 80. This greatly reduces our search space.

Each time we arrive at a cell that is not yet filled in, we call cell_get_candidates to see which numbers can be filled in that cell, and we create a new branch for each of these candidates.

For example, if in cell A there are three possible candidates [0, 3, 5], we create three branches in the tree. For branch 0, 1 and 2 we fill in 0, 3 and 5 in cell A.

Then for each of those branches, we move to the next cell, check their candidates, and create branches from each of these candidates. This is done recursively until we reach a branch that has all numbers filled in. This is the solution to the sudoku.

Sometimes we arrive at a branch that does not have all numbers filled in, but has no more candidate numbers in the current empty cell. That means that branch can be disregarded.

Because a proper sudoku is guaranteed to have only a single solution, we should arrive at this single solution using this approach.

Implementation #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
std::optional<Board> solve(const Board& in) {
  struct StackFrame{
    Board board;
    int cell_index;
  };
  std::stack<StackFrame> stack;
  stack.emplace(in, 0);

  while (!stack.empty()) {
    auto [board, cell_index] = stack.top();
    stack.pop();

    if (cell_index >= 9 * 9) {
      // we've found the solution, all numbers are filled in
      return board;
    }

    const auto [row, column] = to_row_column(cell_index);

    // skip non-empty cells
    if (board[cell_index] != EMPTY_CELL) {
      stack.emplace(board, cell_index + 1);
      continue;
    }

    // otherwise, create a branch for each of the candidate numbers of the current cell
    const unsigned short candidates = cell_get_candidates(board, row, column);
    for (int i = 0; i < 9; ++i) {
      if ((candidates & (1u << i)) != 0) {
        // is candidate, create branch
        Board child = board;
        child[cell_index] = i; // set the value
        stack.emplace(child, cell_index + 1);
      }
    }
  }

  return std::nullopt;
}

The offending sudoku #

I blame the following sudoku for having written this algorithm:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
5..|72.|..9
324|519|.7.
...|.8.|..2
---|---|---
.6.|1..|4..
...|...|...
8..|.4.|26.
---|---|---
...|.3.|7.4
..3|...|...
.91|.6.|.8.

The algorithm arrived at the following solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
586|724|139
324|519|876
179|386|542
---|---|---
962|178|453
437|652|918
815|943|267
---|---|---
658|231|794
743|895|621
291|467|385

In order to reach this final branch, it had to explore 23653 solutions. Luckily, modern computers are incredibly fast, so it blazes through these solutions in less than a second.

Conclusion and further reading material #

I can highly recommend reading about the shortcomings of this approach, as there are possible sudoku’s that make the DFS solution wildly inefficient: https://en.wikipedia.org/wiki/Sudoku_solving_algorithms. The approach is discussed under “backtracking”.

Another avenue that might be interesting is to apply optimization methods such as simulated annealing or genetic algorithms. I’m curious to what extent these are actually more efficient due to the relatively small search space of a sudoku using the discussed DFS approach.