View previous topic :: View next topic |
Author |
Message |
someone_somewhere
Joined: 07 Aug 2005 Posts: 275 Location: Munich
|
Posted: Mon Dec 12, 2005 5:26 pm Post subject: the hardest Sudoku ever encountered ... |
|
|
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 |
|
|
someone_somewhere
Joined: 07 Aug 2005 Posts: 275 Location: Munich
|
Posted: Mon Dec 12, 2005 5:37 pm Post subject: |
|
|
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 |
|
|
someone_somewhere
Joined: 07 Aug 2005 Posts: 275 Location: Munich
|
Posted: Mon Dec 12, 2005 6:04 pm Post subject: |
|
|
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 |
|
|
David Bryant
Joined: 29 Jul 2005 Posts: 559 Location: Denver, Colorado
|
Posted: Mon Dec 12, 2005 7:19 pm Post subject: It has 69 solutions ... |
|
|
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 |
|
|
someone_somewhere
Joined: 07 Aug 2005 Posts: 275 Location: Munich
|
Posted: Mon Dec 12, 2005 7:39 pm Post subject: |
|
|
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 |
|
|
David Bryant
Joined: 29 Jul 2005 Posts: 559 Location: Denver, Colorado
|
Posted: Fri Dec 16, 2005 11:57 pm Post subject: This is one tough nut! |
|
|
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 |
|
|
someone_somewhere
Joined: 07 Aug 2005 Posts: 275 Location: Munich
|
Posted: Sat Dec 17, 2005 7:28 am Post subject: List of examples for "star constellation" techniqu |
|
|
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 |
|
Back to top |
|
|
someone_somewhere
Joined: 07 Aug 2005 Posts: 275 Location: Munich
|
Posted: Sat Dec 17, 2005 7:38 am Post subject: The limit between the "logic" an "trail and e |
|
|
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 |
|
|
Guest
|
Posted: Thu May 11, 2006 7:52 pm Post subject: |
|
|
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
|
Posted: Thu May 11, 2006 7:57 pm Post subject: |
|
|
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
|
Posted: Mon May 15, 2006 8:11 am Post subject: |
|
|
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 |
|
|
ravel
Joined: 21 Apr 2006 Posts: 536
|
Posted: Mon May 29, 2006 1:50 pm Post subject: |
|
|
For the zen sudoku fans: I started a new thread now with ultrahard puzzles: The hardest sudokus |
|
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
|