what is the hardest known suduko ?

dukuso · Last edited by dukuso on Fri Jul 22, 2005 3:20 pm; edited 8 times in total

seems that there is no accepted measure for "hardness",
but anyway ...

OK, I found this one, posted it yesterday but deleted it again
after I realized that my solver rated it much less hard,
when I rotated it or just changed the order of processing
the moves.

Anyway, here it is again:

Nick70 · Posted: Fri Jul 22, 2005 7:11 am Post subject:

Not that hard, can be solved withoug guessing using turbot fish / xy-wing / double forcing chains.

This one, on the other hand, cannot:

tilps · Posted: Fri Jul 22, 2005 7:20 am Post subject:

Original one is rated 1.2.2 by my current solver - see puzzles section for a 1.3.2 and a 1.2.3 puzzle

1.2.2 is 1 lookahead invoking 2 'trivial' logic steps from a possibility pair needed to make progress at some point during the logical solve.

Just a random note, when posting boards its best to use the 'code' button to wrap the board. And if you are feeling really friendly, dashes are usually used to mark group boundries and whitespace or dots to mark empty squares, rather than the otherway round.

Nick70s example is rated 1.2.3 - 1 lookahead invoking 2 'trivial' logic steps from a possibility triplet.

dukuso · Posted: Fri Jul 22, 2005 11:26 am Post subject:

thanks.
Can we have the 1.3.2 here ?

I'm still learning how to post sudokus here, what's a "dash" ?

I'm not sure how your rating works. Does it also work
for 16*16 sudokus ?

Maybe I can refine my method to create hard sudokus later...

sorry, I see now that I should have posted this to the
"extremely hard puzzles" thread in the "puzzles" section

hoppy · Posted: Fri Jul 22, 2005 12:38 pm Post subject:

A dash is a hyphen.

Though really pedantic Britons would say they are not the same.

Nick70 · Posted: Fri Jul 22, 2005 1:02 pm Post subject:

tilps · Posted: Sat Jul 23, 2005 3:42 am Post subject:

My solver appears to have followed a very different path to yours. Taking from your current fixed positions rather than the starting state, and apart from eliminations which you have already generated...

Nick70 · Posted: Sat Jul 23, 2005 9:31 am Post subject:

tilps · Posted: Sat Jul 23, 2005 2:08 pm Post subject:

Ahh, simple forcing chains are even simpler then I expected.

I think i should investigate changing my rating scheme to take into account the bifrucations, since they really do increase the challenge level significantly. Unfortunately to ensure accuracy of rating in that case would cause a large increase in 'rating time' per sudoku.

wallyb · Posted: Thu Jul 28, 2005 1:22 pm Post subject: Hardest Sudoku

Hi

I have examined the 2 puzzles above and that of Dukuso has 2 digits which can be solved manually. The puzzle of Nick70 has 3 digits solvable by direct methods. My solver rated them much easier than the following which for which no digits can be solved manually. It is the most difficult I have encountered. I have confirmed the solution is unique -

002 | 090 | 107
038 | 600 | 000
400 | 000 | 000
----+-----+----
000 | 005 | 000
009 | 010 | 300
000 | 400 | 000
----+-----+----
000 | 000 | 004
000 | 007 | 920
806 | 030 | 700

Wally

Nick70 · Posted: Thu Jul 28, 2005 10:19 pm Post subject: Re: Hardest Sudoku

wallyb · Posted: Fri Jul 29, 2005 5:38 am Post subject: The hardest Sudoku

Hi Nick70

Using the sudoku jargon, my direct processing is simply filling in "Singles" and "Hidden Singles" - the ones most people who do the puzzles manually would complete. My solver doesn't use any rocket science. It simply fills in the singles and then, in an optimised way, iterates the reduced problem by trial and error to find the solution. I use Prolog, which is very suited to an iterative approach. It displays the solved singles differently so they are easily recognised. Of course, since there are no solvable singles in the puzzle I submitted, my solver found it the hardest.

Frankly, until I encountered puzzles of the difficulty level of those on this thread, my solver seemed to be so fast that any improvement was academic. Now I know otherwise.

I have toyed with with the idea of using higher level direct processing - those intersecting doubles, triples, "X-wings" etc. - but it requires a lot of programming for, what seems at least, moderate improvement. To a certain extent they probe the weaknesses in the puzzle which the iterative approach, tackled in the best order, may eliminate quickly anyway. That is why, at this stage, I intend to work on the optimisation. No doubt the best program would include both.

I have seen "multiple forcing chains" mentioned in the forums but have not followed it up. Perhaps I should. I am impressed that your solver had no difficulty with that problem.

Wally

darq · Posted: Sat Jul 30, 2005 1:22 am Post subject: Hardness measure?

Hello,

even if there is no commonly accepted measure for hardness, I guess there were some attempts made for such an indicator. Can anyone point them out?

I used Paul's solver (http://www.paulspages.co.uk/sudoku/) and tried to take its statistics of guesses as a kind of measure, but the results are far from intuition. Eg. for this puzzle (credited to RUBYLIPS)

dukuso · Posted: Sat Jul 30, 2005 4:20 pm Post subject:

trying to give a definition of hardness:

it's the running time of the fastest solver-program around.

I guess, this solver would use "backtracking" or "t/e"
for the small fraction of really hard puzzles
although it woulf be possible to do it without, but
I assume this would be slower or not much faster
at least.

It's not clear to me, whether there is a definition of
"t/e" either. We could traverse the searchtree to a given
depth and then decide which path to choose, but that's
pretty close to t/e when the depth is 3 or higher, isn't it ?

My fastest solver just fills in directly forced cells but
otherwise just does backtracking.
I was hoping this would change for 16*16,25*25 but
it might not. (?)

Guenter.

wallyb · Posted: Mon Aug 01, 2005 2:59 pm Post subject: Hardest Sudoku Puzzle

Hi again

The approach I took in a trial / error was to tackle in order the structure (row,column or box) with the most known information and leave the least known to last. I am convinced I can get faster solutions by choosing a better order to trial the cells.

With so many people striving to create sudoku solving programs it would be challenging if someone held a competition for the fastest solver. I would just like to see the pace of the best - say on a group of nominated puzzles - to be motivated to squeeze a bit more speed out of mine.

The other challenge is to design the hardest puzzle.

Wally