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 |
|
|
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 |
|
|
|