Eternity II


Thierry BENOIST


Results of my experiments on Edge-matching puzzles  

(instances and details available here)

Results as text file (CSV)


Legend and remarks
  • time are expressed in seconds
  • empty cells denotes instances that could not be solved in 6 hours
  • instances are sorted by increasing best time
  • doc_smith and mgaillard are implemented in C, all other approaches are in Java
instance time doc_smith nodes doc_smith time mgaillard nodes mgaillard time Basic CP O(1) [mindomain, nobackjumping, no preemptions] nodes basic CP O(1) [mindomain, nobackjumping, no preemptions] time CP O(1) [minExpectedGap, fullShaving, backjumping, preemptions, cycles and outboard reasoning] nodes CP O(1) [minExpectedGap, fullShaving, backjumping, preemptions, cycles and outboard reasoning] time choco nodes choco best
E_10_11.b13i13.nohint 9 271540494 1 3678223 43 11615782 11 1044779 632 18461 1
E_10_12.b12i13.nohint 5 168195416 1 1887284 30 7606573 11 1067398 1037 32908 1
E_10_14.b12i13.nohint 31 917950203 1 7457370 155 38810872 52 4880684 3024 104944 1
E_10_16.b13i13.nohint 38 1128900290 1 4857450 10 2399286 5 480001 303 9814 1
E_10_17.b13i13.nohint 58 1743889689 1 1208306 16 4188865 6 539572 239 7186 1
E_10_18.b12i13.nohint 66 1929542165 1 3544870 44 12308541 9 868019 365 10543 1
E_10_19.b12i13.nohint 98 2875279640 1 10459768 599 158436263 87 8534940 2505 89430 1
E_10_21.b12i13.nohint 125 3721763564 1 14429884 104 28876165 29 2896311 4369 227045 1
E_10_22.b12i13.nohint 431 12690295733 1 10717762 21 5358208 9 890692 827 28553 1
E_10_5.b14i14.nohint 1 31748898 1 713918 47 12765974 15 1479893 440 12429 1
E_10_7.b12i15.nohint 1 806428 1 137290 21 4937750 6 564451 159 3999 1
E_10_8.b13i14.nohint 2 67394984 1 3963921 87 22072499 14 1498835 785 22527 1
E_10_9.b12i14.nohint 7 195192536 1 3959180 103 26702880 22 2118716 722 21453 1
E_9_3.b11i12.nohint 2 56350848 1 1233161 27 6505733 10 1025727 428 22942 1
E_9_4.b9i12.nohint 4 96882028 1 1917013 16 4293544 8 721648 79 5017 1
E_9_5.b10i11.nohint 24 523018065 1 9821126 61 14794667 26 2668897 750 48995 1
E_9_7.b9i11.nohint 36 988372045 1 10866595 61 15869868 41 4069998 708 47204 1
E_10_20.b11i14.nohint 47 1392893514 2 34083879 609 162519790 123 11846490 3236 110221 2
E_9_11.b9i11.nohint 150 4228947704 2 32775719 34 7964009 23 2179866 1905 225173 2
E_10_23.b12i12.nohint 1350 39380686402 3 74495168 3048 832992440 205 19865599 11065 409029 3
E_9_13.b10i10.nohint 758 20684112187 3 56243052 32 8798886 12 1252767 521 41849 3
E_9_15.b10i10.nohint 1891 52409952366 3 70619424 1430 341560732 344 35259775 20904 1596401 3
E_9_12.b10i10.nohint 447 12352170813 4 94902710 45 10820155 22 2109816 4055 528110 4
E_10_25.b12i12.nohint 2318 66996375336 5 110297791 195 42357063 74 6988749 3521 128754 5
E_7_1.b6i6.nohint 133 3318269017 8 159156829 31 7709131 36 4735789 468 193257 8
E_9_17.b9i10.nohint 3012 82908945540 9 216833818 1694 424629719 431 44702425 9
E_9_14.b9i10.nohint 1083 29801039566 12 291918407 1021 268041634 666 71309759 16680 1297667 12
E_10_15.b11i12.nohint 13307 376459877889 13 318080240 1238 317353707 156 15305674 11825 536571 13
E_9_10.b10i10.nohint 41 990872978 54 13642362 13 1337142 544 42368 13
E_10_10.b12i12.nohint 11381 327799548129 14 353214300 1784 469211974 393 38084395 14870 615010 14
E_10_24.b12i12.nohint 4661 132809966916 15 378872909 8176 2085656267 445 44489252 15
E_7_2.b6i6.nohint 1359 32745333640 49 1076409667 17 4468569 23 2687319 319 128327 17
E_9_16.b9i10.nohint 6339 175486069872 25 602887224 2031 496546247 261 27324387 9347 796125 25
E_10_26.b12i12.nohint 11378 328733464444 36 939164352 15719 4064883837 1379 141628593 36
E_10_13.b12i12.nohint 37 955515541 1926 518583197 140 14174081 9199 343759 37
E_10_6.b11i12.nohint 7305 196633748564 37 1011078686 1832 442540031 782 77129277 37
E_8_1.b8i8.nohint 6710 180493609292 49 1145104722 150 38125818 109 13389315 2699 325613 49
E_7_3.b6i6.nohint 1467 35669199163 149 3236732494 752 193448046 710 98756071 16449 6534922 149
E_9_6.b9i10.nohint 254 6402918583 834 211565921 497 52921854 16687 1516445 254
E_9_1.b9i9.nohint 348 8595663887 13307 3399603704 4273 495456474 348
E_7_4.b6i6.nohint 9963 236946952617 753 16285381325 361 94163044 417 60503241 6003 2552861 361
E_10_3.b11i11.nohint 431 11181333004 1570 154666394 431
E_9_2.b9i9.nohint 646 15456611189 824 204799142 453 51867544 453
E_9_9.b9i10.nohint 674 17161111648 10059 2524500400 4852 503117825 674
E_10_4.b11i11.nohint 1157 29362268054 6474 1702461823 776 76977493 776
E_10_2.b11i11.nohint 2501 62178418868 6701 731670873 2501
E_9_8.b8i9.nohint 2609 62178639312 12328 2902661425 7812 852690261 2609
E_10_1.b11i11.nohint 9172 225669091765 4982 529442954 4982





ThierryBenoist-lastrevised14/05/2008