FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in          Games  Calendar Log in to check your private messages    hardest 16*16 Goto page 1, 2  Next          Sudoku Programmers Forum Index -> Puzzles View previous topic :: View next topic   Author Message dukuso Joined: 14 Jul 2005 Posts: 424 : Location: germany Items Posted: Sun Jul 31, 2005 11:40 am    Post subject: hardest 16*16 ......1....A.C2F ...7.C.....4.3.. 51..3.G.7.E.B..A ..DC2..4.B8G.... .C...8.6...9.1F. ...2..7.4..D..6. F5A..........9.4 .B.8.9....A..7.. C2....9..6...... ..E.F....25C..G7 .4.9BA........1. 6.1..4..3...ED.8 2....5F8..D...B. 4.....D.2..1.G.. ..86A..3BG.....9 ....E2B...67..35 Back to top droid42 Joined: 29 Jul 2005 Posts: 20 : Items Posted: Fri Aug 05, 2005 6:43 am    Post subject: Blimey, that was a toughie indeed. 24s for my solver and it went down to a recursion level of 3 (but only needed to "guess" one cell). Ian. Back to top r4pi Joined: 06 Aug 2005 Posts: 1 : Items Posted: Sat Aug 06, 2005 9:54 pm    Post subject: That was difficult. I actually had to improve my solver to get it to run in a sensible time frame. Using nishio and 4 guesses, my solver took 13.94 seconds. Back to top xyzzy Joined: 24 Aug 2005 Posts: 80 : Items Posted: Wed Aug 24, 2005 10:51 pm    Post subject: Solved in 1.17 seconds on a Pentium2 @ 333MHz. This one I found is harder for my solver, taking 1.70 seconds. Code: . A . . * G . . E * . . . . * F D . . . B 6 . * 2 . 1 . * . 4 . . * . 9 . . . . . . * . . . . * . . . C * . . . 7 D . . . * . A . . * . . F . * 5 3 8 . ************************************* . . . 8 * 6 . . B * 4 3 . E * . . . . . F . . * . . 8 2 * D . . . * E 1 4 . . . G 7 * . 5 . . * . 1 . . * . 2 . D . E . . * C . . . * G 9 A . * . . . . ************************************* . . . . * . D 7 3 * . . . 4 * . . B . 5 . C . * . . F . * . . 8 . * A E . . . 2 9 E * . . . A * 3 G . . * . . C . . . . . * E . 4 5 * 1 . . 6 * G . . . ************************************* . G D 9 * . 8 . . * . . E . * . . . 6 C . . . * A . . . * . . . . * . . . . . . 4 . * . . 9 . * . B . 7 * . F 3 . . . 1 3 * . . . . * 5 . . 2 * . . 7 . Back to top dukuso Joined: 14 Jul 2005 Posts: 424 : Location: germany Items Posted: Thu Aug 25, 2005 3:31 am    Post subject: some more hard 16*16 are here: http://magictour.free.fr/su16 Back to top dukuso Joined: 14 Jul 2005 Posts: 424 : Location: germany Items Posted: Fri Sep 02, 2005 1:40 pm    Post subject: another hard one: Code: ......G.49...E52 1.....8..EG.A9.3 .72.3...8.....4. E.5.7.....F...C. ....G.52.F....8. .......E........ 5.B..94..D.2.... ...D.73......G.B .6..F..1E...3..9 ....A67.5....2E. D.G4.......B.... .5...3.47.C.D..1 7.FA8D....2GE... 8B.6..9C3A.EG..4 ...9...A...41... ........D...9.6. Back to top dukuso Joined: 14 Jul 2005 Posts: 424 : Location: germany Items Posted: Sun Oct 30, 2005 1:32 pm    Post subject: new list of hard 16*16-sudokus at : http://magictour.free.fr/top46 hardest now : Code: .G...7...8.B.D.. ....F....1DE.5.G 6A...........8.C 1.....6.34...... .7E...9B4A...... ..............C2 .B...4E1......D9 .5.6..8.G.....7. G....A.DE...9..8 .964G..3...D..2. F....5C...8.46.. C...4...B2.A.... .......72...B.F. 56.C2...A...3.8. .E...G..C7B.A..1 .DF8...A...37.5. Back to top rubylips Joined: 07 Apr 2005 Posts: 62 : Location: London Items Posted: Thu Nov 03, 2005 2:19 pm    Post subject: I've tested the four puzzles here on a solver with just the 'Locked Sector Candidates' and 'Disjoint Subsets' logical strategy types enabled. Two metrics have been produced - time to first solution (arguably the time taken to establish the uniqueness of the solution would be a better measure) and the number of guesses made. dukuso I - 140 guesses in 1.75s dukuso II - 25 guesses in 0.3s dukuso III - 49 guess in 0.85s xyzzy - 58 guesses in 0.75s (Originally my puzzle!) Clearly, dukuso and I have very different metrics. Presumably the results are heavily affected by the effectiveness of the guessing algorithm implemented in the solver. _________________ Java 5.0 Solver/Composer Applet: http://act365.com/sudoku GPL Source Code: http://sf.net/projects/sudoku Back to top dukuso Joined: 14 Jul 2005 Posts: 424 : Location: germany Items Posted: Thu Nov 03, 2005 3:18 pm    Post subject: rubylips wrote: I've tested the four puzzles here on a solver with just the 'Locked Sector Candidates' and 'Disjoint Subsets' logical strategy types enabled. Two metrics have been produced - time to first solution (arguably the time taken to establish the uniqueness of the solution would be a better measure) and the number of guesses made. dukuso I - 140 guesses in 1.75s dukuso II - 25 guesses in 0.3s dukuso III - 49 guess in 0.85s xyzzy - 58 guesses in 0.75s (Originally my puzzle!) Clearly, dukuso and I have very different metrics. Presumably the results are heavily affected by the effectiveness of the guessing algorithm implemented in the solver. can you try the 44 at http://magictour.free.fr/top44 and report the timings, then we can calculate the correlation coefficients as we had done with the contest-programs ? Back to top rubylips Joined: 07 Apr 2005 Posts: 62 : Location: London Items Posted: Thu Nov 03, 2005 6:26 pm    Post subject: The quoted time is time to find all solutions (i.e. to establish the uniqueness of the solution). The number of eliminations quoted per strategy includes all paths, i.e. the count hasn't been partially reset after a backtrack. The Disjoint Subsets algorithm has limited its search to groups of six cells/values. Puzzle #4 proved by far the most difficult with 2427 unwinds required. Code: Puzzle #1: 1 solution found in 2.812s Unwinds: 413 Single Candidature: 17254 calls Locked Sector Candidates: 2260 calls 2997 eliminations Disjoint Subsets: 912 calls 2128 eliminations Puzzle #2: 1 solution found in 1.250s Unwinds: 226 Single Candidature: 9440 calls Locked Sector Candidates: 1136 calls 1701 eliminations Disjoint Subsets: 490 calls 1335 eliminations Puzzle #3: 1 solution found in 2.953s Unwinds: 386 Single Candidature: 17012 calls Locked Sector Candidates: 2094 calls 2795 eliminations Disjoint Subsets: 809 calls 1773 eliminations Puzzle #4: 1 solution found in 13.156s Unwinds: 2427 Single Candidature: 98388 calls Locked Sector Candidates: 9868 calls 12293 eliminations Disjoint Subsets: 4526 calls 8580 eliminations Puzzle #5: 1 solution found in 7.063s Unwinds: 1307 Single Candidature: 52935 calls Locked Sector Candidates: 6032 calls 6640 eliminations Disjoint Subsets: 2907 calls 5082 eliminations Puzzle #6: 1 solution found in 0.672s Unwinds: 108 Single Candidature: 5268 calls Locked Sector Candidates: 525 calls 740 eliminations Disjoint Subsets: 230 calls 574 eliminations Puzzle #7: 1 solution found in 1.938s Unwinds: 393 Single Candidature: 15771 calls Locked Sector Candidates: 1749 calls 2135 eliminations Disjoint Subsets: 767 calls 1440 eliminations Puzzle #8: 1 solution found in 0.500s Unwinds: 89 Single Candidature: 4320 calls Locked Sector Candidates: 515 calls 829 eliminations Disjoint Subsets: 191 calls 481 eliminations Puzzle #9: 1 solution found in 1.672s Unwinds: 304 Single Candidature: 13118 calls Locked Sector Candidates: 1283 calls 1517 eliminations Disjoint Subsets: 570 calls 1034 eliminations Puzzle #10: 1 solution found in 1.438s Unwinds: 220 Single Candidature: 9800 calls Locked Sector Candidates: 1138 calls 1420 eliminations Disjoint Subsets: 500 calls 1233 eliminations Puzzle #11: 1 solution found in 1.156s Unwinds: 211 Single Candidature: 9183 calls Locked Sector Candidates: 985 calls 1401 eliminations Disjoint Subsets: 414 calls 908 eliminations Puzzle #12: 1 solution found in 0.984s Unwinds: 179 Single Candidature: 7680 calls Locked Sector Candidates: 791 calls 962 eliminations Disjoint Subsets: 367 calls 848 eliminations Puzzle #13: 1 solution found in 1.797s Unwinds: 298 Single Candidature: 13589 calls Locked Sector Candidates: 1919 calls 2723 eliminations Disjoint Subsets: 717 calls 1868 eliminations Puzzle #14: 1 solution found in 1.547s Unwinds: 288 Single Candidature: 12239 calls Locked Sector Candidates: 1368 calls 1501 eliminations Disjoint Subsets: 626 calls 1349 eliminations Puzzle #15: 1 solution found in 5.797s Unwinds: 1092 Single Candidature: 43108 calls Locked Sector Candidates: 4740 calls 5731 eliminations Disjoint Subsets: 2388 calls 6238 eliminations Puzzle #16: 1 solution found in 0.641s Unwinds: 90 Single Candidature: 4653 calls Locked Sector Candidates: 669 calls 805 eliminations Disjoint Subsets: 312 calls 885 eliminations Puzzle #17: 1 solution found in 4.343s Unwinds: 868 Single Candidature: 33654 calls Locked Sector Candidates: 4123 calls 5086 eliminations Disjoint Subsets: 1889 calls 4149 eliminations Puzzle #18: 1 solution found in 2.922s Unwinds: 515 Single Candidature: 22873 calls Locked Sector Candidates: 2304 calls 2727 eliminations Disjoint Subsets: 1084 calls 2044 eliminations Puzzle #19: 1 solution found in 1.563s Unwinds: 316 Single Candidature: 12753 calls Locked Sector Candidates: 1237 calls 1508 eliminations Disjoint Subsets: 630 calls 1241 eliminations Puzzle #20: 1 solution found in 0.875s Unwinds: 162 Single Candidature: 7264 calls Locked Sector Candidates: 582 calls 713 eliminations Disjoint Subsets: 284 calls 503 eliminations Puzzle #21: 1 solution found in 1.797s Unwinds: 319 Single Candidature: 14649 calls Locked Sector Candidates: 1777 calls 2561 eliminations Disjoint Subsets: 646 calls 1388 eliminations Puzzle #22: 1 solution found in 0.718s Unwinds: 134 Single Candidature: 5826 calls Locked Sector Candidates: 696 calls 909 eliminations Disjoint Subsets: 270 calls 685 eliminations Puzzle #23: 1 solution found in 4.688s Unwinds: 785 Single Candidature: 33756 calls Locked Sector Candidates: 4057 calls 5918 eliminations Disjoint Subsets: 1646 calls 3830 eliminations Puzzle #24: 1 solution found in 3.641s Unwinds: 651 Single Candidature: 28600 calls Locked Sector Candidates: 3110 calls 4093 eliminations Disjoint Subsets: 1458 calls 4725 eliminations Puzzle #25: 1 solution found in 3.281s Unwinds: 589 Single Candidature: 24899 calls Locked Sector Candidates: 2941 calls 4178 eliminations Disjoint Subsets: 1168 calls 2895 eliminations Puzzle #26: 1 solution found in 1.922s Unwinds: 332 Single Candidature: 15133 calls Locked Sector Candidates: 1545 calls 2209 eliminations Disjoint Subsets: 644 calls 1449 eliminations Puzzle #27: 1 solution found in 0.672s Unwinds: 101 Single Candidature: 4552 calls Locked Sector Candidates: 623 calls 917 eliminations Disjoint Subsets: 233 calls 675 eliminations Puzzle #28: 1 solution found in 0.453s Unwinds: 78 Single Candidature: 3801 calls Locked Sector Candidates: 388 calls 470 eliminations Disjoint Subsets: 178 calls 415 eliminations Puzzle #29: 1 solution found in 2.578s Unwinds: 464 Single Candidature: 20475 calls Locked Sector Candidates: 1945 calls 2331 eliminations Disjoint Subsets: 953 calls 2167 eliminations Puzzle #30: 1 solution found in 2.188s Unwinds: 379 Single Candidature: 16293 calls Locked Sector Candidates: 2219 calls 3075 eliminations Disjoint Subsets: 816 calls 1949 eliminations Puzzle #31: 1 solution found in 1.906s Unwinds: 334 Single Candidature: 13051 calls Locked Sector Candidates: 1960 calls 3024 eliminations Disjoint Subsets: 810 calls 2657 eliminations Puzzle #32: 1 solution found in 1.031s Unwinds: 194 Single Candidature: 8275 calls Locked Sector Candidates: 812 calls 1077 eliminations Disjoint Subsets: 349 calls 641 eliminations Puzzle #33: 1 solution found in 4.938s Unwinds: 738 Single Candidature: 31756 calls Locked Sector Candidates: 4609 calls 7751 eliminations Disjoint Subsets: 1690 calls 5092 eliminations Puzzle #34: 1 solution found in 1.093s Unwinds: 183 Single Candidature: 8254 calls Locked Sector Candidates: 947 calls 1291 eliminations Disjoint Subsets: 381 calls 759 eliminations Puzzle #35: 1 solution found in 3.610s Unwinds: 653 Single Candidature: 28589 calls Locked Sector Candidates: 3354 calls 4951 eliminations Disjoint Subsets: 1383 calls 3077 eliminations Puzzle #36: 1 solution found in 1.172s Unwinds: 181 Single Candidature: 8511 calls Locked Sector Candidates: 997 calls 1642 eliminations Disjoint Subsets: 378 calls 863 eliminations Puzzle #37: 1 solution found in 4.140s Unwinds: 696 Single Candidature: 30699 calls Locked Sector Candidates: 3552 calls 5233 eliminations Disjoint Subsets: 1516 calls 3542 eliminations Puzzle #38: 1 solution found in 1.469s Unwinds: 218 Single Candidature: 9888 calls Locked Sector Candidates: 1432 calls 2284 eliminations Disjoint Subsets: 563 calls 1616 eliminations Puzzle #39: 1 solution found in 0.422s Unwinds: 81 Single Candidature: 3518 calls Locked Sector Candidates: 345 calls 383 eliminations Disjoint Subsets: 180 calls 576 eliminations Puzzle #40: 1 solution found in 0.797s Unwinds: 145 Single Candidature: 6139 calls Locked Sector Candidates: 626 calls 733 eliminations Disjoint Subsets: 321 calls 715 eliminations Puzzle #41: 1 solution found in 1.234s Unwinds: 201 Single Candidature: 10012 calls Locked Sector Candidates: 1219 calls 1615 eliminations Disjoint Subsets: 486 calls 951 eliminations Puzzle #42: 1 solution found in 4.422s Unwinds: 804 Single Candidature: 31775 calls Locked Sector Candidates: 3952 calls 5249 eliminations Disjoint Subsets: 1691 calls 3277 eliminations Puzzle #43: 1 solution found in 5.469s Unwinds: 885 Single Candidature: 38181 calls Locked Sector Candidates: 5293 calls 7816 eliminations Disjoint Subsets: 2089 calls 6198 eliminations Puzzle #44: 1 solution found in 3.203s Unwinds: 562 Single Candidature: 23866 calls Locked Sector Candidates: 2658 calls 3030 eliminations Disjoint Subsets: 1391 calls 3299 eliminations _________________ Java 5.0 Solver/Composer Applet: http://act365.com/sudoku GPL Source Code: http://sf.net/projects/sudoku Back to top dukuso Joined: 14 Jul 2005 Posts: 424 : Location: germany Items Posted: Fri Nov 04, 2005 4:31 am    Post subject: thanks. We have only small correlation of less than 0.1 So what's hard for one of us is often only average for the other. At least for these 44. Can some others add their timings for the 44 ? xyzzy ? Back to top frisch Joined: 16 Nov 2005 Posts: 55 : Location: Paris, France Items Posted: Wed Nov 16, 2005 3:37 pm    Post subject: dukuso wrote: thanks. Can some others add their timings for the 44 ? xyzzy ? Hello, I started implementing my own solver in Objective Caml. Here are the timings for the 44 16x16 puzzles: Puzzle #1 : 2.139449 Puzzle #2 : 1.799821 Puzzle #3 : 1.629330 Puzzle #4 : 5.230866 Puzzle #5 : 3.399682 Puzzle #6 : 1.473732 Puzzle #7 : 1.053263 Puzzle #8 : 1.365327 Puzzle #9 : 1.158942 Puzzle #10 : 5.538775 Puzzle #11 : 2.713385 Puzzle #12 : 4.421679 Puzzle #13 : 2.228177 Puzzle #14 : 0.807142 Puzzle #15 : 5.685518 Puzzle #16 : 1.065917 Puzzle #17 : 2.115596 Puzzle #18 : 2.019362 Puzzle #19 : 0.541237 Puzzle #20 : 0.307445 Puzzle #21 : 1.167909 Puzzle #22 : 2.025859 Puzzle #23 : 1.255290 Puzzle #24 : 2.578237 Puzzle #25 : 1.274635 Puzzle #26 : 1.066506 Puzzle #27 : 0.297509 Puzzle #28 : 0.339485 Puzzle #29 : 1.122464 Puzzle #30 : 2.413098 Puzzle #31 : 3.338550 Puzzle #32 : 1.918564 Puzzle #33 : 1.258575 Puzzle #34 : 0.912666 Puzzle #35 : 1.431445 Puzzle #36 : 0.768451 Puzzle #37 : 2.704529 Puzzle #38 : 0.909053 Puzzle #39 : 0.703783 Puzzle #40 : 0.626426 Puzzle #41 : 1.125610 Puzzle #42 : 1.315709 Puzzle #43 : 1.196817 Puzzle #44 : 1.590050 These are wall-clock times for computing all the solutions, running on an Intel Pentium 4 2.80 GHZ. -- Alain Back to top dukuso Joined: 14 Jul 2005 Posts: 424 : Location: germany Items Posted: Wed Nov 16, 2005 6:18 pm    Post subject: thanks. I assume only finding the solution is about twice as fast as completely searching the searchtree. We have correlation 0.48 , quite high. I will study your method from your webpage. But then, I don't know my own method yet... I didn't yet post my timings, so here is the average over 10 randomized runs: 2963229 2750725 2267642 2369159 2472734 2075290 2219133 1887084 1815952 2838847 1797424 1876477 1981727 1346576 1942310 2042878 1756983 1788441 1590887 1562504 1490384 1938041 1873084 1544781 1419448 1665687 1554791 1276454 1751161 1641792 1254190 1541687 1091189 1188271 1261870 1101214 1617334 1619304 1435307 1598698 1424517 1062207 1524803 1450818 these are nodecounts, which is easier to measure. Total time is about 25sec. with 2.6GHz , complete search. See also the "nodes per second"- thread in the programmer's forum for more timings. -Guenter Back to top dukuso Joined: 14 Jul 2005 Posts: 424 : Location: germany Items Posted: Thu Nov 17, 2005 5:24 am    Post subject: correlation coefficients of the timings are: Code:   | AL D1 D2 RU | time in Mcycles --+-------------+-------------- AL| 99 48 15 50 | 205000 D2| 48 99 47 17 | 65000 D1| 15 47 99 06 | 500000 RU| 50 17 06 99 | 280000(?) ----------------+---------------- D1,D2 are average timings over 10 or 100 randomized runs with my old,new version Back to top gsf Joined: 18 Aug 2005 Posts: 411 : Location: NJ USA Items Posted: Tue Nov 29, 2005 8:29 am    Post subject: dukuso wrote: Can some others add their timings for the 44 ? xyzzy ? I finally got around to coding for N instead of 9. Here are my top44 times/guesses/puzzle# on a 2.8Ghz p4: Code: 0.227966      243 1 0.258960      261 2 0.104984       88 3 0.168975      128 4 0.073988       51 5 1.993697     1768 6 0.208969      220 7 0.629904      581 8 0.059991       59 9 0.243962      190 10 0.146978      131 11 0.175973      166 12 0.328950      260 13 0.013998       12 14 0.151977      114 15 0.161975      118 16 0.148978      148 17 0.012998        9 18 0.113982       85 19 0.051992       65 20 0.097985       87 21 0.267960      276 22 0.194970      143 23 0.063990       56 24 0.086987       70 25 0.020997       19 26 0.150978      138 27 0.026995       20 28 0.205969      194 29 0.152977      105 30 0.568913      440 31 0.071989       54 32 0.155977      141 33 0.137979      114 34 0.152976      128 35 0.083988       64 36 0.286956      196 37 0.180972      169 38 0.368944      285 39 0.010998        7 40 0.014998       10 41 0.048993       36 42 0.359945      279 43 0.255961      234 44 2/s/GHz GC 18.5 C/n 2325946 puzzles 44 seconds 9.259592 nodes 7962 Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         Sudoku Programmers Forum Index -> Puzzles All times are GMT Goto page 1, 2  Next Page 1 of 2   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