A sliding puzzle from Nob-Net: Torsten Sillke, FRA, 1998-09-20 Update FRA, 1998-09-28 o . . o . . . . . . . . --> . o o . . . . . . o o . o . . o . . . . Rule: contact sliding Each move (horizontal or vertical) must be as long as possible. That means until you reach the boarder or the next position is occupied. Notation: I lable the pieces and give the direction of the move behind them: u(p), d(own), l(eft), r(ight). Example: Adru means piece A moves first down and than right and up. Two different 12 move solutions: A . . D Br, A D . . Adru . D . . Dldru . . . . Cl, . . . . . . . . Cu, . . . C . A . C . A . C Bu . A C . . . . . Dl . . . . . . . . . D . . . D B . B . . C . . B . . . B . . . B . . . . . A . . D Br, A D . . Ad, . D . . Bu, . D . . Br, . . . . . . . . Dl . . . . Bl, . . . . Aru . B . . Dd, . D B . . . . . . . . . Cl . . . . . A . . Bl, . A C . B . . C . . B C A B C . . . C . Cu . . . . An extremal positions for 3 pieces (12 moves): A . . C Ard, Br, Au, Cdlu, . . . . . . . . Ardlu, Cr . . . C . . . . . . A . B . . . . B . . The 2n-square: Now try to move four coins from the corners of a 2n-square into the middle 2-square. An 8/3 n + O(1) scheme for the transformation (example n=6) line-up: 6 moves o . . . . . . . . . . o . . . . . . . . . . . . . . . --> . . . o . . . . . . . . . . o o o o o . . . . . . . . line-up + 1: 8 moves o . . . . . . . . . . o . . . . . . . . . . . . . . . --> . . . o . . . . . . . . . . o . o o o o . . . . . . . line-up + 2: 12 moves (this method is one above minimal) o . . . . . . . . . . o . . . . . . . . . . . . . . . --> . . . o . . . . . . . . . . o . . o o o o . . . . . . shift-right: 4(n-3) - 4 floor(n/3 - 1) . . . . . . . . . . . . . . . . . .|. . . . . . . . . --> . . . o o o o . . . . . . . . . . . o o o|o . . . . . bent: 5 moves . . . . . .|. . . . . . . . . . . o|. . . . . . . . . . . .|. . . . . . . . . . . o|. . . . . . . . . . . .|. . . . . . . . . . . o|. . . . . . . . . --> . . . . . . o o o|o . . . . . . . . . . .|o . . . . . shift-down: 4(n-2) moves . . . . . o|. . . . . . . . . . . .|. . . . . . . . . . . o|. . . . . . . . . . . .|. . . . . . . . . . . o|. . . . . . . . . . . .|. . . . . . . . . . . .|. . . . . . . . . . . .|. . . . . . . . . . . .|. . . . . . . . . . . o|. . . . . . . . . . . .|. . . . . . . . . . . o|. . . . . . . . . . . .|. . . . . . . . . . . o|. . . . . . . . . --> . . . . . . . . .|o . . . . . . . . . . .|o . . . . . square: 4 moves . . . . . .|. . . . . . . . . . . .|. . . . . . . . . . . .|. . . . . . . . . . . .|. . . . . . . . . . . .|. . . . . . . . . . . .|. . . . . . . . . . . .|. . . . . . . . . . . .|. . . . . . . . . . . o|. . . . . . . . . . . .|. . . . . . . . . . . o|. . . . . . . . . . . o|o . . . . . . . . . . o|. . . . . . . . . . . o|o . . . . . . . . --> . . . . . . . . .|o . . . . . . . . . . .|. . . . . . Total number of moves: 8n - 5 - 4 floor(n/3 - 1) - d if 3 | n then d = 0 otherwise d = 2 For n=2 this method is not valid, but I derived from it the second 12 move solution given above by little modifications. Table: n 2n moves 2 4 12 opt 3 6 19 opt 4 8 25 opt 5 10 33 opt=32 6 12 39 opt 7 14 45 opt 8 16 53 opt=52 Optimal number of moves: floor(20n/3) - 1 Problem: move the four pieces to a 2*2 block whose left lower corner is at (x,y) in a rectangle of size at least 2x*2y. Minimal number of moves (for x>=y>=2) floor(8x/3)+3 + 4(y-1). The first term counts the number of moves to the bent-it position. The second term the final steps. Example: a 2*2 block at (4,3) 4| . . . o o . 3| . . . o o . 2| . . . . . . 1| . . . . . . ^ ^ ^ ^ ^ ^ 1 2 3 4 5 6 optimal moves for n = 0, 1 (modulo 3) which are suboptimal for n = 2 (modulo 3) line-up (6 moves) D . . . . . . . . . . C Bl, . . . . . . . . . . . . . . . Cdl, . . . A . . . . . . . . . . B Drdl A B C D . . . . . . . . line-up + 1 (8 moves) D . . . . . . . . . . C Ar, Cld, . . . . . . . . . . . . . . . ABl, . . . A . . . . . . . . . . B Drdl . C A B D . . . . . . . the 3-step (8 moves) . . . . . . . . . . . . Du, ABCr, . . . . . . . . . . . . . . . Dd, ABCl . . . A B C D . . . . . . . . . . . D A B C . . . . . the 1-step (4 moves) used for the suboptimal n = 2 (modulo 3) case . . . . . .|. . . . . . Aurdl . . . . . .|. . . . . . . . . | . . . | . . A o o o|. . . . . . . . . o o o|A . . . . . bend-it (5 moves) . . . . . . . . . . . . Bu, . . . . . B . . . . . . . . . . . . . . . . . . Aru, . . . . . A . . . . . . . . . . . . . . . . . . Dru . . . . . D . . . . . . . . . . . . . . . D A B|C . . . . . . . . . . .|C . . . . . shift-down (4 moves) . . . . . B . . . . . . Bldru . . . . . . . . . . . . . . . . . A . . . . . . . . . . . A . . . . . . . . . . . D . . . . . . . . . . . D . . . . . . . . . . . . . . . . . . . . . . . B . . . . . . . . . . . . . . . . . . C . . . . . . . . . . . C . . . . . square (4 moves) . . . . . . . . Cr, . . . . . . . . . . . . . . . . Bd, . . . . . . . . . . . B . . . . Cl, . . . . . . . . . . . C . . . . Du . . . B C . . . . . . A . . . . . . . A D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .|D . . . . . . . . . . . optimal moves for n = 2 (modulo 3) alternate start (2 moves) D . . . . . . . . . . C Ar, D C . . . . . . . . . . . . . Cl, . . . A . . . . . . . . . . B . . . . . . . . . . A B alternate 3-step (8 moves) A B . . . . . . . . . . Bd, CDl, Ar, . . . D A . . . . . . . . . . Du, BCr, Al . . . . . . . . . . . . . C D . . . . . . . . . . B C alternate bend-it (6 moves) . . . D A|. . . . . . . Dd, BCl, . . . . A . . . . . . . . . . . .|. . . . . . . Bu, Dru . . . . B . . . . . . . . . . . .|. . . . . . . . . . . D . . . . . . . . . .| . . . . . . . .|. . . . . B C . . . . .|C . . . . . . A symmetrical solution for rectangles 2n*m: Now try to move four coins from the corners of a 2n*m-rectangle into a 2-square somewhere on the middle strip. Example for 8*5: A . . . . . . D Br, Dl, . . . B A . . . . . . . . . . . Adr, Cul, . . . . . . . . . . . . . . . . Ddr, Bul, . . . . . . . . . . . . . . . . Cdr, Aul . . . . . . . . B . . . . . . C . . . C D . . . . . . B A . . . Cu, Bldr, . . . . . . . . . . . . . . . . Du, Ardl . . . C D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . C D . . . . . . B A . . . . . . . . . . . Bu . . . . . . . . . . . C D . . . Au . . . C D . . . . . . . . . . . . . . B A . . . . . . . . . . . . . . . . . . . . . . B A . . . . . . . . . . . Allow diagonal moves: A . . D A(rd) . . . D Dl(rd) . . . . . . . . B(ru) . . B . Cl(ru) . D B . . . . . . . A . . C A . B . . C . . . C . . . . A 3n+2 scheme for 2n-square for n>2. A . . . . . . D prephase: 5 moves . . . . . . . . . . . . . . . . B(ru), Ad(ru), Cl(ru) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B . . . . . . C . . . . . . . D 1-steps: 3(n-3) moves . . . . . . B . . . . . . A . . Dld(ru) . . . . C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . postphase: 6 moves . . . . . . B . . . . . . A . . Cd, A(ld)l, B(ld), Ar, Cu . . . . C . . . . . . D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A B . . . . . . D C . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-D extansion: -------------- Try to shift the 8 corners of a 4-cube into the middle 2-cube. I can do it in 4+12+4+12+4 = 36 moves or in 6+6+12+12 = 36 moves. The 2n-Cube: The second possibility for the 4-cube generalizes to bigger ones. The k-dimensional case reduces to 2-dimensional ones. The problem is solved in two phases. (diagrams shown for the 4-cube) phase 1: Reduce the dimension by 1. o . . o . o o . . . . . --> . . . . Do this for 2^(k-2) . . . . . . . . 2-dimensional squares. o . . o . o o . phase 2: Solve two (k-1)-dimensional problems. Faster is a more complicated procedure, which uses 7-steps. In the second phase 5-steps save a move. the 5-step: . . . . . . . . . . . . . . . . . Cu, Br, Cd, Bd A . . . . . . . . . . . . . . . . . . . . . . . . . B C D E F G H . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . DEFGHl, Bu, DEFGHr A . . . . . . . . . C . . . . . . . . . . . . . . . . . D E F G H . . . . . . . . . . . B . . . . . . . . . . . . . . . . . . . . . . . Ad, Cl, Au, Ar A . . . . . . . . . C . . . . . . . . . . . D E F G H B . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . C . . . . . . . . . . . . . . . . . . . . A D E F G H B . . . . . . . . . . . . . . . . . . . . . . . total: 19 moves Number of states of the closure for the n*m-rectangle with 1 piece. closure(n,m) = 4 for n,m >= 2 closure(r,s,t) = 8 for r,s,t >= 2 Number of states of the closure for the n*m-rectangle with 2 pieces. closure(n,m) = 4((m-3)_+ + (n-3)_+) + 8(m+n-4) + 6 for n,m >= 2 = 4(m+n-6) + 8(m+n-4) + 6 for n,m >= 3 = 12(n+m) - 50 The three terms count: 4(m+n-6) : states with 0 coin in a corner 8(m+n-4) : states with 1 coin in a corner 6 : states with 2 coins in a corner Number of states of the closure for the n*m-rectangle with 3 pieces. 4 5 6 7 8 +------------------------- 4| 428 744 1140 1616 2172 5| 744 1242 1844 2550 3360 6| 1140 1844 2676 3636 4724 7| 1616 2550 3636 4874 6264 8| 2172 3360 4724 6264 7980 closure(n,m) = 12(n+m)nm - 8(n+m)^2 - 18nm - 100(n+m) + 492 for n,m >= 4 Number of states of the closure for the n-square with 4 pieces. n closure 2 1 3 121 4 1684 5 9629 6 35232 7 96229 8 218412 9 437053 10 798344 11 1360837 12 2196884 13 3394077 14 5056688 15 7307109 closure(n) = 12n^5 + O(n^4) closure(n,m) = 6(n+m)(nm)^2 + O((n+m)^4) Number of states of the closure for the n*m-rectangle with k>=2 pieces. closure(n,m) = 12(n+m)(nm)^(k-2)/(k-2)! + O((n+m)^(2k-4)) There are C(nm,k-2) possibilities to place k-2 coins. The remaining 2 can be placed at the boarder in 12(n+m) + O(1) ways. This gives the highest term. 3-square statistics: -------------------- dist configurations (unlabeled) 0 1 1 8 2 28 3 48 4 28 5 8 ------------- Total 121 of 126 Transition states: 5 4-square statistics: (3 coins) -------------------- dist configurations (unlabeled) 0 1 1 6 2 18 3 36 4 59 5 54 6 67 7 61 8 50 9 24 10 26 11 22 12 4 ------------- Total 428 The 0 move configuration is: o . . o . . . . . . . . o . . . The 12 move configurations are: . . . . . . . . . . . . . . . o . o . . . . . o . . o . . . . o . o . . . o . . . . o . . . o . 4-square statistics: -------------------- First consider the labeled case. dist configurations 0 1 1 8 2 36 3 136 4 380 5 998 6 2454 7 4916 8 7334 9 8588 10 7985 11 4798 12 2090 13 626 14 66 ------------- Total 40416 = 1684*24 dist configurations (unlabeled) 0 1 1 8 2 28 3 80 4 148 5 200 6 286 7 312 8 304 9 226 10 66 11 16 12 9 ------------- Total 1684 of 1820 = C(16,4) Transition states: 140-4 The 12 move configurations are: . . . . . . o . . . o . . o o . . o . . . o . . . o o . . . o . o . o . . . . . . o . . . . . . 4-square statistics: (3 coins) -------------------- dist configurations (unlabeled) 0 1 1 6 2 18 3 36 4 63 5 102 6 139 7 127 8 122 9 147 10 131 11 73 12 94 13 105 14 68 15 10 ------------- Total 1242 The 15 move configurations are: . . . . . . . o . o o . o . . . . . o . . . . . . . . o . . . . . . . . . . . . . . . . . . . o . . . . . . o . . o . . . . o . . . o . . . o . . . . . . . . o . . . . . . . . . . . . . . . . . . . o . . . . . . . . . . . . . . . . . o . . . . . . . 5-square statistics: -------------------- dist configurations (unlabeled) 0 1 1 8 2 28 3 80 4 172 5 352 6 548 7 732 8 1008 9 1154 10 1230 11 1084 12 996 13 1100 14 700 15 308 16 104 17 20 18 4 ------------- Total 9629 The 18 move configurations are: o . . . . . o . . . . . . o . . . o . . . . . . . 6-square statistics: -------------------- dist configurations (unlabeled) 0 1 1 8 2 28 3 80 4 172 5 352 6 660 7 1172 8 1640 9 2176 10 2622 11 2708 12 3224 13 3636 14 3452 15 3368 16 3384 17 2744 18 1652 19 1085 20 778 21 250 22 40 ------------- Total 35232 of 58905 = C(36,4) The 22 move configurations are: . o . . . . o . . . . . . . . . . . o . . . . . . . . . . . . . . . . . . . o . . . . . o . . . . . . o . . . . . o . . . . . . o . . . . . . o . . . . . . . . . o . . . . o . . . . . . . . . . . . . . . . o . . . . . . o . . . . o . . . . . . . . . . . o . . . . . . . . . . . . . o . . . o . . . . . o . . . . o . . . o . . . . o . . . . . o . . . . o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . o . . . . . . . . . 7-square statistics: -------------------- dist configurations (unlabeled) 0 1 1 8 2 28 3 80 4 172 5 352 6 660 7 1216 8 2008 9 2978 10 3774 11 4572 12 5540 13 6336 14 7088 15 7364 16 8364 17 8484 18 7644 19 7372 20 7172 21 5512 22 3788 23 3172 24 1692 25 680 26 156 27 12 28 4 ------------- Total 96229 The 28 move configurations are: o . . . . . . . . . . . . . . . . o . . . . . o . . . . . . . . o . . . . . . . . . . . . . . . . 8-square statistics: -------------------- dist configurations (unlabeled) 0 1 1 8 2 28 3 80 4 172 5 352 6 660 7 1216 8 2008 9 3154 10 4442 11 5944 12 7528 13 9318 14 10704 15 11772 16 13908 17 15056 18 15220 19 15640 20 17268 21 16492 22 14408 23 13776 24 12108 25 9205 26 7326 27 5190 28 2748 29 1748 30 752 31 172 32 8 ------------- Total 218412 The 8 move configurations are: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . o . . . . . . . . . . . . . o . . . . . . . . . . . . . o . . . . . o 9-square statistics: -------------------- dist configurations (unlabeled) 0 1 1 8 2 28 3 80 4 172 5 352 6 660 7 1216 8 2008 9 3154 10 4486 11 6416 12 8884 13 11400 14 13728 15 15788 16 18952 17 21692 18 22784 19 24860 20 27388 21 28232 22 28668 23 29124 24 28648 25 26140 26 24380 27 22908 28 18496 29 14824 30 12304 31 8824 32 5244 33 3284 34 1484 35 324 36 80 37 32 ------------- Total 437053 10-square statistics: --------------------- dist configurations (unlabeled) 0 1 1 8 2 28 3 80 4 172 5 352 6 660 7 1216 8 2008 9 3154 10 4486 11 6416 12 9084 13 12412 14 15864 15 18986 16 23372 17 27572 18 29840 19 33904 20 37804 21 40968 22 42492 23 44460 24 46632 25 46248 26 46468 27 45484 28 43024 29 40660 30 38004 31 32584 32 26985 33 23584 34 19280 35 13236 36 9180 37 6188 38 3024 39 1688 40 664 41 72 ------------- Total 798344 11-square statistics: --------------------- dist configurations (unlabeled) 0 1 1 8 2 28 3 80 4 172 5 352 6 660 7 1216 8 2008 9 3154 10 4486 11 6416 12 9084 13 12460 14 16440 15 20724 16 26400 17 32028 18 36052 19 41644 20 46872 21 51692 22 56028 23 59844 24 62892 25 65896 26 69120 27 69168 28 68992 29 70076 30 70088 31 66880 32 61608 33 58852 34 54976 35 47488 36 40800 37 35812 38 28324 39 21460 40 16168 41 10676 42 7184 43 3976 44 1480 45 692 46 364 47 16 ------------- Total 1360837 12-square statistics: --------------------- dist configurations (unlabeled) 0 1 1 8 2 28 3 80 4 172 5 352 6 660 7 1216 8 2008 9 3154 10 4486 11 6416 12 9084 13 12460 14 16456 15 20976 16 27552 17 34818 18 40312 19 47788 20 54892 21 61388 22 68044 23 74308 24 79908 25 84724 26 90896 27 93932 28 96400 29 100520 30 101892 31 101716 32 100708 33 101276 34 98484 35 91572 36 87396 37 84000 38 75936 39 65521 40 59392 41 50052 42 40016 43 32884 44 26876 45 17552 46 11832 47 8464 48 4852 49 1976 50 1048 51 288 52 80 53 32 ------------- Total 2196884 13-square statistics: --------------------- dist configurations (unlabeled) 0 1 1 8 2 28 3 80 4 172 5 352 6 660 7 1216 8 2008 9 3154 10 4486 11 6416 12 9084 13 12460 14 16456 15 20976 16 27624 17 35412 18 42432 19 51916 20 60692 21 69276 22 78400 23 86828 24 94916 25 102940 26 110744 27 116700 28 123296 29 130772 30 134552 31 136548 32 138368 33 143244 34 145212 35 141020 36 139404 37 138428 38 133280 39 126176 40 120984 41 113668 42 100252 43 90840 44 82900 45 69580 46 58300 47 50264 48 38024 49 27168 50 22184 51 15620 52 8368 53 4944 54 3260 55 1368 56 416 57 152 58 48 ------------- Total 3394077 14-square statistics: --------------------- dist configurations (unlabeled) 0 1 1 8 2 28 3 80 4 172 5 352 6 660 7 1216 8 2008 9 3154 10 4486 11 6416 12 9084 13 12460 14 16456 15 20976 16 27624 17 35436 18 42684 19 53164 20 64120 21 74918 22 86136 23 97472 24 107984 25 118772 26 129716 27 138912 28 148284 29 159692 30 167912 31 173704 32 178564 33 185484 34 191272 35 192572 36 194648 37 197808 38 196400 39 192604 40 188556 41 186068 42 177224 43 169480 44 161104 45 145605 46 133838 47 125390 48 110036 49 90440 50 79780 51 70456 52 52188 53 39440 54 33120 55 23548 56 14216 57 10208 58 6868 59 2996 60 1400 61 904 62 352 63 32 ------------- Total 5056688 15-square statistics: --------------------- dist configurations (unlabeled) 0 1 1 8 2 28 3 80 4 172 5 352 6 660 7 1216 8 2008 9 3154 10 4486 11 6416 12 9084 13 12460 14 16456 15 20976 16 27624 17 35436 18 42696 19 53272 20 64860 21 77292 22 91124 23 104960 24 117940 25 132188 26 145676 27 157648 28 171048 29 186392 30 197348 31 207692 32 218008 33 228984 34 237216 35 241980 36 248844 37 255896 38 259800 39 262848 40 261936 41 261412 42 258540 43 255012 44 251948 45 239608 46 230140 47 222068 48 209140 49 189320 50 175832 51 164024 52 140640 53 120816 54 110940 55 93892 56 70776 57 57336 58 49640 59 35544 60 22584 61 16792 62 11736 63 6556 64 3180 65 1928 66 896 67 416 68 112 69 16 ------------- Total 7307109 13*15-rectangle statistics: --------------------------- dist configurations (unlabeled) 0 1 1 8 2 28 3 80 4 172 5 352 6 660 7 1216 8 2008 9 3154 10 4486 11 6416 12 9084 13 12460 14 16456 15 20976 16 27624 17 35424 18 42564 19 52594 20 62776 21 73284 22 84762 23 95894 24 106428 25 117564 26 128210 27 137174 28 147174 29 158586 30 165910 31 171946 32 177776 33 185050 34 189946 35 190442 36 192908 37 195518 38 194466 39 191686 40 188220 41 183632 42 174372 43 166832 44 159554 45 144784 46 131506 47 121368 48 107100 49 90144 50 78656 51 67428 52 50972 53 38974 54 32388 55 23504 56 13820 57 9124 58 6472 59 3052 60 1196 61 712 62 296 63 48 ------------- Total 4997417 -- http://www.mathematik.uni-bielefeld.de/~sillke/