
View previous topic :: View next topic 
Author 
Message 
 dukuso
 Joined: 14 Jul 2005  Posts: 424  :  Location: germany  Items 

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.
Anyway, here it is again:
Code: 
7......19
46.19....
...6827.4

.9......7
...3..4.5
..67.....

..1......
2...74...
...2..3..

>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 

Back to top 


 Nick70
 Joined: 08 Jun 2005  Posts: 160  :   Items 

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


Not that hard, can be solved withoug guessing using turbot fish / xywing / double forcing chains.
This one, on the other hand, cannot:
Code:  ..1.8.6.4
.376.....
5........
.....5...
..6.1.8..
...4.....
........3
.....752.
8.2.9.7.. 


Back to top 


 tilps
 Joined: 19 Jun 2005  Posts: 44  :   Items 

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. 

Back to top 


 dukuso
 Joined: 14 Jul 2005  Posts: 424  :  Location: germany  Items 

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 

Back to top 


 hoppy
 Joined: 15 Jul 2005  Posts: 7  :   Items 

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. 

Back to top 


 Nick70
 Joined: 08 Jun 2005  Posts: 160  :   Items 

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


tilps wrote:  Nick70s example is rated 1.2.3  1 lookahead invoking 2 'trivial' logic steps from a possibility triplet. 
Sorry does that mean that your solver doesn't need to backtrack?
How do you get past this stage?
Code:  29 29 1  57 8 3  6 57 4
4 3 7  6 25 129  129 1589 12589
5 6 8  1279 247 1249  1239 1379 1279
++
12379 12789 349  2789 367 5  12349 134679 12679
2379 249 6  279 1 29  8 34579 2579
12379 12789 5  4 367 2689  1239 13679 12679
++
1679 179 49  1258 2456 1268  149 689 3
1369 149 349  18 46 7  5 2 1689
8 5 2  3 9 146  7 146 16 


Back to top 


 tilps
 Joined: 19 Jun 2005  Posts: 44  :   Items 

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...
Code: 
6,3 2) (6,4 2) (6,5 2) Eliminated 6,4 6 in 2 steps
Trial (6,3 2):
0: 6, 3 2
2: 6, 4 5
Trial (6,4 2):
0: 6, 4 2
Trial (6,5 2):
0: 6, 5 2
1: 5, 5 8
2: 8, 5 6
(8,5 1) (8,5 4) (8,5 6) Eliminated 6,7 9 in 2 steps
Trial (8,5 1):
0: 8, 5 1
1: 7, 3 8
2: 6, 7 8
Trial (8,5 4):
0: 8, 5 4
1: 6, 6 4
2: 6, 2 9
Trial (8,5 6):
0: 8, 5 6
1: 8, 8 1
1: 8, 7 4
2: 6, 6 9

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. 

Back to top 


 Nick70
 Joined: 08 Jun 2005  Posts: 160  :   Items 

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


tilps wrote:  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:
r7c6=2 => r7c6<>6
r7c6=2 => r7c6<>8 => r6c6=8 => r6c6<>6 

Back to top 


 tilps
 Joined: 19 Jun 2005  Posts: 44  :   Items 

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. 

Back to top 


 wallyb
 Joined: 28 Jul 2005  Posts: 4  :   Items 

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 

Back to top 


 Nick70
 Joined: 08 Jun 2005  Posts: 160  :   Items 

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


wallyb wrote:  The puzzle of Nick70 has 3 digits solvable by direct methods. 
Can you elaborate on what kind of direct methods?
wallyb wrote:  My solver rated them much easier than the following which for which no digits can be solved manually. 
Funnily, my solver sovles your puzzle using multiple forcing chains, while it cannot solve the one I posted. 

Back to top 


 wallyb
 Joined: 28 Jul 2005  Posts: 4  :   Items 

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, "Xwings" 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 

Back to top 


 darq
 Joined: 29 Jul 2005  Posts: 7  :   Items 

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)
Code:  . . .  . . 3  . 6 .
. . .  . . .  . 1 .
. 9 7  5 . .  . 8 .
++
. . .  . 9 .  2 . .
. . 8  . 7 .  4 . .
. . 3  . 6 .  . . .
++
. 1 .  . . 2  8 9 .
. 4 .  . . .  . . .
. 5 .  1 . .  . . . 
got results: Max guess level: 6, Guess squares: 20, Guesses: 36, Dead ends: 16
Though it's relatively easy to choose a solution at this stage:
Code:  . 8 .  . . 3  . 6 .
. 3 .  . . .  . 1 .
. 9 7  5 . .  3 8 .
++
. . .  . 9 .  2 . .
. . 8  . 7 .  4 . .
. . 3  . 6 .  . . .
++
3 1 6  . . 2  8 9 .
. 4 9  . . .  . 2 .
. 5 2  1 . 9  6 4 . 
(analyzing colums 2, 4 and 8 within rows 46 shows that 3 cannot be placed in row 5 col 4)
On the following puzzle the statistics show lower numbers: Max guess level: 2, Guess squares: 4, Guesses: 8, Dead ends: 4
Code:  . . 1  . . .  . . .
. 9 .  . . 6  . . 3
. . .  . 5 .  1 . .
++
. . .  . . 2  . . 6
1 . 8  . 4 .  5 . .
. . 5  . 8 3  2 . .
++
. . 4  . . .  . 8 .
. . .  9 . .  . . .
. 3 .  . . .  . . 7 
However, in this situation
Code:  . . 1  . . .  . . .
. 9 .  . 1 6  . . 3
. . .  . 5 .  1 . .
++
. . .  5 9 2  8 1 6
1 2 8  6 4 7  5 3 9
9 6 5  1 8 3  2 7 4
++
. . 4  . . 5  9 8 .
. . .  9 . .  3 . .
. 3 9  . . 1  . . 7 
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? 

Back to top 


 dukuso
 Joined: 14 Jul 2005  Posts: 424  :  Location: germany  Items 

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

Back to top 


 wallyb
 Joined: 28 Jul 2005  Posts: 4  :   Items 

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 

Back to top 




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

Powered by phpBB © 2001, 2005 phpBB Group
Igloo Theme Version 1.0 :: Created By: Andrew Charron
