Posted: Fri Jul 22, 2005 6:56 am Post subject: what is the hardest known suduko ?

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.

>this is the hardest sudoku, which my computer could find
>with hillclimbing in some hours.
>It requires 199 guesses and 11574 placements by my program !
>There was a big gap to the 2nd hardest found,
>which required only 64 guesses and 3719 placements.[quote][code]

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

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.

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

Next 5,5 cannot be 6, then 7,4 cannot be 6 trivially, which pretty much solves all the 4s, everything from then on i would say your program can do.
I think the second of the two steps listed is the key. Note the two 1 lines. Two consequences of the initial point are neded to get the second line which gives the common elimination. That 'bifrucation' in the forcing chain is what I suspect your program would miss. 'Complex forcing chains'.

I am not sure why your code would not have found the first, it looks like a simple forcing tripplet.

I am not sure why your code would not have found the first, it looks like a simple forcing tripplet.

No, it's not simple.
In simple forcing chains, each = step follows from a conjugate relationship. In this case r9c6=6 is not conjugate of anything, you needtwo consequences of having put 2 in r7c6:

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.

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 -

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.

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)

I cannot see any relatively simple dependencies (possibly because I'm not experienced and missed something?)

Anyway, my point is that dumb guesses don't give a valuable measure. But what if a solver tried every possiblity of guess and shown a solution, which:
a) minimizes the number of guesses through the resolution process (a guess == choosing a number for a field or choosing a position in row/column/box for a number)
b) then minimizes the number of solving steps needed for reaching "dead ends" from each incorrect guess

Such a solution could be treated as the "simplest" one, and the number of its guesses/steps could be a kind of hardness measure. The reasoning for "dead ends" could also be treated as equivalent of some (possibly complicated) solving scheme.

There is an obvious problem, which techniques would be allowed for the solver to use before trying to guess, and this choice would influence measured results. But anyway - has someone implemented that kind of measure? Or something similar?

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. (?)

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.

All times are GMT Goto page 1, 2, 3 ... 13, 14, 15Next

Page 1 of 15

You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum