User:Heiner
From Sokoban Wiki
Hello Sokoban-Fans!
Contents |
About me
While I also have written a sokoban solver program, it is not the usual kind, that tries hard to find some solution at all, but I rather restrict to brute force methods, i.e. I only generate push-optimal solutions.
Also, no graphics.
Sometime I will publish the program (written in C), but currently I do not yet feel so.
My personal home page is: http://www.drb.insel.de/~heiner
I'm living in: Berlin, Germany.
Wanted
- A reference or link to "Edelkamp's work", as mentioned in Sokoban solver "scribbles" by Brian Damgaard about the YASS solver
Answer: http://www.tzi.de/~edelkamp/publications/ - A reference or link to explicitly push-optimal move numbers (that is not the same as a world record)
I don't know if such a link exists. However, the world records at sokobano.de are push optimal for most of the (small to middle size) levels. For small levels you can use a solver like JSoko which can solve easy levels push optimal to compare the results.
Results for Microban
Since I'm not yet sure how that will look like in the end, as an experiment I show my current results of Microban (from Skinner). All but one (153) are solved:
Level 001 from Microban : 33 moves, 8 pushes Level 002 from Microban : 16 moves, 3 pushes Level 003 from Microban : 41 moves, 13 pushes Level 004 from Microban : 31 moves, 7 pushes Level 005 from Microban : 31 moves, 6 pushes Level 006 from Microban : 107 moves, 29 pushes Level 007 from Microban : 38 moves, 6 pushes Level 008 from Microban : 113 moves, 32 pushes Level 009 from Microban : 30 moves, 10 pushes Level 010 from Microban : 91 moves, 21 pushes Level 011 from Microban : 80 moves, 16 pushes Level 012 from Microban : 49 moves, 11 pushes Level 013 from Microban : 63 moves, 21 pushes Level 014 from Microban : 55 moves, 10 pushes Level 015 from Microban : 43 moves, 12 pushes Level 016 from Microban : 110 moves, 39 pushes Level 017 from Microban : 27 moves, 9 pushes Level 018 from Microban : 73 moves, 13 pushes Level 019 from Microban : 41 moves, 20 pushes Level 020 from Microban : 50 moves, 16 pushes Level 021 from Microban : 17 moves, 5 pushes Level 022 from Microban : 47 moves, 15 pushes Level 023 from Microban : 56 moves, 10 pushes Level 024 from Microban : 35 moves, 9 pushes Level 025 from Microban : 33 moves, 7 pushes Level 026 from Microban : 42 moves, 10 pushes Level 027 from Microban : 50 moves, 10 pushes Level 028 from Microban : 33 moves, 9 pushes Level 029 from Microban : 108 moves, 22 pushes Level 030 from Microban : 21 moves, 5 pushes Level 031 from Microban : 17 moves, 6 pushes Level 032 from Microban : 35 moves, 9 pushes Level 033 from Microban : 49 moves, 10 pushes Level 034 from Microban : 39 moves, 8 pushes Level 035 from Microban : 96 moves, 31 pushes Level 036 from Microban : 200 moves, 59 pushes Level 037 from Microban : 73 moves, 23 pushes Level 038 from Microban : 37 moves, 8 pushes Level 039 from Microban : 93 moves, 27 pushes Level 040 from Microban : 22 moves, 7 pushes Level 041 from Microban : 60 moves, 13 pushes Level 042 from Microban : 70 moves, 15 pushes Level 043 from Microban : 63 moves, 22 pushes Level 044 from Microban : 1 moves, 1 pushes Level 045 from Microban : 49 moves, 11 pushes Level 046 from Microban : 47 moves, 8 pushes Level 047 from Microban : 83 moves, 22 pushes Level 048 from Microban : 67 moves, 14 pushes Level 049 from Microban : 100 moves, 21 pushes Level 050 from Microban : 80 moves, 17 pushes Level 051 from Microban : 34 moves, 8 pushes Level 052 from Microban : 29 moves, 8 pushes Level 053 from Microban : 37 moves, 12 pushes Level 054 from Microban : 94 moves, 30 pushes Level 055 from Microban : 72 moves, 27 pushes Level 056 from Microban : 23 moves, 6 pushes Level 057 from Microban : 66 moves, 23 pushes Level 058 from Microban : 44 moves, 11 pushes Level 059 from Microban : 185 moves, 50 pushes Level 060 from Microban : 169 moves, 44 pushes Level 061 from Microban : 100 moves, 21 pushes Level 062 from Microban : 68 moves, 30 pushes Level 063 from Microban : 115 moves, 50 pushes Level 064 from Microban : 99 moves, 30 pushes Level 065 from Microban : 170 moves, 41 pushes Level 066 from Microban : 95 moves, 15 pushes Level 067 from Microban : 37 moves, 8 pushes Level 068 from Microban : 98 moves, 28 pushes Level 069 from Microban : 144 moves, 37 pushes Level 070 from Microban : 78 moves, 26 pushes Level 071 from Microban : 120 moves, 21 pushes Level 072 from Microban : 115 moves, 40 pushes Level 073 from Microban : 116 moves, 25 pushes Level 074 from Microban : 123 moves, 34 pushes Level 075 from Microban : 94 moves, 34 pushes Level 076 from Microban : 201 moves, 56 pushes Level 077 from Microban : 201 moves, 55 pushes Level 078 from Microban : 147 moves, 33 pushes Level 079 from Microban : 56 moves, 18 pushes Level 080 from Microban : 135 moves, 38 pushes Level 081 from Microban : 46 moves, 12 pushes Level 082 from Microban : 52 moves, 14 pushes Level 083 from Microban : 188 moves, 47 pushes Level 084 from Microban : 243 moves, 68 pushes Level 085 from Microban : 159 moves, 51 pushes Level 086 from Microban : 119 moves, 25 pushes Level 087 from Microban : 155 moves, 53 pushes Level 088 from Microban : 217 moves, 63 pushes Level 089 from Microban : 147 moves, 35 pushes Level 090 from Microban : 71 moves, 16 pushes Level 091 from Microban : 50 moves, 14 pushes Level 092 from Microban : 152 moves, 48 pushes Level 093 from Microban : 111 moves, 34 pushes Level 094 from Microban : 87 moves, 29 pushes Level 095 from Microban : 25 moves, 8 pushes Level 096 from Microban : 102 moves, 37 pushes Level 097 from Microban : 164 moves, 41 pushes Level 098 from Microban : 281 moves, 110 pushes Level 099 from Microban : 373 moves, 131 pushes Level 100 from Microban : 183 moves, 52 pushes Level 101 from Microban : 79 moves, 15 pushes Level 102 from Microban : 170 moves, 44 pushes Level 103 from Microban : 39 moves, 12 pushes Level 104 from Microban : 101 moves, 27 pushes Level 105 from Microban : 83 moves, 24 pushes Level 106 from Microban : 259 moves, 50 pushes Level 107 from Microban : 42 moves, 10 pushes Level 108 from Microban : 256 moves, 68 pushes Level 109 from Microban : 215 moves, 42 pushes Level 110 from Microban : 99 moves, 14 pushes Level 111 from Microban : 184 moves, 61 pushes Level 112 from Microban : 287 moves, 94 pushes Level 113 from Microban : 206 moves, 51 pushes Level 114 from Microban : 323 moves, 60 pushes Level 115 from Microban : 209 moves, 29 pushes Level 116 from Microban : 78 moves, 14 pushes Level 117 from Microban : 278 moves, 47 pushes Level 118 from Microban : 196 moves, 44 pushes Level 119 from Microban : 145 moves, 18 pushes Level 120 from Microban : 217 moves, 64 pushes Level 121 from Microban : 159 moves, 47 pushes Level 122 from Microban : 287 moves, 90 pushes Level 123 from Microban : 372 moves, 101 pushes Level 124 from Microban : 245 moves, 39 pushes Level 125 from Microban : 131 moves, 38 pushes Level 126 from Microban : 120 moves, 23 pushes Level 127 from Microban : 136 moves, 32 pushes Level 128 from Microban : 94 moves, 19 pushes Level 129 from Microban : 126 moves, 22 pushes Level 130 from Microban : 114 moves, 36 pushes Level 131 from Microban : 84 moves, 31 pushes Level 132 from Microban : 165 moves, 37 pushes Level 133 from Microban : 161 moves, 39 pushes Level 134 from Microban : 340 moves, 76 pushes Level 135 from Microban : 165 moves, 36 pushes Level 136 from Microban : 146 moves, 25 pushes Level 137 from Microban : 195 moves, 46 pushes Level 138 from Microban : 215 moves, 54 pushes Level 139 from Microban : 368 moves, 106 pushes Level 140 from Microban : 330 moves, 80 pushes Level 141 from Microban : 149 moves, 52 pushes Level 142 from Microban : 84 moves, 20 pushes Level 143 from Microban : 262 moves, 65 pushes Level 144 from Microban : 166 moves, 36 pushes Level 145 from Microban : 81 moves, 18 pushes Level 146 from Microban : 51 moves, 14 pushes Level 147 from Microban : 156 moves, 50 pushes Level 148 from Microban : 208 moves, 49 pushes Level 149 from Microban : 100 moves, 35 pushes Level 150 from Microban : 179 moves, 43 pushes Level 151 from Microban : 137 moves, 50 pushes Level 152 from Microban : 297 moves, 35 pushes Level 153 from Microban : -- moves, -- pushes Level 154 from Microban : 429 moves, 2 pushes Level 155 from Microban : 282 moves, 175 pushes
Note that all push numbers are optimal (minimal).
Results for Yoshio's Handmade
Level 001 from Yoshio's Handmade : 154 moves, 48 pushes Level 002 from Yoshio's Handmade : 100 moves, 17 pushes Level 003 from Yoshio's Handmade : 115 moves, 14 pushes Level 004 from Yoshio's Handmade : 84 moves, 11 pushes Level 005 from Yoshio's Handmade : 85 moves, 16 pushes Level 006 from Yoshio's Handmade : 76 moves, 16 pushes Level 007 from Yoshio's Handmade : 59 moves, 10 pushes Level 008 from Yoshio's Handmade : -- moves, -- pushes Level 009 from Yoshio's Handmade : 142 moves, 22 pushes Level 010 from Yoshio's Handmade : 43 moves, 14 pushes Level 011 from Yoshio's Handmade : 101 moves, 12 pushes Level 012 from Yoshio's Handmade : 69 moves, 20 pushes Level 013 from Yoshio's Handmade : -- moves, -- pushes Level 014 from Yoshio's Handmade : 225 moves, 47 pushes Level 015 from Yoshio's Handmade : 51 moves, 16 pushes Level 016 from Yoshio's Handmade : 66 moves, 17 pushes Level 017 from Yoshio's Handmade : 89 moves, 25 pushes Level 018 from Yoshio's Handmade : 178 moves, 51 pushes Level 019 from Yoshio's Handmade : 155 moves, 29 pushes Level 020 from Yoshio's Handmade : 199 moves, 45 pushes Level 021 from Yoshio's Handmade : 190 moves, 45 pushes Level 022 from Yoshio's Handmade : 179 moves, 35 pushes Level 023 from Yoshio's Handmade : 95 moves, 26 pushes Level 024 from Yoshio's Handmade : 119 moves, 24 pushes Level 025 from Yoshio's Handmade : 139 moves, 30 pushes Level 026 from Yoshio's Handmade : 129 moves, 33 pushes Level 027 from Yoshio's Handmade : 176 moves, 43 pushes Level 028 from Yoshio's Handmade : 143 moves, 24 pushes Level 029 from Yoshio's Handmade : 441 moves, 84 pushes Level 030 from Yoshio's Handmade : 93 moves, 25 pushes Level 031 from Yoshio's Handmade : 263 moves, 54 pushes Level 032 from Yoshio's Handmade : 145 moves, 28 pushes Level 033 from Yoshio's Handmade : 198 moves, 37 pushes Level 035 from Yoshio's Handmade : 344 moves, 61 pushes Level 036 from Yoshio's Handmade : 182 moves, 40 pushes Level 037 from Yoshio's Handmade : 117 moves, 21 pushes Level 038 from Yoshio's Handmade : 134 moves, 21 pushes Level 039 from Yoshio's Handmade : 126 moves, 18 pushes Level 040 from Yoshio's Handmade : 69 moves, 16 pushes Level 041 from Yoshio's Handmade : 188 moves, 28 pushes Level 042 from Yoshio's Handmade : 164 moves, 34 pushes Level 043 from Yoshio's Handmade : 210 moves, 33 pushes Level 044 from Yoshio's Handmade : 132 moves, 32 pushes Level 045 from Yoshio's Handmade : 273 moves, 35 pushes Level 046 from Yoshio's Handmade : 374 moves, 60 pushes Level 047 from Yoshio's Handmade : 139 moves, 30 pushes Level 048 from Yoshio's Handmade : 141 moves, 19 pushes Level 049 from Yoshio's Handmade : 120 moves, 26 pushes Level 050 from Yoshio's Handmade : 171 moves, 17 pushes Level 051 from Yoshio's Handmade : 228 moves, 34 pushes Level 052 from Yoshio's Handmade : 88 moves, 23 pushes Level 053 from Yoshio's Handmade : 72 moves, 12 pushes
My program seems to solve 2 levels, which JSoko does not solve: 27 and 29. Ha!
Results for SokHard
This is for "SokHard" from Lee J Haywood.
I'm using a "AMD Sempron(tm) Processor 3000+" CPU with 2GB memory.
Sokoban solver by Heiner Marxen, rev 710 from 2010-11-27 on 'k4' Level 0001: 52 pushes, 183 moves, 1.832 secs Level 0002: 92 pushes, 340 moves, 7.875 secs Level 0003: 92 pushes, 346 moves, 8.546 secs Level 0004: 57 pushes, 210 moves, 5.897 secs Level 0005: 84 pushes, 307 moves, 1.695 secs Level 0006: 90 pushes, 339 moves, 9.705 secs Level 0007: 83 pushes, 271 moves, 3.981 secs Level 0008: 65 pushes, 303 moves, 11.851 secs Level 0009: 103 pushes, 427 moves, 7.700 secs Level 0010: 97 pushes, 447 moves, 10.217 secs Level 0011: 158 pushes, 618 moves, 3.616 secs Level 0012: 138 pushes, 450 moves, 19.952 secs Level 0013: 126 pushes, 623 moves, 10.790 secs Level 0014: 93 pushes, 457 moves, 10.213 secs Level 0015: 86 pushes, 300 moves, 0.983 secs Level 0016: 94 pushes, 396 moves, 3.885 secs Level 0017: 97 pushes, 687 moves, 3.792 secs Level 0018: 110 pushes, 465 moves, 1.238 secs Level 0019: 88 pushes, 281 moves, 3.540 secs Level 0020: 65 pushes, 332 moves, 0.988 secs Level 0021: 143 pushes, 554 moves, 17.114 secs Level 0022: 67 pushes, 277 moves, 0.136 secs Level 0023: 129 pushes, 586 moves, 2.443 secs Level 0024: 91 pushes, 356 moves, 2.363 secs Level 0025: 96 pushes, 467 moves, 3.161 secs Level 0026: 120 pushes, 468 moves, 15.750 secs Level 0027: 157 pushes, 657 moves, 6.874 secs Level 0028: 70 pushes, 227 moves, 3.810 secs Level 0029: 115 pushes, 522 moves, 27.083 secs Level 0030: 60 pushes, 245 moves, 1.538 secs Level 0031: 59 pushes, 202 moves, 4.543 secs Level 0032: 66 pushes, 210 moves, 17.716 secs Level 0033: 118 pushes, 290 moves, 1.585 secs Level 0034: 101 pushes, 398 moves, 6.666 secs Level 0035: 140 pushes, 634 moves, 19.398 secs Level 0036: 117 pushes, 488 moves, 13.979 secs Level 0037: 81 pushes, 351 moves, 3.908 secs Level 0038: 73 pushes, 213 moves, 0.038 secs Level 0039: 83 pushes, 329 moves, 20.182 secs Level 0040: 102 pushes, 462 moves, 2.336 secs Level 0041: 102 pushes, 376 moves, 12.958 secs Level 0042: 89 pushes, 295 moves, 12.221 secs Level 0043: 114 pushes, 323 moves, 20.423 secs Level 0044: 98 pushes, 339 moves, 39.697 secs Level 0045: 97 pushes, 384 moves, 16.496 secs Level 0046: 81 pushes, 312 moves, 6.825 secs Level 0047: 106 pushes, 513 moves, 10.717 secs Level 0048: 108 pushes, 400 moves, 26.759 secs Level 0049: 111 pushes, 415 moves, 18.672 secs Level 0050: 86 pushes, 359 moves, 3.212 secs Level 0051: 87 pushes, 311 moves, 5.540 secs Level 0052: 144 pushes, 655 moves, 21.163 secs Level 0053: 66 pushes, 289 moves, 0.185 secs Level 0054: 87 pushes, 345 moves, 0.062 secs Level 0055: 105 pushes, 345 moves, 4.565 secs Level 0056: 112 pushes, 519 moves, 11.751 secs Level 0057: 108 pushes, 410 moves, 17.914 secs Level 0058: 99 pushes, 324 moves, 9.449 secs Level 0059: 101 pushes, 421 moves, 9.886 secs Level 0060: 107 pushes, 487 moves, 4.320 secs Level 0061: 116 pushes, 399 moves, 7.826 secs Level 0062: 101 pushes, 382 moves, 8.273 secs Level 0063: 128 pushes, 678 moves, 36.673 secs Level 0064: 136 pushes, 564 moves, 18.005 secs Level 0065: 98 pushes, 342 moves, 19.013 secs Level 0066: 97 pushes, 365 moves, 50.894 secs Level 0067: 135 pushes, 513 moves, 97.649 secs Level 0068: 171 pushes, 769 moves, 32.013 secs Level 0069: 111 pushes, 498 moves, 10.281 secs Level 0070: 144 pushes, 652 moves, 25.484 secs Level 0071: 121 pushes, 473 moves, 19.158 secs Level 0072: 145 pushes, 535 moves, 20.049 secs Level 0073: 124 pushes, 416 moves, 7.952 secs Level 0074: 139 pushes, 721 moves, 43.453 secs Level 0075: 122 pushes, 641 moves, 61.140 secs Level 0076: 156 pushes, 413 moves, 28.403 secs Level 0077: 119 pushes, 626 moves, 14.118 secs Level 0078: 161 pushes, 656 moves, 68.049 secs Level 0079: 193 pushes, 620 moves, 25.249 secs Level 0080: 154 pushes, 405 moves, 34.492 secs Level 0081: 161 pushes, 780 moves, 45.860 secs Level 0082: 132 pushes, 531 moves, 39.225 secs Level 0083: 187 pushes, 648 moves, 37.763 secs Level 0084: 136 pushes, 562 moves, 49.590 secs Level 0085: 200 pushes, 785 moves, 69.868 secs Level 0086: 156 pushes, 425 moves, 44.080 secs Level 0087: 108 pushes, 609 moves, 4.262 secs Level 0088: 253 pushes, 625 moves, 35.509 secs Level 0089: 123 pushes, 467 moves, 79.907 secs Level 0090: 128 pushes, 659 moves, 5.034 secs Level 0091: 134 pushes, 536 moves, 21.291 secs Level 0092: 135 pushes, 608 moves, 26.530 secs Level 0093: 119 pushes, 532 moves, 5.874 secs Level 0094: 135 pushes, 487 moves, 27.966 secs Level 0095: 128 pushes, 484 moves, 0.621 secs Level 0096: 174 pushes, 710 moves, 36.980 secs Level 0097: 135 pushes, 612 moves, 18.929 secs Level 0098: 132 pushes, 464 moves, 32.632 secs Level 0099: 142 pushes, 506 moves, 78.237 secs Level 0100: 131 pushes, 509 moves, 70.590 secs Level 0101: 130 pushes, 586 moves, 25.356 secs Level 0102: 227 pushes, 830 moves, 0.520 secs Level 0103: 185 pushes, 697 moves, 55.268 secs Level 0104: 176 pushes, 530 moves, 13.027 secs Level 0105: 136 pushes, 572 moves, 45.542 secs Level 0106: 170 pushes, 554 moves, 26.205 secs Level 0107: 161 pushes, 535 moves, 9.841 secs Level 0108: 142 pushes, 527 moves, 240.923 secs Level 0109: 156 pushes, 489 moves, 23.135 secs Level 0110: 157 pushes, 501 moves, 23.014 secs Level 0111: 220 pushes, 1068 moves, 31.895 secs Level 0112: 117 pushes, 414 moves, 62.268 secs Level 0113: 164 pushes, 796 moves, 66.607 secs Level 0114: 214 pushes, 646 moves, 129.324 secs Level 0115: 132 pushes, 388 moves, 28.442 secs Level 0116: 174 pushes, 569 moves, 55.582 secs Level 0117: 203 pushes, 602 moves, 91.452 secs Level 0118: 149 pushes, 433 moves, 16.520 secs Level 0119: 205 pushes, 612 moves, 21.799 secs Level 0120: 121 pushes, 622 moves, 9.686 secs Level 0121: 148 pushes, 541 moves, 54.392 secs Level 0122: 238 pushes, 804 moves, 46.657 secs Level 0123: 262 pushes, 680 moves, 3.727 secs Level 0124: 128 pushes, 415 moves, 33.965 secs Level 0125: 230 pushes, 762 moves, 31.126 secs Level 0126: 138 pushes, 572 moves, 54.087 secs Level 0127: 209 pushes, 711 moves, 65.700 secs Level 0128: 148 pushes, 512 moves, 22.068 secs Level 0129: 92 pushes, 324 moves, 36.799 secs Level 0130: 155 pushes, 751 moves, 22.344 secs Level 0131: 185 pushes, 520 moves, 34.880 secs Level 0132: 150 pushes, 511 moves, 68.311 secs Level 0133: 189 pushes, 543 moves, 51.863 secs Level 0134: 195 pushes, 705 moves, 85.552 secs Level 0135: 239 pushes, 686 moves, 135.244 secs Level 0136: 148 pushes, 611 moves, 56.017 secs Level 0137: 189 pushes, 741 moves, 109.157 secs Level 0138: 133 pushes, 638 moves, 25.794 secs Level 0139: 185 pushes, 656 moves, 31.997 secs Level 0140: 113 pushes, 619 moves, 19.637 secs Level 0141: 145 pushes, 965 moves, 37.848 secs Level 0142: 122 pushes, 624 moves, 57.038 secs Level 0143: 188 pushes, 924 moves, 107.798 secs Level 0144: 150 pushes, 718 moves, 74.729 secs Level 0145: 169 pushes, 619 moves, 21.331 secs Level 0146: 141 pushes, 726 moves, 53.287 secs Level 0147: 177 pushes, 617 moves, 113.521 secs Level 0148: 125 pushes, 647 moves, 52.149 secs Level 0149: 142 pushes, 540 moves, 61.652 secs Level 0150: 135 pushes, 433 moves, 36.507 secs Level 0151: 138 pushes, 650 moves, 33.089 secs Level 0152: 176 pushes, 652 moves, 113.336 secs Level 0153: 184 pushes, 1010 moves, 58.335 secs Level 0154: 177 pushes, 811 moves, 66.000 secs Level 0155: 161 pushes, 698 moves, 44.756 secs Level 0156: 181 pushes, 850 moves, 45.932 secs Level 0157: 178 pushes, 606 moves, 16.584 secs Level 0158: 154 pushes, 519 moves, 28.793 secs Level 0159: 159 pushes, 638 moves, 26.328 secs Level 0160: 187 pushes, 740 moves, 97.628 secs Level 0161: 117 pushes, 496 moves, 12.868 secs Level 0162: 198 pushes, 882 moves, 28.519 secs Level 0163: 108 pushes, 420 moves, 13.243 secs Level 0164: 240 pushes, 762 moves, 191.664 secs Level 0165: 213 pushes, 732 moves, 42.460 secs Level 0166: 189 pushes, 648 moves, 82.824 secs Level 0167: 150 pushes, 504 moves, 31.710 secs Level 0168: 150 pushes, 637 moves, 56.101 secs Level 0169: 105 pushes, 623 moves, 6.982 secs
All pushes are optimal, moves most probably are not. All levels are solved!
This kind of level seems to be especially good suited for a simple minded brute force solver like mine. JSoko does solve only 131 of the first 163 levels (see SolverStatistics-jsoko-LeeJHaywood-SokHard), but the other tested solvers do solve them all (see Solver Statistics - Lee J Haywood).
