An answer to this question on Stack Overflow.

Question

I've recently been working on a sudoku game in c++. I've made a graphic version of it using SFML and it works just fine. However, I need to implement an algorithm which will solve the sudoku, whilst not being a brute-force algorithm (so backtracking doesn't work for me ;/). I've read about many ways to solve it and I've come across different algorithm names (such as Dancing Links), as well as algorithms which only describe how the search works without giving any specific pieces of information on how to implement it in c++. (i.e. assigning a table or a list of possible numbers to each single "bucket" and searching for the solution, also someone mentioned so-called A* algorithm?)

So here is my question, what kind of algorithm is fairly easy to implement and is not the backtracking one? And where to find specific pieces of information on how to use it in c++? Thanks in advance. My program works on a two-dimensional array, but I could somehow make the buckets into structures if needed.

Answer

Peter Norvig recommends using process of elimination (constraint propagation) followed by search. His article here provides a very thorough explanation.

In constraint propagation you use the following strategy:

(1) If a square has only one possible value, then eliminate that value from the square's peers. 
(2) If a unit has only one possible place for a value, then put the value there.

Now, it's easy to find in O(N) time the initially-filled squares in the puzzle. Put them all in a queue. If their neighbours, after propagating the constraint, have only a single value, add that to the queue. Repeat until the queue is empty.

The puzzle is now either solved or no further progress can be made by propagating constraints.

If the puzzle is not solved, you could either use a fancier algorithm or, as Norvig recommends, employ backtracking. Since the backtracking is being performed on a typically-small subset of the puzzle space, you're not using brute-force.