Sudoku solver

[Marko Rauhamaa]

Ian Kelly <ian.g.kelly at gmail.com>:

> On Mon, Mar 30, 2015 at 1:13 AM, Christian Gollwitzer <auriocus at gmx.de>
> wrote:
>> Am 30.03.15 um 08:50 schrieb Ian Kelly:
>>>
>>> On Sun, Mar 29, 2015 at 12:03 PM, Marko Rauhamaa <marko at pacujo.net>
>>> wrote:
>>>>
>>>> Be careful with the benchmark comparisons. Ian's example can be
>>>> solved with the identical algorithm in eight different ways (four
>>>> corners, left or right). I ran the example with my recent Python
>>>> solver and got these times in the eight cases:
>>>>
>>>>      884   s
>>>>        2.5 s
>>>>       13   s
>>>>      499   s
>>>>        5.9 s
>>>>      128   s
>>>>     1360   s
>>>>       36   s
>>>
>>>
>>> That sounds to me like either a transcription error was made to the
>>> puzzle at some point, or there's something wrong with your solver.
>>> The whole point of that example was that it was a puzzle with the
>>> minimum number of clues to specify a unique solution.
>>
>> I think Marko meant, that if he creates symmetrically equivalent
>> puzzles by rotating / mirroring the grid, he gets vastly different
>> execution times, but ends up with the same solution.
>
> That makes sense, but it is true for all puzzles that there are eight
> possible orientations (since it's impossible for a puzzle solution to
> be symmetric), and the wording made it sound like he was describing a
> property specific to the puzzle that I posted.

Thing is, if you are not careful in your comparisons, you might easily
get a good-looking time from one implementation and a lousy time from
another implementation because of a different traversal order.

That is why brute-force sudoku might not be as good for benchmark
testing as BertC was hoping.


Marko