Sudoku solver update

I spent some time considering how people solve Sudoku and it gave me a few ideas on how to improve my original Sudoku solver‘s performance. I hypothesized that finding naked pairs and lines would save more calculation than it would cost.

Naked pairs

Naked pairs are quite easy to calculate and use. The idea behind it is that, on a row or column, if two squares have the same two possible values and no other, then no other square on that row or column could be one of these two values.

This is simple to comprehend. If the either of the two squares is one of the values, then the other square is the other value since they are both exclusive to one another. And, independently of which square has which value, no other square can be either of these two values on that row or column so we can remove them from the available values.

This also applies to sections, but it is more costly to calculate it for a section so I skipped that.

Lines

Lines are a little more generic, but cost more to calculate. We start by analyzing rows and column to find on which of the three sections a certain value is along this “line”.

If it can only be in one section along that line, then we can be certain that the value is not in any other line in that section.

In the following example, on the second column, the value “1″ can only be in the last section. This means it is necessarily in that column for the last section, so we can remove any other “1″ from that section.

On the other had, if it can be in two sections, then we still check one more thing. If it can only be in the two specific sections and it can only be in these same two specific sections in another line (in the same three lines block), then the third line necessarily has the value from the remaining section, so we can remove that value from the other line.

In this example, the values “1″, “8″ and “9″ can only be in the second and third sections of the second and third columns. This means that neither of these three values can be in the first column.

Conclusion

I also reordered the rules and eliminated a few of the previous rules that became too costly to run. In total, these improvements allowed me to cut the execution time by roughly 75% in regards of my original version.

I also made a JavaScript version which I will post on this site in the next few days.

The code

Here is the source code (zipped: 4KB).

9 Responses to Sudoku solver update

  1. Your solution is really great!
    I ported it for a programming contest to Basic4Android. I tried to optimize it and found only very few things to make it faster. My end result was perhaps 10% to 20% faster than the one to one port of your source.

    You can find my solution here: http://www.basic4ppc.com/forum/basic4android-updates-questions/11834-sudoku-solver-contest-we-have-winner.html
    Here is a small description of how I have done it: http://www.basic4ppc.com/forum/basic4android-getting-started-tutorials/12099-how-write-sudoku-solver.html#post67856

    Of course with the help of your algorithm I was the winner of the contest. :-)

  2. Amazing! Thanks for letting me know. It makes a great subject to brag about ;)

  3. About naked pair you can do the same for naked triple
    exemple
    if possible value are only “123″ “123″ “123″ in 3 different square of the same line/colum/section you can remove 1 2 3 to the other square because 1 2 3 will be forced in this 3 square.
    that work also for
    “12″ “123″ “123″ (can remove 1 2 3)
    or
    “12″ “123″ “1234″ “1234″ (can remove 1 2 3 4)
    or
    “12″ “23″ “31″ (can remove 1 2 3)
    or etc…

  4. Nice work. Why don’t you port it to C/C++ and compare the speed improvement?

  5. Great solution!
    I used it to create an open source Sudoku Solver for Android which loads puzzles in JSON format from a web server.

    Source code available here:
    git@github.com:bizz84/SudokuSolver.git

    Android app available here:
    https://play.google.com/store/apps/details?id=com.musevisions.android.SudokuSolver

    Andrea

  6. Hi
    How can I run the program? I get the error:

    Vous devez fournir le chemin du fichier contenant le probl�me.

    Do I have to give it the
    answer.txt file
    as in input in the run configurations?

    I basically downloaded the SudokuSolver folder and also have the Solver folder in the sam e project in eclipse.

    Any help would be appreciated!! : )

  7. What a great article! I’m a sudoku lover too. Recently, I’m trying to write a sudoku solver. But my solver is slower than yours. However, I have a question that if my puzzle has more than one solution, I find your solver can’t give me the all solutions. For example:
    700000501
    203107000
    061000000
    800060000
    400500003
    005902800
    900041060
    000000140
    040800000
    This puzzle have 343 solutions, but your solver only give me one solution. I want to know how can I get all the solutions through your solver?

    Thanks advanced!

  8. Hi, interesting post. Are you familiar with Constraint Satisfaction programming (CSP)? Your considerations on backtracking vs. rule enforcement fits nicely into the CSP-theory. Simple backtracking are called Look Ahead (LA) and techniques that maintains consistency among all constraints and variables are called Maintaining Arc Consistency (MAC). On hard problems MAC is considered superior to LA. But I’m not sure that Sudoko is hard in that sense.

    Anyway, great read. My generic MAC-solver in java solves hard sudokos in 300 ms, using “Alldifferent” constraints. Your approach is a lot faster.

  9. @echofish : Time would be the main reason! But if you or anyone else wants to port it to other languages, I will gladly add a link to your article.

    @M : It takes the path to the sudoku file in parameter to the program. You may add it in Eclipse’s run configuration or simply run it from command line.

    @Michael Leo : The sudoku solver stops solving as soon as it finds one solution. It should be pretty easy to tweak it to find more but it would be very slow at it. The big advantage of my solver is that it uses logic rules to deduce a valid state from the problem’s constraints. Without the constraints, more valid states are possible but the rules also become inefficient.

    It you want to solve sudokus with multiple solutions efficiently, your best bet is still a normal backtracking brute force algorithm.

    @Søren : I must admit I am not that well versed in the mathematical theories behind algorithmic problem solving. I did some research, mostly to solve specific problems and I find the subject fascinating, but most of my work or side projects relate to parallel and distributed algorithms and architectures.

    In the case of improving the performance of your backtracking algorithm, you may want to try Donald Knuth’s Dancing Links method.

Leave a Reply