On 07/02/2012 04:38 AM, David Bernier wrote:
> On 07/01/2012 09:45 PM, Richard Tobin wrote:
>> A small fraction of a second, in fact, using simple backtracking search.
>>
>> -- Richard
>
> Longest solving time so far (taking thousands of copies of the same
> problem):
>
> 3.6 milliseconds per solution (all identical).
>
> IvoC's Sudoku:
>
> ======================
> ..1 ..4 ...
> ... .6. 3.5
> ... 9.. ...
>
>
> 8.. ... 7.3
> ... ... .28
> 5.. .7. 6..
>
>
> 3.. .8. ..6
> ..9 2.. ...
> .4. ..1 ...
> =======================
>
>
> 10,000 solved in 36,303 ms .
>
> One solved per 3.6 millisecond .
>
> Longest so far ...
[...]
Andrew Stuart (a Database and Web Applications Developer) is more
knowledgeable than most about hard-to-solve sudoku puzzles.
I refer to his recent news column comparing the Finnish mathematician's
sudoku (which appeared in the Daily Telegraph, etc.) to puzzles rated
"unsolvable" published over the years:
<
http://www.sudokuwiki.org/Arto_Inkala_Sudoku > .
Stuart describes there a rating heuristic for hard sudokus.
Andrew Stuart wrote in his news column:
"David Filmer is the hands down winner with these two puzzles:"
These sudokus by David Filmer are 1st and 2nd, with
Arto Inkala's recent (2012) puzzle coming in 3rd place.
I tested the 1st rated hard puzzle by David Filmer,
dubbed "Unsolvable #28", archived here:
<
http://www.sudokuwiki.org/Weekly_Sudoku.asp?puz=28 > .
===
I note that Filmer's "Unsolvable #28" has 22 clues, and yet
some true sudokus (unique solution) have as few as
17 clues.
I have tested (solved by program) some 17-clue sudokus.
To get more accurate timings, I always create an input file
with 100 or more copies of the puzzle to be tested for
timing.
"Unsolvable #28" takes the solver I downloaded and compiled
(written in the C programming language)
26 to 27 milliseconds to solve.
IvoC's Sudoku mentioned in my last post took only
3.6 milliseconds to solve, with the same timing methodology.
Screen copy about solving #28: (the "1K" is misleading... )
=========================================================================
[Test]$ time ./a.out < unsnum28x1K.txt > outSolnUnsnum28a.txt
real 0m3.054s
user 0m2.717s
sys 0m0.001s
[Test]$ wc unsnum28x1K.txt // the "1K" is misleading
100 100 8200 unsnum28x1K.txt // 100 lines; one puzzle <==> 1 line
=========================================================================
In English, it took 2.7 seconds to solve "Unsolvable #28" 100 times over.
David Bernier