dailysudoku.com Forum Index dailysudoku.com
Discussion of Daily Sudoku puzzles
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

the hardest Sudoku ever encountered ...

 
Post new topic   Reply to topic    dailysudoku.com Forum Index -> Other puzzles
View previous topic :: View next topic  
Author Message
someone_somewhere



Joined: 07 Aug 2005
Posts: 275
Location: Munich

PostPosted: Mon Dec 12, 2005 5:26 pm    Post subject: the hardest Sudoku ever encountered ... Reply with quote

Hi,

For me, up to now, this is the hardest Sudoku I ever encountered:

Code:
....7.94.
.7..9...5
3....5.7.
.874..1..
463......
.....7.8.
8..7.....
.......28
.5.268...


Could not solve it using all the techniques, even the advanced ones, except "trail & error".
Any suggestions?

see u,
Back to top
View user's profile Send private message
someone_somewhere



Joined: 07 Aug 2005
Posts: 275
Location: Munich

PostPosted: Mon Dec 12, 2005 5:37 pm    Post subject: Reply with quote

Hi,
I have found only 1 digit:
8 in r5c5

and after a lot of applying the "double implication chain" technique,
I got up to this:

Code:
1256 12   1568  1368 7    1236 9    4    1236

126  7    468   1368 9    2346 2368 136  5
 
3    1249 14689 168  124  5    268  7    126

259  8    7     4    235  2369 1    3569 2369

4    6    3     159  8    12   257  59   27

1259 129  1259  3569 235  7    346  8    3469

8    2349 26    7    1345 349  456  1569 1469

1679 349  1469  1359 1345 349  4567 2    8

179  5    149   2    6    8    347  139  13479


P.S. I did not try any solver from Internet pages.

see u,
Back to top
View user's profile Send private message
someone_somewhere



Joined: 07 Aug 2005
Posts: 275
Location: Munich

PostPosted: Mon Dec 12, 2005 6:04 pm    Post subject: Reply with quote

Sorry, I think that I copied (the first Sudoku that I have posted) it wrong.
Because of this it could have multiple solutions, which I can not check.

It looks like I have missed the digit 7 in r8c1. This is because I found between I stored puzzles one from Doug Bowman, which looks like:

Code:
....7.94.
.7..9...5
3....5.7.
.874..1..
463.8....
.....7.8.
8..7.....
7......28
.5.268...


and this could be solved with "double implication chains".
So, what is left for me: if someone has a program to check that the initial posted puzzle has no unique solution, it will make my day.

P.S. the solution for the above one is:
Code:
  2 1 5 8 7 6 9 4 3
  6 7 8 3 9 4 2 1 5
  3 4 9 1 2 5 8 7 6
  5 8 7 4 3 2 1 6 9
  4 6 3 9 8 1 7 5 2
  1 9 2 6 5 7 3 8 4
  8 2 6 7 4 3 5 9 1
  7 3 4 5 1 9 6 2 8
  9 5 1 2 6 8 4 3 7


see u,
Back to top
View user's profile Send private message
David Bryant



Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado

PostPosted: Mon Dec 12, 2005 7:19 pm    Post subject: It has 69 solutions ... Reply with quote

Someone_Somewhere wrote:
So, what is left for me: if someone has a program to check that the initial posted puzzle has no unique solution, it will make my day.

I guess I can make your day today!

I ran the initial version of this puzzle (the one with the missing "7") through a solver program, and the program informed me that the puzzle has 69 different solutions. dcb

PS The revised puzzle seems very tough, even with the "extra" clue.
Back to top
View user's profile Send private message Send e-mail Visit poster's website
someone_somewhere



Joined: 07 Aug 2005
Posts: 275
Location: Munich

PostPosted: Mon Dec 12, 2005 7:39 pm    Post subject: Reply with quote

Hi David,

A big THANK YOU. You made my day.
Could you give me the link to the page of the solver you have used?

Yup, the puzzle with the additional 7 is even so one of the most difficult ones. The 3D Meduza is cnacking it. I used "double implication chains" which are equivalent to 3D Meduza and it is solving it.

for 3D Meduza see:
http://www.stolaf.edu/people/hansonr/sudoku/top95-analysis.htm#medusa

see u,
Back to top
View user's profile Send private message
David Bryant



Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado

PostPosted: Fri Dec 16, 2005 11:57 pm    Post subject: This is one tough nut! Reply with quote

Someone_Somewhere wrote:
Yup, the puzzle with the additional 7 is even so one of the most difficult ones.

This puzzle is ridiculously complicated. I don't think a typical human solver would have the patience to get all the way through it. I know that I don't have that much patience -- I ran it through a computerized solver to learn how the logic goes. There's an awful lot of logic involved, much of it coming close to "trial and error."

Anyway, here's the chain of reasoning to place the first number in this puzzle, an "8" at r5c5. Let's start with the grid of possibilities.
Code:
 1256     12     1258    1368      7     1236      9       4     1236
  126      7     1248    1368      9     12346    2368    136      5
   3     1249    12489    168    1248      5      268      7      126
  259      8       7       4      235    2369      1     3569    2369
   4       6       3     1589    1258     129     257     59      279
 1259     129    1259    3569     235      7     23456     8     23469
   8     12349   12469     7     1345    1349     456    1569    1469
   7     1349    1469    1359    1345    1349     456      2       8
  19       5      149      2       6       8      347     139    13479

We observe, first, that there are only two cells in which "8" can fit in column 5 -- it's either at r3c5, or else it's at r5c5. Let's assume, for the sake of argument, that r3c5 = 8. Then the following moves are forced.

-- As a result of this move, the triplet {1, 3, 6} appears in column 4, rows 1 - 3. Eliminating these values from the rest of the top center 3x3 box reveals a "2" in r1c6 and a "4" in r2c6.

-- Still as a result of the "8" at r3c5, we see a triplet {1, 2, 6} in row 3 -- eliminating these values (plus the "8") from r3c2 & r3c3 reveals a pair {4, 9} in those two cells.

-- We see one last thing as the immediate result of our first move, r3c5 = 8: the existence of the {1, 3, 6} triplet noted above also forces the {5, 9} pair to appear at r6c4 & r8c4, and from that we deduce r5c4 = 8.

-- r7c2 = 8 (sole candidate in top right 3x3 box).

-- r1c2 = 1; r2c3 = 2; r2c1 = 6; r1c1 = 5; r1c3 = 8. All these moves are forced by the "2" at r1c6, by the existence of the {4, 9} pair in r3c2 & r3c3, and by the "8" at r2c7.

We've made quite a few moves already, and the matrix has changed quite a bit as a result. Here's an updated version of the matrix, after making these moves.
Code:
   5       1       8      36       7       2       9       4      36
   6       7       2      13       9       4       8      13       5
   3      49      49      16       8       5      26       7      126
  29       8       7       4      235     369      1     3569    2369
   4       6       3       8      125     19      257     59      279
  129     29      159     59      235      7     23456     8     23469
   8     2349    1469      7     1345     139     456    1569    1469
   7      349    1469     59     1345     139     456      2       8
  19       5      149      2       6       8      347     139    13479

Continuing with the forced moves, we note the {2, 9} pair in the middle left 3x3 box:

-- r6c1 = 1 (sole candidate in middle left 3x3 box). Note that this move creates the {5, 9} pair in row 6, forcing us to conclude that r6c2 = 2 and that r4c1 = 9. But now a contradiction is apparent, because there is no available candidate at r9c1. We conclude that our initial move, r3c5 = 8, is impossible; therefore r5c5 = 8.

And that's just the first move on this monstrously difficult puzzle! dcb
Back to top
View user's profile Send private message Send e-mail Visit poster's website
someone_somewhere



Joined: 07 Aug 2005
Posts: 275
Location: Munich

PostPosted: Sat Dec 17, 2005 7:28 am    Post subject: List of examples for "star constellation" techniqu Reply with quote

Hi David,

I told you, that it is "one of the/the" most difficult ones.

The same way one is solving and having fun with classic techniques,
one can have fun using the highly advanced techniques.

You will not need a computer program in order to use the "double implication" chains.
I found at the Internet page (you have mentioned):
http://krazydad.com/sudoku/
the "Super Tough" (Sudoku Puzzles by Jim Bumgardner)
as adequate for training this technique.

The difference is that you work with the "candidate table" instead of the "Sudoku table". Now one has to find the "4 start constellations" or the "5 star constellations" (if possible without writing the double implication chains on the paper, just trying to keep them in the head).

Some/most of them can be cracked after finding only one "star constellation" and this is all the fun.
The problem is from where and which digit to start the double implication chain technique.

The best strategy that I have found, up to now, is to start from the pairs (as I have mentioned in one of my previous messages). This because if one came to a contradiction, than one digit from the pair can be eliminated (unfortunate, not in all cases) and the other digit is the one we where looking for this cell.

Lately, I have found out that for some puzzles, there are "too less" pairs, so I did not know what to do next. I found that it makes a lot of sence (meaning it looks to be a good strategy) to start with a digit from a cell of the candidate table that has more than 2 as candidates, (as I say, from a digit) that when eliminated, an other one from the row/column/3x3 block can be marked as beeing part of the solution.

If you select random a digit and do the "double implication chain" strating from it, you can find out [after a lot of work] that you can eliminate it from the candidate table, but after this ... you will notice that you did not make a substantial progress, meaning that you will have to pick an other one to continue.

Example for puzzles which you can crack after finding one constallation are a challanging nice start for a training.
See Super-Tough example 8 from book 8 from the above link.

I could make a list of examples, for interested solvers, who want to solve Sudoku's beyond the advanced techniques and that have only one "star constellation" after which it can be cracked.

Just let me know (I don't want to work on it, if the market has no need ...)

see u,

P.S. sorry if it was to "chinezee" for some of the readers, but if you take a look at the "double implication chain" techniques, you will understand what I was trying to explain [I am sure].
P.P.S. my message was still shorter than the average ones from Alan Laughing
Back to top
View user's profile Send private message
someone_somewhere



Joined: 07 Aug 2005
Posts: 275
Location: Munich

PostPosted: Sat Dec 17, 2005 7:38 am    Post subject: The limit between the "logic" an "trail and e Reply with quote

There is no general limit between "logic" and "trail and error".

The limit is different for every human solver:

"Trail and error" starts from where our "logic and memory" gets to the it's limit.

see u,
Back to top
View user's profile Send private message
Guest






PostPosted: Thu May 11, 2006 7:52 pm    Post subject: Reply with quote

ill try it, but it seems that even a computer had to guess to get the final answer

Difficulty score: 4401
Number of guesses required: 4
Back to top
Guest






PostPosted: Thu May 11, 2006 7:57 pm    Post subject: Reply with quote

i put in the revised one and it gave me an even harder difficulty level

Difficulty score: 9610
Number of guesses required: 9
Back to top
ravel



Joined: 21 Apr 2006
Posts: 536

PostPosted: Mon May 15, 2006 8:11 am    Post subject: Reply with quote

Its a toughie, but with 3 brute force steps not hard enough to add it to my toughest list.
Brute force step means, that by setting a cell to a value, my (rather simple) program enounters a contradiction using singles, k-tuples, locked candidates, x-wing and UR type 1.

Using those eliminations it can be solved with the same techniques:
r2c3<>4, r3c5<>1, r3c2<>9 or
r3c3<>4, r2c3<>4, r3c5<>1
(in arbitrary order)
Back to top
View user's profile Send private message
ravel



Joined: 21 Apr 2006
Posts: 536

PostPosted: Mon May 29, 2006 1:50 pm    Post subject: Reply with quote

For the zen sudoku fans: I started a new thread now with ultrahard puzzles: The hardest sudokus
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    dailysudoku.com Forum Index -> Other puzzles All times are GMT
Page 1 of 1

 
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


Powered by phpBB © 2001, 2005 phpBB Group