Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

NEWS:
what is the hardest known suduko ?
Goto page 1, 2, 3 ... 13, 14, 15  Next
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku
View previous topic :: View next topic  
Author Message
dukuso

Joined: 14 Jul 2005
Posts: 454
:
Location: germany

Items
PostPosted: Fri Jul 22, 2005 6:56 am    Post subject: what is the hardest known suduko ? Reply with quote

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.-...
...-682-7.4
------------
.9.-...-..7
...-3..-4.5
..6-7..-...
------------
..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
View user's profile Send private message Send e-mail Visit poster's website
Nick70

Joined: 08 Jun 2005
Posts: 160
:

Items
PostPosted: Fri Jul 22, 2005 7:11 am    Post subject: Reply with quote

Not that hard, can be solved withoug guessing using turbot fish / xy-wing / 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
View user's profile Send private message
tilps

Joined: 19 Jun 2005
Posts: 46
:

Items
PostPosted: Fri Jul 22, 2005 7:20 am    Post subject: Reply with quote

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
View user's profile Send private message
dukuso

Joined: 14 Jul 2005
Posts: 454
:
Location: germany

Items
PostPosted: Fri Jul 22, 2005 11:26 am    Post subject: Reply with quote

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
View user's profile Send private message Send e-mail Visit poster's website
hoppy

Joined: 15 Jul 2005
Posts: 7
:

Items
PostPosted: Fri Jul 22, 2005 12:38 pm    Post subject: Reply with quote

A dash is a hyphen.

Though really pedantic Britons would say they are not the same.
Back to top
View user's profile Send private message
Nick70

Joined: 08 Jun 2005
Posts: 160
:

Items
PostPosted: Fri Jul 22, 2005 1:02 pm    Post subject: Reply with quote

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
View user's profile Send private message
tilps

Joined: 19 Jun 2005
Posts: 46
:

Items
PostPosted: Sat Jul 23, 2005 3:42 am    Post subject: Reply with quote

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
View user's profile Send private message
Nick70

Joined: 08 Jun 2005
Posts: 160
:

Items
PostPosted: Sat Jul 23, 2005 9:31 am    Post subject: Reply with quote

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
View user's profile Send private message
tilps

Joined: 19 Jun 2005
Posts: 46
:

Items
PostPosted: Sat Jul 23, 2005 2:08 pm    Post subject: Reply with quote

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
View user's profile Send private message
wallyb

Joined: 28 Jul 2005
Posts: 4
:

Items
PostPosted: Thu Jul 28, 2005 1:22 pm    Post subject: Hardest Sudoku Reply with quote

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
View user's profile Send private message
Nick70

Joined: 08 Jun 2005
Posts: 160
:

Items
PostPosted: Thu Jul 28, 2005 10:19 pm    Post subject: Re: Hardest Sudoku Reply with quote

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
View user's profile Send private message
wallyb

Joined: 28 Jul 2005
Posts: 4
:

Items
PostPosted: Fri Jul 29, 2005 5:38 am    Post subject: The hardest Sudoku Reply with quote

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
Back to top
View user's profile Send private message
darq

Joined: 29 Jul 2005
Posts: 7
:

Items
PostPosted: Sat Jul 30, 2005 1:22 am    Post subject: Hardness measure? Reply with quote

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 4-6 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
View user's profile Send private message
dukuso

Joined: 14 Jul 2005
Posts: 454
:
Location: germany

Items
PostPosted: Sat Jul 30, 2005 4:20 pm    Post subject: Reply with quote

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.
Back to top
View user's profile Send private message Send e-mail Visit poster's website
wallyb

Joined: 28 Jul 2005
Posts: 4
:

Items
PostPosted: Mon Aug 01, 2005 2:59 pm    Post subject: Hardest Sudoku Puzzle Reply with quote

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
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku All times are GMT
Goto page 1, 2, 3 ... 13, 14, 15  Next
Page 1 of 15

 
Jump to:  
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
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron
FREE FORUM HOSTING by AtFreeForum. Terms of Service - Privacy Policy
FASHION ACCESSORIES - BLING BLING - LADIES WATCHES - KOREAN CHILDREN CLOTHING - ONLINE BARGAIN STORE - FASHION JEWELLERIES