what is the hardest known suduko ?

Merri · Posted: Tue Aug 02, 2005 2:43 am Post subject:

There is actually a sudoku contest at VBForums. I'm taking part in it, currently I can solve the easiest sudokus in about 0,02 ms, but the hardest (currently your, wallyb, being the one) takes about 190 ms. The permitted languages in the contest are VB6, VB.NET and C#, I use VB6.

I'm trying to figure out if I could find a good and fast logic here, which could help to solve the harder ones faster: I've optimized my backtracker, but as we all know, it isn't the fastest method around no matter how much you optimize. I also have some simple logic coded which explains the super fast results on easier sudokus.

darq · Posted: Wed Aug 03, 2005 9:07 pm Post subject: hardness

The definition of hardness given by dukuso is pretty good when we have a bunch of general-purpose solvers. This definition is machine-oriented and should be a good measure for testing new solver ideas.
But what if we'd like to have a human-oriented measure? Would it be the same? Or is it impossible to give such a measure because every one of us solves in slightly different way? My feel is that for the hardest sudokus the depth of 'anticipation' should be involved in hardness measure.
I like the way tilps has defined hardness in his solver. And I wonder what definition they took at menneske.

dukuso · Posted: Thu Aug 04, 2005 7:21 am Post subject: Re: hardness

Doug · Posted: Fri Aug 05, 2005 8:02 am Post subject:

To me the obvious measure should be the maximum number of future board states that must be computed to make progress on the puzzle at some point in its solution by logic.

tilps needs do take the product of his second and third numbers in his 1.x.y measures. My puzzle has a difficulty of 48 = 12 * 4, as under tilps algorithm its measure is 1.12.4.

I think the reason for measuring number of board states for progress is pretty clear: it maxes out human memory and accuracy quickly.

That said, tilps algorithm is not decisive as it ignores contradiction arguments, which are perfectly valid, and only have a bad name by lame association with backtracking algorithms, which humans cannot do because of their computational complexity, not because of the fact that they rely on contradiction. D'uh folks! All logics can be put in the form of a contradiction by using the contrapositive. Give up this *anti-contradiction* stance. It looks ignorant. And is. Sorry to be so blunt, but someone needs to make this point.
_________________
Doug Bowman
www.flickr.com/photos/bistrosavage

dukuso · Posted: Fri Aug 05, 2005 10:15 am Post subject:

there is a tradeoff between "logic", lookahead to determine the forced
placements (backbone) and just starting to backtrack.

There are clearly problems where any "logic" fails, though maybe
not at size 9*9.
There is always a point where you have to decide whether
you should spend time on finding the next forced placement
with some (new,complicated) rule or just
with complicated lookahead or whether you should just start
backtracking. (humans can do this too !)
And when the latter is faster, why exclude it from a
rating method ?

Guenter.

Doug · Posted: Fri Aug 05, 2005 10:56 am Post subject:

That tradeoff only happens near the end of puzzles. The nearer you are to the beginning, the exponentially longer the backtracking searches are. On very hard puzzles, the problems occur typically near the early stages, or at least the middle, not near the end. Until you can put forth a puzzle where backtracking is *actually* shorter than (even) long logics, you are sounding like a devil's advocate troll. Do you have such a puzzle? I'm being blunt again. Sorry, not meaning offense. Cheers.

Oh, and I really want to hear what tilps has to say about the measure I suggested above. I love his solver's approach. Just wish I could play with an implementation of it. Bah!
_________________
Doug Bowman
www.flickr.com/photos/bistrosavage

dukuso · Posted: Fri Aug 05, 2005 12:29 pm Post subject:

my backtracking solver, which just puts in the immediately
forced entries (from the 324 constraints) but does no refining
with "rules" or lookahead is my fastest.
I did experiment with level2-lookahead
but this was slower.

Also quoting from :
http://staff.washington.edu/ruan/papers/quals.pdf

"Another interesting thing we learned on the basis of knowledge
of the backbone is that branching on the backbone variables
at the root of search tree is a two-edged knife: if you assign the
values to the backbone variables correctly, it really helps; otherwise
it really hurts you"

that was for QWH-problem but I assume that sidoku-completion
problem is similar.
Backbone can be seen as the number of cells which can
be completed by "logic" (however advanced), before you
start backtracking.
But as I said, for a small size like 9*9 it could be different.

Guenter.

Nick70 · Posted: Fri Aug 05, 2005 8:15 pm Post subject:

Doug · Posted: Fri Aug 05, 2005 9:04 pm Post subject:

I said:

"shorter than (even) long logics"

I'm counting the length of the logic used, like tilps said before. Not cpu runtime. My point is to compute the difficulty of human comprehension. Cpu runtime is irrelevent.

tilps said:

"My rating system is an attempt to classify the logic rules generated in a 'basic' order of difficulty. Within each rating classification there are easier and harder ones, and there is probably some overlap between the classifications themselves, but as an overal concept, they show an order of difficulty. "

My point is that he is ignoring the contradiction logic which any reasonable person would use in solving puzzles. To get a more accurate measure of the logical difficulty of the super hard puzzles this needs to be included.

My posts give a suggested method for measuring the difficulty of minimal logic required for solving sudokus.

tilps program is right on target, but I feel it has a couple of flaws:

1) Only he can use it.

2) It ignores contradiction logic

3) He hasn't figured out yet (or at least posted here) how to measure the difficulty from the steps it needs to take in solving the puzzles.

My posts were addressing issues 2) and 3) above.

My solution to 3) is for tilps to compute the total number of future board states required for progress at the hardest point. This reduces to taking the product of his second and third number, if I understand his solver correctly.

Are things clearer now?

BTW here is another super hard puzzle. It's not as difficult as the other one that rates 1.12.4 under silps program, though. I wonder what silps program gives for it:

dukuso · Posted: Mon Aug 08, 2005 6:15 pm Post subject:

seems that tilps has retired from sudoku...

my solver needs 1.1ms to solve it.
9th hardest for me.

Doug · Posted: Mon Aug 08, 2005 7:10 pm Post subject:

I think he just visits the forum in fits and starts.

BTW that puzzle you list second in your list of super hard sudokus was too hard for MadOverlord's susser until he made a recent improvement (not released yet). After his improvement, that second puzzle falls to his susser. My super hard puzzle, which you list as number 1, still defeats it, though. Looks like your number 2 ranking was right on.

Cheers!
_________________
Doug Bowman
www.flickr.com/photos/bistrosavage

dukuso · Posted: Tue Aug 09, 2005 12:30 am Post subject:

and that although I'm just measuring the time needed by a
pure exact-cover solver, doing none of the rules which
humans are told to follow !
That might indicate that computer solvingtime is a suitable
measure for sudoku-hardness.

We still don't know, how you generate these ?!

Guenter.

MadOverlord · Posted: Tue Aug 09, 2005 11:45 am Post subject:

Thanks to an insight by Doug, the tables algorithm now cracks the #1 puzzle! More details in the "Tables" thread.

Merri · Posted: Wed Aug 10, 2005 1:30 pm Post subject:

wallyb · Posted: Thu Aug 11, 2005 6:48 am Post subject: Hardest Sudoku

Hi All

On the subject of judging the most difficult Sudoku, since the hardest puzzles require a directed form of guessing there will be a divergence of results from different solvers. Some will guess better on particular puzzles but be slower on others depending on the algorithms used. A puzzle could be judged by timing it on a range of solvers just as a solver should be judged on a range of puzzles.

An alternative would be to judge the grid of possible candidates for the unsolved cells after all the standard techniques - singles, multiples, X-wings etc. - have been used to simplify the puzzle as much as possible. Of course it would then come down to how you would judge the lists of candidates. Since these puzzles are really designed to be done manually and computer solvers are just a bastard child of Sudoku, perhaps most weight should be placed on singles, which are the cells readily solved manually. To a manual solver, the fewer the singles the harder the puzzle. On that basis the puzzle I submitted above is the only one I have encountered so far without any singles.

Wally