The New Sudoku Players' Forum

[singaurav]

Hi all,

I am Gaurav and I have written a Sudoku Solver https://github.com/singaurav/fast-sudoku-solver in C++. The solver

Is decently fast: Can solve and assert unique solutions for Gordon 17 clue puzzles collection at the rate of 800-900 puzzles/sec on my 2 GHz Intel I7.

Uses Pure Backtracking: The solver does not use any traditional techniques like singles, intersections, fish, wings etc. Although I believe that these can make the solver even faster. The backtracking itself is unlike others i.e. it occurs over digits rather than squares.

I deliberately chose C++ over C; have attempted to write human friendly code and did not delve too much on low level optimizations.

I ask the Sudoku programming enthusiasts and the experienced to kindly take a look and offer comments, suggestions, ideas for improvements etc. Contributors are also welcome.

[JasonLion]

Welcome to the Sudoku Players Forum!

Only the very simplest solving techniques can help make a solver faster. Using singles can help dramatically and locked candidates will give you some additional improvement. But no one has been able to find a way to use any of the more complex techniques to speed things up. That is not to say that you can't do anything interesting with more complex techniques. It is only when speed is your primary criteria that they don't help.

The current state of the art in fast solvers is around 250,000 puzzles/second (see here for details). So your code has plenty of room for improvement, depending on what your goals are.

It would be nice if you gave us a brief overview of the data structures you are using.

[singaurav]

Hi Jason,

Here is the idea behind my program:
Consider a solved Sudoku grid. Let's strip all numbers from this grid except the digit 1. The resulting grid has the digit 1 exactly once each in one row, column and 3x3 box. Let's call this a state of the digit 1. There are 6^6 = 46656 such states for each digit. Now, two states may be conflicting or not depending on whether they share one or more squares. Theoretically, one could generate all possible solved Sudoku grids by finding nine mutually non-conflicting states from the 46656 states and assigning each state a digit. Interestingly if you find 8 non-conflicting states and place them in a grid, the ninth state is appears automatically.
Let me now describe the actual algorithm.
1. Using the clues, i restrict the possible states for each digit.
2. Now, select the digit with the least possible States.
3. Chose one state from the list arbitrarily, remove the conflicting states from the remaining digits and go to step 2 until solved.

I use three 32 bit integers to represent state and a linked list for representing a set of possible states for a digit.

My goal is speed but not at the expense of readability and maintainability. Furthermore, i want to know: if properly implemented, how does the above approach to backtracking compare against the traditional square by square backtracking.

Please let me know if you have any ideas for improvement.

[JasonLion]

Ah, a brute force approach based on templating. Very few people have pursued that approach. A template corresponds to one of the 46656 possible states for each digit

No one has yet developed a solver based on templates which is remotely competitive in speed with other approaches. That doesn't mean it can't be done. As far as I am aware there has been very little work in this area, and there may well be optimizations that have not been explored. Abstractly, this approach should be roughly the same amount of work as the other approaches. The key question is: can you develop an internal representation that is as efficient to manipulate as the internal representations used for the other approaches.

One of the challenges is that the lists of currently valid templates takes a fair bit of memory and is constantly changing as you recurse. That means you are manipulating a lot of memory at each step, clearly not the most efficient thing. The current cell by cell brute force solvers change just a few words of memory at each step.

Another issue is the percentage of the search tree that you can eliminate at each recursion. For your approach that corresponds to number of potential templates eliminated at each recursion. If there are say 200 possible templates for a digit, your current approach only eliminates one of them at a time or 0.5% of the possible solutions. It is potentially much more efficient if you could somehow eliminate a number of them at one time, ideally something approaching 50% of the possible solutions per recursion. The current cell by cell brute force solvers are able to eliminate a large portion of the search tree at each recursion, which is one of the keys to their efficiency.

[singaurav]

I incorporated naked and hidden singles before the brute force search and compared performance with JSolve and here are the results:
TestCase: 10 test cases with Top 1465 Sudokus * 64 = 93760 puzzles each
JSolve : 27765 puzzles/sec
My solver: 1177 puzzles/sec

Looks like my solver is about 25 times slower than JSolve. Not sure if that qualifies for:

No one has yet developed a solver based on templates which is remotely competitive in speed with other approaches.

Regarding considering branch factor as a measure of efficiency as you mention,

Another issue is the percentage of the search tree that you can eliminate at each recursion. For your approach that corresponds to number of potential templates eliminated at each recursion. If there are say 200 possible templates for a digit, your current approach only eliminates one of them at a time or 0.5% of the possible solutions. It is potentially much more efficient if you could somehow eliminate a number of them at one time, ideally something approaching 50% of the possible solutions per recursion. The current cell by cell brute force solvers are able to eliminate a large portion of the search tree at each recursion, which is one of the keys to their efficiency.

I think the number of nodes searched is a better indicator, because if your search tree has less branching factor but more depth, it is equivalent to a shallow tree with large branching factor.

I am now planning to incorporate some sort of pruning technique to make the brute force search faster. Unlike JSolve where brute force search is augmented with singles and intersection strategies, i can't think of a way to leverage these in between my brute force search since number of templates to manage with each step is high. It has to be some other strategy.

Any suggestions/comments/questions are welcome. Posting the source code link again for quick reference: https://github.com/singaurav/fast-sudoku-solver.