FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in          Games  Calendar Log in to check your private messages    Hardest Sudokus to Solve by Hand          Sudoku Programmers Forum Index -> Solving sudoku 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 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         Sudoku Programmers Forum Index -> Solving sudoku All times are GMT Page 1 of 1   Jump to: Select a forum Sudoku----------------Solving sudokuSetting sudokuProgramming sudokuThe mathematics of sudokuExotic sudoku Library----------------PuzzlesSoftwareSudoku elsewhere Not sudoku----------------Random thoughtsForum feedback  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