what is the hardest known suduko ?

Bob Hanson · Posted: Sat Dec 03, 2005 9:11 pm Post subject:

Sudoku Assistant now solves these two puzzles. Very interesting ones.

OK, the deal here is that the "bifurcation" stuff amounts to trial-and-error depth, because it amounts to looking for singles again -- a new cycle, right?.

So I just allowed the hypothesis/proof engine to go ahead and look also for locked candidates, subsets, and grids (X-wings, swordfish, etc.) These last are all from the same function, so that wasn't any great work. -- Essentially do a full 2nd round of analysis short of figuring out a whole new set of chain calculation and hypothesis.

This cracks both of these puzzles in short order.

7.. ... 4..
.2. .7. .8.
..3 ..8 ..9

... 5.. 3..
.6. .2. .9.
..1 ..7 ..6

... 3.. 9..
.3. .4. .6.
..9 ..1 .35

Done! (52 steps) MP+

798 635 421
126 974 583
453 218 679

972 586 314
564 123 897
381 497 256

617 352 948
835 749 162
249 861 735

7.8 ... 3..
... 2.1 ...
5.. ... ...

.4. ... .26
3.. .8. ...
... 1.. .9.

.9. 6.. ..4
... .7. 5..
... ... ...

Done! (58 steps) WMP++

728 946 315
934 251 678
516 738 249

147 593 826
369 482 157
852 167 493

293 615 784
481 379 562
675 824 931

MP+ means "3d medusa and logical proof with a bit of depth (through locked candidates)"

WMP++ means "X-wing or swordfish and medusa and logical proof with depth (through subsets and X-wings/swordfish).

Obviously this story will continue -- harder Sudoku will be found. But so far I'd say these take the cake.
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr

dukuso · Posted: Sun Dec 04, 2005 1:28 am Post subject:

when you just increase the level of lookahead, then, why is it
better to include locked candidates, x-wing etc. at all,
versus just using singles and one extra level of lookahead ?

Bob Hanson · Posted: Sun Dec 04, 2005 9:09 am Post subject:

Are you asking why not just use singles entirely, and keep on branching?

The answer for me is that I didn't set up Sudoku Assistant to be fully recursive in terms of depth, and it was so easy to tap into what I already had. Doing the "bifurcation" -- looking for the next level of singles -- is essentially starting over in a new cycle.

I'm not claiming this solves all possible Sudoku -- I realize that would require full depth trial and error (the NP Complete issue, I think). But it's interesting that even these super-fiendish ones crack in just 50 steps or so just with this added bit of depth.

Actually, I believe that looking for n-tuples and X-wings amounts to adding an element of depth. These can't be found with simple forced chain logic. You have to say, "If X is true and Y is true, then ...," and that's depth.

But it's an interesting question. What I observe is that the solution goes quite rapidly, and since these functions add minimal effort to the solution, it seems to me they pay off.

Once you are in trial and error, I don't see why NOT to look for these things. The faster we can get to a disproof, the better, of course. So I'm sure just using singles but allowing full depth would do the job as well -- and probably faster. (My understanding is that that's what the dancing links algorithm does, but I can't say I understand exactly what's going on there. Knuth refers to it as depth backtracking, so I presume that all it's doing is straight singles. And I'm told that dancing links can be extremely slow with certain "renegade" Sudoku puzzles.)
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr

dukuso · Posted: Sun Dec 04, 2005 10:26 am Post subject:

>Are you asking why not just use singles entirely, and keep on branching?

yes

>The answer for me is that I didn't set up Sudoku Assistant to be
>fully recursive in terms of depth, and it was so easy to tap into
>what I already had. Doing the "bifurcation" -- looking for the
>next level of singles -- is essentially starting over in a new cycle.
>
>I'm not claiming this solves all possible Sudoku -- I realize
>that would require full depth trial and error (the NP Complete
>issue, I think).

the NP-issue says nothing about 9*9-sudoku. Only that n*n-sudoku
will become very difficult when n becomes larger

>But it's interesting that even these super-fiendish ones crack
>in just 50 steps or so just with this added bit of depth.
>
>Actually, I believe that looking for n-tuples and X-wings
>amounts to adding an element of depth. These can't be found
>with simple forced chain logic. You have to say, "If X is
>true and Y is true, then ...," and that's depth.
>
>But it's an interesting question. What I observe is that the
>solution goes quite rapidly, and since these functions add
>minimal effort to the solution, it seems to me they pay off.
>
>Once you are in trial and error, I don't see why NOT to look
>for these things. The faster we can get to a disproof,
>the better, of course. So I'm sure just using singles
>but allowing full depth would do the job as well -- and
>probably faster.

.. with some additional tricks and modifications. See the puzzles-forum.
But these tricks to speed up the search e.g. for 25*25 sudokus
don't seem to contain any of your 12 rules except singles.

>(My understanding is that that's what the dancing links
>algorithm does,

dancing links just looks for a constraint with minimum possible
placements (usually 2, unless there are singles) and then
tries all the placements for that constraint.
It doesn't tell, what to do on ties, when there are
several constraints with two possible placements, though.
Here you can enter some improvement-ideas.

>but I can't say I understand exactly what's going on there.
>Knuth refers to it as depth backtracking, so I presume that
>all it's doing is straight singles.

essentially, yes

>And I'm told that dancing links can be extremely slow with
>certain "renegade" Sudoku puzzles.)

Then I'd say that any sudoku-solver can be "extremely slow"
with certain puzzles. I don't think there is a 9*9, where
dancing links takes more than 10ms

-Guenter

Bob Hanson · Posted: Sun Dec 04, 2005 5:32 pm Post subject:

dukuso · Posted: Mon Dec 05, 2005 1:03 am Post subject:

http://magictour.free.fr/sudqwh.exe
(source code attached to the executable)
http://www.eleves.ens.fr/home/frisch/sudoku.html#strategy

or see any SAT-solver, since the currently most efficient
way seems to be to convert the sudoku into a SAT-instance
and then use a SAT-solver. The SAT-solver knows
nothing about sudoku-rules, of course.

for a description of the probably fastest SAT-solver
for large sudokus see:
www.ii.uam.es/~delval/ps/aaai04-qwh.pdf

you can get lots of SAT-solvers from:
http://www.intellektik.informatik.tu-darmstadt.de/SATLIB/solvers.html

you can convert sudokus to SAT-instances with:
http://magictour.free.fr/sud2sat.exe

JPF · Posted: Tue Dec 06, 2005 12:07 am Post subject:

thermosome · Posted: Thu Dec 22, 2005 8:07 am Post subject: Are any Sudokus hard?

Are any 9x9 sudokus hard? Are there any that will take most experienced (human) solvers more than an hour to solve? Here is some indirect evidence that suggests there are no hard 9x9 sudokus.

I looked at 32930 17-clue puzzles provided by Gordon:

http://www.csse.uwa.edu.au/~gordon/sudokumin.php

All of them can be solved with a depth 3 computer search. In other words at most 3 levels of guessing are needed. Most were solvable with 2 levels of guessing (28764), some with 1 level of guessing (2196), and some with 3 levels (1970).

It looks like many human (logical) solving techniques are equivalent to 2, 3 or higher levels of guessing. I realize it is a big leap to infer from this that there are no hard sudokus.

I ranked the 1970 17-clue puzzles that required 3 levels of guessing according to how many different first guesses produced a solution. Half of these puzzles could be solved at depth 3 with correct initial guesses in any of 48 cells. One puzzle required an initial guess in one specific cell. The next most difficult could be solve at depth 3 with initial guesses in 5 different cells. The exceptional puzzle that permitted only one initial guess I call "El Loco". It took about 2 hours for me to solve El Loco by hand. Here is that puzzle and the other 8 allowing a depth 3 solution with the fewest number of possible initial guesses. I named the others for easy reference.

A mathematical question:

Can all 9x9 sudokus be solved with a depth 3 search?

Tom

Ruud · Site Admin

It is a common mistake to think that the most difficult Sudokus have to be the ones with the least clues. A search in the list of Gordon's 17s will reveal the most difficult from that list, but certainly not the most difficult known.

In fact, none of the 17s really requires guessing. Some require multiple forward implication chains, but no guesses.

At this moment (and this may change any time), this is the hardest known Sudoku:

gsf · Posted: Thu Dec 22, 2005 11:04 am Post subject: Re: Are any Sudokus hard?

gsf · Posted: Thu Dec 22, 2005 11:20 am Post subject:

dukuso · Posted: Thu Dec 22, 2005 11:39 am Post subject:

what exactly is forward check backtrack guessing ?

BTW. top1465 is here:
http://magictour.free.fr/top1465

gsf · Posted: Thu Dec 22, 2005 12:01 pm Post subject:

dukuso · Posted: Thu Dec 22, 2005 12:10 pm Post subject:

thanks.
can you check :

"forward check haralick"

this gives no entry at google

gsf · Posted: Thu Dec 22, 2005 9:27 pm Post subject: