> I implemented branching and backtracking

The solvers they describe are indeed based on depth-first search and backtracking; in Python, the backtracking part involves some copying:

      for v in cands:
          new_board = [row[:] for row in board]
          new_board[i][j] = v
          solved = solve(new_board)

For anyone interested in solving sudokus, I recommend reading Knuth's Dancing Links paper [1] and implement sudoku solver as an exact cover problem. The idea is to completely get rid of copying the state, switching the pointers of doubly linked lists instead, which speeds up the backtracking part a lot.

It's a little bit more code than plain DFS, but much more exciting when it actually works!

[1]: https://arxiv.org/pdf/cs/0011047