A PC Could Do A Sudoku In Minutes

[Bret Cahill]

http://www.telegraph.co.uk/science/science-news/9360022/Worlds-hardest-sudoku-the-answer.html

[DonH]

"Bret Cahill" <Bret_E...@yahoo.com> wrote in message
news:28cae10f-0bd1-4e40...@l6g2000pbi.googlegroups.com...
> http://www.telegraph.co.uk/science/science-news/9360022/Worlds-hardest-sudoku-the-answer.html

# Yes, a computer can number-crunch much faster than any of us, and can be
programmed to consider all possible options - using clues provided.
I assume that it is minimal clues which determines degree of difficulty;
giving a unique answer.
I find it hard enough filling in a blank sudoku, let alone bother
solving one.

[David Bernier]

The solver at http://sudoku-solutions.com/ rates the "Everest" sudoku
from the past few days at HARD.

Their solver can give hints and show the steps to the solution.

Can there be a sudoku that their solver would take a minute
or more to solve? what about 5 minutes? 15 minutes? etc.

David Bernier

[Richard Tobin]

A small fraction of a second, in fact, using simple backtracking search.

-- Richard

[Tim Little]

On 2012-07-01, David Bernier <davi...@videotron.ca> wrote:
> Can there be a sudoku that their solver would take a minute
> or more to solve? what about 5 minutes? 15 minutes? etc.

Not for the standard 9x9 size. For larger ones, sure. Solving
sudokus of arbitrary size is NP-complete.


--
Tim

[David Bernier]

On 07/01/2012 09:45 PM, Richard Tobin wrote:
> A small fraction of a second, in fact, using simple backtracking search.
>
> -- Richard

Thanks to you and Tim Little.

I got a strange message from the on-line solver:

[ http://sudoku-solutions.com/ ]


"Fatal error: Maximum execution time of 30 seconds
exceeded in
/home/web28/public_html/includes/grid.php
on line 902"



That's after entering a 17-clue puzzle and asking to ckeck for
uniqueness of solution. ---> "Unique Check"

What's strange is that the solver rated the 17-clue sudoku
copied below as "Intermediate"



4.. ... 8.5
.3. ... ...
... 7.. ...



.2. ... .6.
... .8. 4..
... .1. ...



... 6.3 .7.
5.. 2.. ...
1.4 ... ...




Now, if the solver can solve it, as it claimed it did,
how can it not know that the solution is unique?
(or at least couldn't show uniqueness in 30 seconds?)
Very strange ...


Puzzle taken (#1 in list)
from
"b) 95 hardest sudokus sorted by rating: top95
(they are here mainly for historical reasons)" of

Guenter Stertenbrink's (I think) page:

http://magictour.free.fr/sudoku.htm

===

There's a preprint
"17 clues is the minimum, and no true 16-clue sudoku" [paraphrased]

by Gary McGuire, Bastian Tugemann and Gilles Civario

< http://arxiv.org/abs/1201.0749v1 >

David Bernier


P.S. I haven't my own solver, so I can't assess difficulty
independepently of sudoku-solutions.com

[Bret Cahill]

> A small fraction of a second, in fact, using simple backtracking search.

Some of us cannot afford to upgrade from our 8080As.


Bret Cahill

[David Bernier]

Previously, I mentioned http://www.sudoku-solutions.com/ ,
which couldn't reply to the "Unique Check" question in less
than 30 seconds.

I took a list of "top 95" sudokus from :
http://magictour.free.fr/top95

by Guenter Stertenbrink.

Then, I used the free C source code solver
by Attractive Chaos <at...or@........u.>

< https://raw.github.com/attractivechaos/plb/master/sudoku/sudoku_v1.c >

===

The 95 puzzles were in the same directory, 1 per line, as the
compiled C solver.

====
[david@localhost Sudoku]$ time ./solver.out < TOPpuzzles95.txt >
outsoln95.txt

real 0m0.083s
user 0m0.080s
sys 0m0.001s


I haven't checked the output for accuracy, in outsoln95.txt, but I sort
of believe it.

<100 milliseconds for 95 hard sudokus, 9x9 . Hmmph !


David

[Tim Little]

On 2012-07-02, David Bernier <davi...@videotron.ca> wrote:
> "Fatal error: Maximum execution time of 30 seconds exceeded in
> /home/web28/public_html/includes/grid.php on line 902"

Given that it's written in PHP, it wouldn't at all surprise me that
it's slow.

> Now, if the solver can solve it, as it claimed it did,
> how can it not know that the solution is unique?
> (or at least couldn't show uniqueness in 30 seconds?)

Sounds like poor programming. Verifying uniqueness of a given
standard sudoku should take milliseconds at most.


--
Tim

[David Bernier]

On 07/01/2012 10:05 PM, Tim Little wrote:

[david@localhost Sudoku]$ time ./solver.out < n10k > outsolnN10K

real 0m23.771s
user 0m23.063s
sys 0m0.008s

23,771 milliseconds for 10,000 copies of "Everest" (rated 11 stars).

About 2.4 milliseconds per each solution (all identical) ...


David

[David Bernier]

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 ...

David


[david@localhost Sudoku]$ time ./solver.out < new10kt > outsolnNew10KT

real 0m36.303s
user 0m34.216s
sys 0m0.022s

[Peter Webb]

"Tim Little" <t...@little-possums.net> wrote in message
news:slrnjv20f...@soprano.little-possums.net...

A correct Sudoku has a unique answer.

How do they *know* it is unique, without a brute force computer search?

(This has always bugged me about Sudoku).

[Richard Tobin]

In article <jsuavk$d0t$1...@news.albasani.net>,

Peter Webb <r.peter...@gmail.com> wrote:

>How do they *know* it is unique, without a brute force computer search?

By performing a non-brute-force human search.

-- Richard

[David Bernier]

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

[Tonico]

On the other hand, even the most stupid man on Earth (say, a
politician or a reality program participant) can unplug ANY computer
and render it useless...

Tonio

[John Morriss]

On Wednesday, July 4, 2012 9:58:46 AM UTC-4, Tonico wrote:
>
>
> On the other hand, even the most stupid man on Earth (say, a
> politician or a reality program participant) can unplug ANY computer
> and render it useless...
>
> Tonio

I thought politicians WERE participating in a reality program: forming and reforming alliance and cliques, getting voted off the island... oops, government, etc...

[1treePetrifiedForestLane]

wow, no 16-clue Sudoku; now,
for a little numbertheoretic proof?

[1treePetrifiedForestLane]

one-by-one ... wait; zero-by-zero, undefined?

two-by-two, special case for 'le theoreme prochaine du Fermatttt.'