View previous topic :: View next topic |
Author |
Message |
| Mark
| Joined: 19 Oct 2005 | Posts: 30 | : | Location: Arizona | Items |
|
Posted: Sun Dec 18, 2005 3:06 am Post subject: Hardest Sudokus to Solve by Hand |
|
|
In a recent post, Bob H. suggested mentioning truly difficult sudokus that had been published in newspapers. I encountered one such beast recently, which I thought exceeded the limits of human solvability. It's No. 50 from Penguin Sudoku 2006:
Code: | .5..7...9
8.4..9.1.
.....152.
9......45
..3...9..
24......6
.187.....
.6.4..7.3
4...3..5.
|
This puzzle gave Sudoku Susser fits, requiring extensive tabling operations that would be pretty unthinkable for humans to attempt. Oddly, though, Eppstein's solver rated it as only "evil", having cracked it by means of the "path" rule.
Any opinions?
Mark |
|
Back to top |
|
|
| Ruud Site Admin
| Joined: 17 Sep 2005 | Posts: 708 | : | Location: Netherlands | Items |
|
Posted: Sun Dec 18, 2005 9:13 am Post subject: |
|
|
Hi Mark,
I checked the puzzle with Sudo Cue, and it also required tabling to complete. Since there was only a single tabling step required, and my program does not try to find the shortest chain, there may be a short forcing chain present.
A puzzle of this difficulty is usually not published. But heck, so are puzzles with multiple solutions, and I've seen them too.
Ruud. _________________ Meet me at sudocue.net |
|
Back to top |
|
|
| Nick70
| Joined: 08 Jun 2005 | Posts: 160 | : | | Items |
|
Posted: Sun Dec 18, 2005 11:01 am Post subject: |
|
|
The only difficult step is at this position:
Code: | 16 5 126 | 2368 7 23468 | 3468 368 9
8 23 4 | 2356 256 9 | 36 1 7
7 39 69 | 368 468 1 | 5 2 48
-------------------+--------------------+-------------------
9 78 16 | 12368 268 23678 | 1238 4 5
16 78 3 | 1256 2456 2456 | 9 78 12
2 4 5 | 1389 89 378 | 138 378 6
-------------------+--------------------+-------------------
3 1 8 | 7 2569 256 | 246 69 24
5 6 29 | 4 1 28 | 7 89 3
4 29 7 | 2689 3 268 | 1268 5 128 |
Look at the bivalue cells
Code: | 16 | |
23 | | 36
39 69 | | 48
-------------------+--------------------+-------------------
78 16 | |
16 78 | | 78 12
| 89 |
-------------------+--------------------+-------------------
| | 69 24
29 | 28 | 89
29 | | |
You can see the xy-chain
6-r2c7-3-r2c2-2-r9c2-9-r8c3-2-r8c6-8-r8c8-9-r7c8-6
which allows to remove 6 from r1c8. It's easy from there. |
|
Back to top |
|
|
| Mark
| Joined: 19 Oct 2005 | Posts: 30 | : | Location: Arizona | Items |
|
Posted: Sun Dec 18, 2005 1:05 pm Post subject: |
|
|
Nick70 wrote: | Look at the bivalue cells
Code: | 16 | |
23 | | 36
39 69 | | 48
-------------------+--------------------+-------------------
78 16 | |
16 78 | | 78 12
| 89 |
-------------------+--------------------+-------------------
| | 69 24
29 | 28 | 89
29 | | |
You can see the xy-chain
6-r2c7-3-r2c2-2-r9c2-9-r8c3-2-r8c6-8-r8c8-9-r7c8-6
which allows to remove 6 from r1c8. It's easy from there. |
Thanks. This chain does comport with Eppstein's path rule, which looks for bivalued cells with conflicting endpoints. In this case, choosing a 6 at r1c8 would necessarily result in two conflicting endpoints in column 8, so such cannot be the case.
Nonetheless, spotting such a chain would appear to be daunting for a human solver. Perhaps that's only the case initially. With practice, I suppose, one can begin to see even fairly long chains with conflicting endpoints.
Out of curiosity, did you solve this one by hand, or did you rely on software to find the chain? It would be interesting to know how many paths were searched before a conflict was found.
Mark |
|
Back to top |
|
|
| Mark
| Joined: 19 Oct 2005 | Posts: 30 | : | Location: Arizona | Items |
|
Posted: Mon Dec 19, 2005 1:24 am Post subject: |
|
|
Ruud wrote: | I checked the puzzle with Sudo Cue, and it also required tabling to complete. Since there was only a single tabling step required, and my program does not try to find the shortest chain, there may be a short forcing chain present. |
Thanks, Ruud. I must confess that the xy-chain identified by Nick went beyond my current abilities to spot manually.
Yet, there was a subtle clue when considering this puzzle (No. 50) within the broader context of the Penguin 2006 Sudokus. Many of the 5-star entries prior to No. 50 could be cracked by identifying simple xy-wings. So, this sets up a kind of "theme" to the puzzles, if you will. Since an xy-wing is just an xy-chain with a single intermediate node, it makes sense that they would generalize things at some point to "n" intermediate nodes.
One philosophical point, though: these xy-chains are well-defined structures that can be found in polynomial time without any use of trial and error. In that sense, they're every bit as logical as, say, subsets. So, if I ever get around to designing a solver, my personal preference would be to search for xy-chains before resorting to tabling.
Cheers, Mark |
|
Back to top |
|
|
| Bob Hanson
| Joined: 05 Oct 2005 | Posts: 187 | : | Location: St. Olaf College | Items |
|
Posted: Thu Dec 22, 2005 12:23 am Post subject: |
|
|
Thanks, mark. Nice puzzle.
Precisely the elimination Sudoku Assistant does when set for Y-cycles only. _________________ Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr |
|
Back to top |
|
|
| Pep
| Joined: 27 Nov 2005 | Posts: 10 | : | Location: Bath, UK | Items |
|
Posted: Thu Dec 22, 2005 11:16 am Post subject: |
|
|
It is a good puzzle.
My program finds at the key point, 45 simple inference chains that lead to erasures, and two which lead to a candidate being fixed. The shortest chain is listed as:
Code: | Elide 3 from r6c4 because to fix it forces a chain of inferences via 3@{r6c4} - (r6) - (!3)@{r6c8} - (c8) - 3@{r1c8} - (r1) - (!3)@{r1c6} - (b2) - 3@{r3c4,r2c4,r1c4} to a clash in c4. |
and the two fixtures are:
Code: | Fix 9 in r3c3 because to elide it forces a chain of inferences via (!9)@{r3c3} - (r3) - 9@{r3c2} - (!3)@{r3c2} - (c2) - 3@{r2c2} - (r2) - (!3)@{r2c7} - 6@{r2c7} - (c7) - (!6)@{r9c7,r7c7} - (b9) - 6@{r7c8} - (!9)@{r7c8} - (c8) - 9@{r8c8} - (r8) - (!9)@{r8c3} to a clash in c3.
Fix 9 in r8c8 because to elide it forces a chain of inferences via (!9)@{r8c8} - (r8) - 9@{r8c3} - (!2)@{r8c3} - (c3) - 2@{r1c3} - (b1) - (!2)@{r2c2} - 3@{r2c2} - (r2) - (!3)@{r2c7} - 6@{r2c7} - (b3) - (!6)@{r1c8} - (c8) - 6@{r7c8} - (!9)@{r7c8} to a clash in c8.
|
|
|
Back to top |
|
|
| Mark
| Joined: 19 Oct 2005 | Posts: 30 | : | Location: Arizona | Items |
|
Posted: Thu Dec 22, 2005 10:20 pm Post subject: |
|
|
Pep wrote: | My program finds at the key point, 45 simple inference chains that lead to erasures, and two which lead to a candidate being fixed. The shortest chain is listed as:
Code: | Elide 3 from r6c4 because to fix it forces a chain of inferences via 3@{r6c4} - (r6) - (!3)@{r6c8} - (c8) - 3@{r1c8} - (r1) - (!3)@{r1c6} - (b2) - 3@{r3c4,r2c4,r1c4} to a clash in c4. |
|
That chain is indeed elegant, and a useful reminder NOT to restrict one's attention solely to bivalue cells when looking for conflicting endpoints. Thanks!
Having grown more accustomed to these inference chains, spotting them is now much easier when solving sudokus by hand. Less than a week ago, I thought such techniques were practical only for computer solution. Now I'm beginning to see that even the more sophisiticated graph-theoretic methods mentioned in Eppstein's paper are within the reach of human solvers: with PRACTICE, that is!
Mark |
|
Back to top |
|
|
| daj95376
| Joined: 05 Feb 2006 | Posts: 349 | : | | Items |
|
Posted: Sun Jul 16, 2006 1:58 am Post subject: |
|
|
Nick70 wrote: | The only difficult step is at this position:
Code: | 16 5 126 | 2368 7 23468 | 3468 368 9
8 23 4 | 2356 256 9 | 36 1 7
7 39 69 | 368 468 1 | 5 2 48
-------------------+--------------------+-------------------
9 78 16 | 12368 268 23678 | 1238 4 5
16 78 3 | 1256 2456 2456 | 9 78 12
2 4 5 | 1389 89 378 | 138 378 6
-------------------+--------------------+-------------------
3 1 8 | 7 2569 256 | 246 69 24
5 6 29 | 4 1 28 | 7 89 3
4 29 7 | 2689 3 268 | 1268 5 128 |
Look at the bivalue cells
Code: | 16 | |
23 | | 36
39 69 | | 48
-------------------+--------------------+-------------------
78 16 | |
16 78 | | 78 12
| 89 |
-------------------+--------------------+-------------------
| | 69 24
29 | 28 | 89
29 | | |
You can see the xy-chain
6-r2c7-3-r2c2-2-r9c2-9-r8c3-2-r8c6-8-r8c8-9-r7c8-6
which allows to remove 6 from r1c8. It's easy from there. |
I believe it also allows you to remove the <6> from r7c7 and r9c7. |
|
Back to top |
|
|
| Carcul
| Joined: 29 Dec 2005 | Posts: 50 | : | Location: Coimbra, Portugal | Items |
|
Posted: Mon Jul 17, 2006 11:21 am Post subject: |
|
|
Daj95376 wrote: | I believe it also allows you to remove the <6> from r7c7 and r9c7. |
Yes it does. |
|
Back to top |
|
|
| maria45
| Joined: 16 Sep 2005 | Posts: 2 | : | | Items |
|
Posted: Tue Aug 08, 2006 10:39 am Post subject: |
|
|
Nick70 wrote: | The only difficult step is at this position:
Code: | 16 5 126 | 2368 7 23468 | 3468 368 9
8 23 4 | 2356 256 9 | 36 1 7
7 39 69 | 368 468 1 | 5 2 48
-------------------+--------------------+-------------------
9 78 16 | 12368 268 23678 | 1238 4 5
16 78 3 | 1256 2456 2456 | 9 78 12
2 4 5 | 1389 89 378 | 138 378 6
-------------------+--------------------+-------------------
3 1 8 | 7 2569 256 | 246 69 24
5 6 29 | 4 1 28 | 7 89 3
4 29 7 | 2689 3 268 | 1268 5 128 |
|
A very short forcing chain could be also (same weak spot):
r2c2=3 => r2c7=6 or
r2c2=2 => r1c13=16 (naked pair) => r2c7=6,
so r2c7=6 which solves the puzzle.
Greetings, Maria _________________ meden agan. |
|
Back to top |
|
|
|