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 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 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.
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.
Here is the source code (zipped: 4KB).