a 1989 puzzle from Random House

Revision History: - July 28, 2002 - Corrected the "Addendum: How many Level 5 paths to a solution at depth n" section, which had errors in the table values. - Added notes regarding level 5 Shortest Solution Algorithm. - Mailed to Courtney McFarren for posting to his website. - May 25, 2002 - Improved the Level 5 solution algorithm. (Only the complicated Shortest Solution algorithm existed earlier.) - Apr 28, 2002 - Posted to newsgroup rec.puzzles: Solutions to all 5 levels, level 5 state counts and number of solution steps from solution, other addendums. --------------------------------------------------------------------- Luminations is a 5-inch high battery operated pyramid with a red, yellow, and green LED on each of its 4 points. It senses which point is up. As a new point is raised, the LEDs on 1 to 4 points change state among red, yellow, green, flashing red, flashing yellow, flashing green, or all off, abbreviated rygRYGx respectively. The goal of each of the 5 difficulty levels is to make all points red. 5 characters give puzzle state, for example 2xrgx means point 2 is up, and points 1,2,3,4 are off, red, green, off. To start Levels 1 through 4, turn on the power with point 1 through 4 up. Level 5 can only be started by first completing Level 4. --------------------------------------------------------------------- Level 1 (1xxxx, poweron, tilt for random start state). Points cycle rgxyG (a cycle of 5). A point only changes color when brought to the up position. Algorithm: - Pick one of the 3 down points as an inntermediate target color. Keep it down and "rock" the puzzle until an up point is the same color. - Make the two same-color points both doown. Keeping these two down, rock more until an up point is the same color. - Now 3 or 4 points are the same color. If 3, make all 3 the same color as the 4th by keeping the 4th down while "rolling" the puzzle so the other 3 each cycle through their states to match the 4th. - Once all 4 points are the same color, if red, you're done. If all 4 are the same color but not red, raise each one in sequence (for example 2431) how ever many times is necessary to move all 4 to red. --------------------------------------------------------------------- Level 2 (2xxxx, poweron, tilt for random start state). Points cycle rYxgy (a cycle of 5). A point changes color when moving either up or down. Algorithm: - Make any two down points the same coloor. - Leave these two down and rock until thhe top point is also the same color. - If all 4 are the same color and red, yyou're done. If all 4 are the same color, not red, skip the next step. - Make the 3 like-colored points (abc) mmatch the 4th down-point (d) by raising a,b,c, repeatedly. If all 4 are red, you're done. If not, continue. - All 4 points are the same color, not rred. Say a is up, bcd are down. Raise bcda. The color of all 4 points has advanced by 2 colors. Repeat until all are red. ----------------------------------------------------------------------- Level 3 (3xxxx, poweron, tilt for random start state). Points cycle rgRYGy (a cycle of 6). A point changes color only when it moves up, and only if was not the previous 2 up points. Example sequences of up points: - 234 (2 or 3 next will not change colorr. 1 next will.) - 121 (2 next will not change color. 3 or 4 will.) Algorithm: - Get a red point on top. Call this is point A. - For all future moves, do BA, CA, or DAA. This leaves A red. Never repeat BA twice, CA twice, or DA twice. This means as A, B, or C is raised it will always change color. This allows cycling B, C, or D colors in a controlled manner. - Make B and C the same color. - Make D match B and C by the sequence BBADACADA as many times as needed. (This sequence changes D 2 colors for every 1-color change in B and C.) - Now B, C, D are the same color. Do thhe sequence BACADA as many times as needed to make all points red. ----------------------------------------------------------------------- Level 4 (4xxxx, poweron, tilt for random start state). Points cycle ryxYgRG (a cycle of 7). If point A is raised, A doesn't change color, but BCD do. Algorithm: - If A is up, move BABABABA... until anyy two low points are the same color. - Keep the two some-color low points loww, and alternate the two other points in the up position until all 3 low points are the same color. If all 4 points are red, you're done. If all 4 are the same color but not red, skip the next step. - Say A is up. BCD are the same color, and different than A. Moves BACADA change A forward 3 colors (= back 4) and change BCD forward 5 colors (= back 2). Repeat this move sequence until ABCD the same color. If all are red, you're done, else continue. - All 4 points are the same color, not rred. Say A is up. Repeat the moves BCDA until all points are red. Each sequence moves all 4 points forward 3 colors (= back 4). ----------------------------------------------------------------------- Level 5 (solve Level 4, hear beeps, tilt for random start state). Points cycle rGYgRxygY (a cycle of 9). Each move, each point steps its color forward in the 9-cycle the number of times it was the up-point in the current and previous 3 states. (This means each point changes by 0, 1, or 2 steps in the 9-cycle each move. Each move, total color steps on all points is always 4.) Algorithm: 1) If point 2 is up, raise point 1. 2) Repeat 21 two or more times, until point 1 is flashing red. 3) Repeat 32 two or more times, until point 2 is all-off. 4) Repeat 43 two or more times, until point 3 is yellow. 5) Repeat 1234 until point 4 is yellow. 6) Repeat 123 until solved. "21" means raise point 2, then raise point 1. This algorithm avoids all point color ambiguities due to the repeated sequencing of green and flashing yellow, and requires only checking the color of the current top point. It takes 112 moves maximum, and 70 moves average. Reaching a solution can happen anywhere during the algorithm. How it works: Repeating 21 gets point 1 to a desired color. Repeating 32 two or more times changes point 1 no more, and gets point 2 to a desired color. Repeating 43 two or more times changes points 1 and 2 no more, and gets point 3 to a desired color. Repeating 1234 changes the color of all 4 points the same number of steps, and allows getting point 4 to a desired color. Repeating 123 eventually changes point 4 no more, and steps the color of points 1, 2, and 3 equally, until they equal the color of point 4. This solution was found by experimenting with a Lotus 123 spreadsheet that simulates the game, after doing the analysis that follows. ----------------------------------------------------------------------- Level 5 Analysis and Shortest Solution Algorithm ================================================ Notation: XYZ ABCD indicates a puzzle state. X, Y, and Z represent up-points (value 1 through 4) two moves ago, one move ago, and now, respectively. A, B, C, D represent the 9-cycle color position (rGYgRxygY = 012345678) of point 1 through 4 respectively. Example: 124 0836 means point 1 was up, then point 2, now point 4, and the colors on points 1 through 4 are red, flashing Yellow (following green), green (following flashing Yellow), and yellow. Determine start state: Notice the up-point 1 step before the solution to Level 4 (A). (Yes, this actually affects Level 5.) Solve Level 4 and notice the up-point (B, B <> A). Start Level 5 by raising point C (C <> B and C <> A). Notice the point colors. If none are Y or g, you have enough information to solve the puzzle (in 22 steps max) -- current and 2 previous up-points, and position on the 9-cycle of colors for each point. If one or more points are Y or g, raise point D (D <> C and D <> B and D <> A). This causes all point colors to advance in the 9-cycle by 1. Now any ambiguity due to reuse of Y and g is gone, and enough is known to solve the puzzle. (This also uses 1 move to determine complete starting state, resulting in 23 moves maximum.) Example: - Point 3 is up 1 move before the end off Level 4. - Point 1 is up at the solution to Levell 4. - Start Level 5 by raising point 2 or 4.. Say we choose 2. Level 5 has started, and point colors are rxYg = 0 5 (2 or 8) (3 or 7). - Ambiguity of Y and g must be removed bby another move. Up-point history so far is 312, so raise point 4, which will advance all points by 1 color. Now colors are GygR = 1634, with no ambiguity. - Start state is 124 1634, with one movee being spent determining it. See the addendum "1- and 2-move solutions". The rest of this solution process ignores these few trivial cases, and will still solve them, just with more solution steps than required. Generate point colors EFGH, that account for existing previous history, by incrementing (mod 9) point X, Y, Z by 1, 2, 3 respectively. For example, start state 124 1634 would imply incrementing point 1 by 1, point 2 by 2, and point 4 by 3, resulting in EFGH = 2837. Determine the minimum number of color steps each of EFGH must advance to be red. This is e=9-E, f=9-F, g=9-G, h=9-H, for points 1 through 4 respectively, with the "-" being done mod 9 (9 - 0 = 0, not 9). A solution is achieved when points 1 through 4 advance in unison by e+9*i, f+9*j, g+9*k, h+9*m, where i, j, k, m are whole numbers (0, 1, 2, 3, ...). Example: EFGH = 2837 means efgh = 7162. Use e, f, g, h, and the following table to pick solution moves: Ways to step forward n (0-8) colors ((n+9*i)/4, quotient & remainder) n= 0 1 2 3 4 5 6 7 8 i q r q r q r q r q r q r q r q r q r = ===== ===== ===== ===== ===== ===== ===== ===== ===== 0 0 0 0* 1* 0* 2* 0 3 1 0 1 1 1 2 1 3 2 0 1 2 1 2 2 2 3 3 0 3 1 3 2 3* 3* 4* 0* 4 1 2 4 2 4 3 5 0 5 1 5 2 5 3 6 0 6 1 6 2 3 6 3 7 0 7 1 7 2 7 3 8 0 8 1 8 2 8 3 4 9 0 9 1 9 2 9 3 10 0 10 1 10 2 10 3 11 0 5 11 1 11 2 11 3 12 0 12 1 12 2 12 3 13 0 13 1 ^^^^^ ^^^^^ ^^^^^ ^^^^^ Point: 2 4 3 1 e, f, g, and h each choose a column, for the example being developed, 7, 1, 6, and 2. (The same column can be used twice if e, f, g, or h have the same value.) Under each column, write the point corresponding to e, f, g, h as shown. Pick from each column an r,q pair such that the 4 picks have remainder ("r") value 0, 1, 2, and 3. Choose toward the top of the table as much as possible to keep total solution length low. "*" indicates a valid choice for the example problem. The last 3 moves of the solution are the points beneath the columns with remainder 3, 2, 1 respectively. In the example, points 3, 4, 2. (This is because the last, prev, prev-prev move has its point incremented only 1, 2, 3 times, while any other solution moves contribute 4 increments to its point.) The "q" values indicate how many more times the point beneath the column has to be included in the solution: 0 2s, 0 4s, 3 3s, 4 1s. Lastly, the solution can't have the same up-point appear twice in a row. Remember we're solving 124 1634, so 4 can't be the first solution move. A solution is 1313131342 (3 3s, 4 1s, then 342, with no value repeating and the first move different than the current up-point). Another more complicated example: Solve 343 3881. 3881 starting colors 3833 colors after incrementing 3 by 1, 4 by 2, 3 by 3, mod 9 6166 color steps to solution = (9 -), mod 9 n= 0 1 2 3 4 5 6 7 8 i q r q r q r q r q r q r q r q r q r = ===== ===== ===== ===== ===== ===== ===== ===== ===== 0 0 0 0* 1* 0 2 0 3 1 0 1 1 1* 2* 1 3 2 0 1 2 1 2 2 2 3 3 0 3 1 3 2 3* 3* 4 0 4 1 2 4 2 4 3 5 0 5 1 5 2 5 3 6* 0* 6 1 6 2 3 6 3 7 0 7 1 7 2 7 3 8 0 8 1 8 2 8 3 4 9 0 9 1 9 2 9 3 10 0 10 1 10 2 10 3 11 0 5 11 1 11 2 11 3 12 0 12 1 12 2 12 3 13 0 13 1 ^^^^^ ^^^^^ Points: 2 1,3,4 "*" = first solution attempt (remainders 0,1,2,3), but it won't work. Notice the q=6 value, and other q values are only 0, 1, and 3. Whatever point is associated with the q=6 value can't repeat, which requires 5 "separator" values. But there are only 0+1+3=4. So try another solution: n= 0 1 2 3 4 5 6 7 8 i q r q r q r q r q r q r q r q r q r = ===== ===== ===== ===== ===== ===== ===== ===== ===== 0 0 0 0 1 0 2 0 3 1 0 1 1 1* 2* 1 3 2 0 1 2 1 2 2 2 3 3 0 3 1 3 2 3 3 4 0 4 1 2 4 2 4* 3* 5 0 5 1 5 2 5 3 6* 0* 6 1 6 2 3 6 3 7 0 7 1 7 2 7 3 8 0 8* 1* 8 2 8 3 4 9 0 9 1 9 2 9 3 10 0 10 1 10 2 10 3 11 0 5 11 1 11 2 11 3 12 0 12 1 12 2 12 3 13 0 13 1 ^^^^^ ^^^^^ Points: 2 1,3,4 Which of points 1,3,4 goes with remainder 2,0,1 is arbitrary. Say point 1,3,4 goes with remainder 2,0,1 respectively. The last 3 solution moves are r=3, r=2, r=1, or points 2,1,4. Preceding these steps are 4 2s, 1 1, 6 3s, and 8 4s. Remember we're solving 343 3881, so the first solution step can't be a 3. One solution: 2424243434343434321214 | | | | 4 2s | 1 1 | | | | | | 6 3s | | | | | | | | 8 4s ||| ending in 214 343 3881 was intentionally chosen, as one of the few starting states requiring 22 moves to solve. It is important to note that for this technique to work, it must be known that any start state is solvable, and in under 22 moves. The table above need not be developed further since the most any single move can appear in the solution is 11 times (every other position of a 22-move solution). This was proven by a program, with results given below. ----------------------------------------------------------------------- Addendum: 1- and 2-move solutions to Level 5 The algorithm above assumes a solution of 3 or more steps. A method of determining if the start state has a 1- or 2-move solution follows, which is simply "try the 3 next moves and 9 next move pairs". 1-move solution: Given XYZ abcd (abcd = desired color moves of points 1234), try next-move T as the the 3 non-Z values. If incrementing points XYZT by 1 totals abcd (a=9-A, b=9-B, c=9-C, d=9-D, mod 9, meaning 9-0=0), you have a solution. Example: Given XYZ ABCD = 343 0077, then abcd = 0022. (Points 1 and 2 are already red. Points 3 and 4 are 2 steps back.) Try 3431, 3432, (3433 is invalid because 3 is repeated), 3434: 3431 increments points 1234 by 1021, not 0022. Not a solution. 3432 increments points 1234 by 0121, not 0022. Not a solution. 3434 increments points 1234 by 0022. A solution. 2-move solution: Given XYZ abcd, try all 9 possible next move pairs T and U. If incrementing point X,Y,Z,T,U by 1,2,2,2,1 totals abcd, you have a solution. Example: Given XYZ ABCD = 343 8065, then abcd = 1034. 34312 increments points 1234 by 2132, not 1034. Not a solution. 34313 increments points 1234 by 2042, not 1034. Not a solution. 34314 increments points 1234 by 2033, not 1034. Not a solution. 34321 increments points 1234 by 1232, not 1034. Not a solution. 34323 increments points 1234 by 0242, not 1034. Not a solution. 34324 increments points 1234 by 0233, not 1034. Not a solution. 34341 increments points 1234 by 1034. A solution. 34342 increments points 1234 by 0134, not 1034. Not a solution. 34343 increments points 1234 by 0044, not 1034. Not a solution. ----------------------------------------------------------------------- Addendum: How Many Level 5 Start States? There are 4 possible up-points. Given current up-point, there are 3 possible previous up-points. Given previous up-point, there are 3 possible previous previous up-points. There are 9 colors (actually "positions on the 9-cycle of colors") for each of the 4 points. This makes 3*3*4*9*9*9*9 = 236,196 starting states total. If positions on the 9-cycle of colors (rGYgRxygY) are assigned the digits 0 through 8, a puzzle state can be represented as 7 digits: previous previous up-point, previous up-point, current up-point, position in the 9-cycle of colors of points 1, 2, 3, and 4. A program was written to start at the solution and work backwards to generate all states that can lead to it. Results: 36 games at level 0, example: 434 0000 108 games at level 1, example: 343 0077 324 games at level 2, example: 343 8065 972 games at level 3, example: 343 8754 2700 games at level 4, example: 343 8723 6084 games at level 5, example: 343 8710 10944 games at level 6, example: 343 8778 14832 games at level 7, example: 343 8855 19044 games at level 8, example: 343 8824 21384 games at level 9, example: 343 8811 23724 games at level 10, example: 343 8870 24552 games at level 11, example: 343 5446 24840 games at level 12, example: 343 8835 23364 games at level 13, example: 343 0002 20160 games at level 14, example: 343 8881 15300 games at level 15, example: 434 7878 11412 games at level 16, example: 434 7847 7200 games at level 17, example: 434 7852 4824 games at level 18, example: 434 7857 2412 games at level 19, example: 434 7853 1368 games at level 20, example: 434 7858 432 games at level 21, example: 434 6207 180 games at level 22, example: 434 3818 236196 games of 236196 total were found All counts above are evenly divisible by 36, due to puzzle symmetry. Given starting state XYZ ABCD, there are 36 values for XYZ: 4 for Z, 3 for Y (Y <> Z), 3 for X (X <> Y). 3*3*4 = 36. But since point number assignments are arbitrary, these 36 possibilities can be reduced to 3 -- Take any starting state and number the up-point 1. Hold the previous up-point toward yourself, and number it 2. Number the back-left 3 and the back-right 4. Using this point numbering system, XYZ = 121, 321, or 421. But these 3 can be further reduced to 1, by noticing these 3 start games have the same solution: 121 A B C D 321 A+1 B C-1 D 421 A+1 B C D-1 where the +/- operation is mod 9 (8+1=0, 0-1=8). If all 121 ABCD solutions are known, all 321 ABCD and 421 ABCD solutions can be inferred. Example: Solve 213 7308. Point 3 is currently up. Point 1 was previously up, so point it at yourself. Point 2 is back-left and point 4 is back-right. (These last 2 are due to how the puzzle is physically labeled.) Renumber point 3 to 1 (up), 1 to 2 (front), 2 to 3 (back-left), and 4 to 4 (back-right). Now solve puzzle 321 0738. But these have the same solution: 121 8748 321 0738 <<< 421 0747 By convention, I solve the 121 history set, and extrapolate to other start histories, so would solve 121 8748. Minimum solution length for this starting state is 18, and one solution is: 212121212121434243 (a solution to 121 8748 and 321 0738 and 421 0747) 131313131313424142 (the same solution mapped back to original point numbers) A detail: 121 0000 need not be considered solved, and can be moved through to another solved 0000-color state, via solution 212121212. This solution provides the basis for 35 other symmetrical start states. So eliminating symmetries, there are only 236,196/36 = 9^4 = 6561 starting states: 121 0000, 121 0001, 121 0002, ..., 121 8888. ----------------------------------------------------------------------- Addendum: Understanding Progression Toward a Level 5 Solution The following table shows what is happening during a solution, and helps understand the solution algorithm. A solution to 121 0836 is 2123431: 121 0836 starting state 212 2136 2 up 121 4336 1 up 212 6536 2 up 123 7746 3 up 234 8857 4 up 343 8078 3 up 431 0000 1 up, solution, all points red Notice the number of color increments due to each move. Moves -2, -1, 0 increment their up-points a total of 1, 2, 3 times respectively. Moves last-2, last-1, last, increment their up-points a total of 3, 2, 1 times respectively. All mid-solution up-points (between the first 3 and last 3) increment their up-points a total of 4 times: 0836 starting colors 1 1 prev prev up-point increments 2 2 prev up-point increments 1 3 starting up-point increments 2 4 first solution move increments 1 4 ... 2 4 ... 3 4 ... 4 3 (last - 2) up-point increments 3 2 (last - 1) up-point increments 1 1 last up-point increments ==== 0000 sum of column, mod 9 (all red, a solution) ----------------------------------------------------------------------- Addendum: How many Level 5 paths to a solution at depth n? The number of paths to a solution goes up as the minimum number of solution steps goes up, because the number of ways of rearranging the mid-solution steps goes up. Here are some test cases for interest. (If someone could verify this table, I would appreciate it.) min sol n-step start steps solutions paths (3^n) ratio ======== ===== ========= =========== ===== 121 0836 7 5 2187 0.229% 343 8881 14 30 4782969 0.001% 343 7860 15 24162 14348907 0.168% 343 7820 16 77153 43046721 0.179% ----------------------------------------------------------------------- Addendum: Original notes that led to understanding the Level 5 "rules" move number | puzzle state | | color increments | ===== ==== -1 4 \_ Both can be inferred affter state 3 is known 0 2 / color increments 1 1gRxg ---- 2 2RyxY 1201 <<< 2nd logic) state -1 had point 4 up 3 3xYyY 1210 <<< 1st logic) state 0 had point 2 up 4 4yrgr 1111 with 3 history, 12341234... changes each point by 1 5 1gGYG 1111 6 2YYrY 1111 7 3rgGg 1111 8 4GRYR 1111 9 1Yxgx 1111 10 2gyRy 1111 11 3Rgxg 1111 12 4xYyY 1111 = 3, 9 moves back 13 1yrgr 1111 = 4 14 2gGYG 1111 = 5... 12341234... changes each point by 1 15 4YYYg 1102 change pattern to 414141... 16 1GgYR 2101 17 4YRYy 1102 18 1RRYY 2002 4141... changes 1 and 4 by 2 19 4yRYG 2002 " 20 1YRYg 2002 " 21 2GxYR 2101 change pattern to 123123... 22 3Yyrx 1111 23 1RgGx 2110 24 2xrYx 1210 25 3yGRx 1120 26 1YYxx 2110 123123... results in 1-2-3 change by 2 each. 27 2rRyx 1210 28 3GxYx 1120 *** Each point is incremented the number of times it was up in the current and previous 3 states. *** ----------------------------------------------------------------------- Addendum: Lotus 123 analysis of one 22-step solution to 343 3881 # u 1 2 3 4 point number of column -2 3 1 past history (343) pending color increments -1 4 2 0 3 3 ------------- 3 8 8 1 start colors 3 8 3 3 start+pending colors (mod 9) 6 1 6 6 required color steps to solution 6 1 6 6 color steps below, mod 9 (SOLUTION CHECK) -------------22 solution steps below 1 2 4 solution step color increments 2 4 4 3 2 4 4 4 4 5 2 4 6 4 4 7 2 4 8 4 4 9 2 4 10 4 4 11 2 4 12 4 4 13 2 4 14 3 4 15 2 4 16 3 4 17 2 4 18 3 4 19 1 4 20 3 3 21 1 2 22 2 1 ----------------------------------------------------------------------- July 28, 2002, incomplete notes regarding the shortest solution from any start state. (I've lost interest in the puzzle and cleaned up this section for posting in case someone else wants to continue the ideas that follow.) Of 6561 symmetrically unique start states with history 121, 3 have 1-step solutions: 7700 2 7880 3 7808 4 9 have 2-step solutions: 5500 21 6580 23 6508 24 5770 31 6670 32 6778 34 5707 41 6607 42 6787 43 and 6549 require 3 or more solution steps. (0000 is already solved, but is re-solved since it is the basis for start states not having 121 history.) These 6549 were solved and analyzed, and the rest of this section applies to them. Ways to step forward n colors ((n+9*i)/4, quotient & remainder) n=0 1 2 3 4 5 6 7 8 i q r q r q r q r q r q r q r q r q r = ==== ==== ==== ==== ==== ==== ==== ==== ==== 0 0 0 0 1 0 2 0 3 1 0 1 1 1 2 1 3 2 0 1 2 1 2 2 2 3 3 0 3 1 3 2 3 3 4 0 4 1 2 4 2 4 3 5 0 5 1 5 2 5 3 6 0 6 1 6 2 3 6 3 7 0 7 1 7 2 7 3 8 0 8 1 8 2 8 3 4 9 0 9 1 9 2 9 3 10 0 10 1 10 2 10 3 11 0 5 11 1 11 2 11 3 12 0 12 1 12 2 12 3 13 0 13 1 Each point falls in one of the columns above, where n = the number of color steps required to get to red, from the start start plus point color increments pending due to the 3 moves that led to the start state. How many ways are there to populate the columns? Each column can contain 0 through 4 points, and the total points in all columns is 4. This is the same question as "How many 9-digit base-5 integers are there that have the sum of all 9 digits equal 4? 1111 (4 columns) 126 = 9 take 4 112 (3 columns) 252 = 9 * (7+6+5+4+3+2+1) 31 (2 columns) 72 = 9*8 22 (2 columns) 36 = 8+7+6+5+4+3+2+1 4 (1 column) 9 === 495 >>> Any puzzle start state fits into one of 495 categories. Each of >>> these categories has the same number of minimum solution steps. For example: 0 1 2 3 4 5 6 7 8 = n = = = = = = = = = 0 0 0 0 0 0 0 4 0 has 22 solution steps minimum 0 1 0 0 0 0 3 0 0 has 22 solution steps minimum - Interesting side issue, discovered witth computer help: The above 2 of 495 are the only ones having 22 solution steps. There are only 5 start states having history 121 and 22-step solutions. Here they are, followed by their colors after incrementing due to the 121 history, and their required number of color increments to red: 121 4133 8333 1666 \ 121 8633 3833 6166 | 3x6s + 1x1 <<< case 1 121 8183 3383 6616 | 121 8138 3338 6661 / 121 7022 2222 7777 4x7s <<< case 2 But for solutions of 3 or more moves, each move adds 4 to its point color (except for the last 3 moves). So to move point X by 4 through 7, make move X once, then move point X by 0 through 3. To move point X by 8, make move X twice. The table may be simplified: add to q (= "s") ================ n=0 1 2 3 0 4 5 6 7 1 8 2 i q r q r q r q r = ==== ==== ==== ==== 0 0 0 0 1 0 2 0 3 1 2 1 2 2 2 3 3 0 2 4 2 4 3 5 0 5 1 3 6 3 7 0 7 1 7 2 4 9 0 9 1 9 2 9 3 5 11 1 11 2 11 3 12 0 How many ways are there to populate this table? Each column again may have 0 to 4 points in it. The sum of the points in all columns must be 4. How many 4-digit base-5 integers are there that have the sum of all 4 digits equal 4? 1111 (4 columns) 1 112 (3 columns) 12 = 4*3 31 (2 columns) 12 = 4*3 22 (2 columns) 6 = 4 take 2 4 (1 column) 4 == 35 Any puzzle start state fits into one of 35 categories, with various possible values of s. The 6549 states being considered in this section were solved and analyzed, giving the following results. "Category" indicates the number of points in the n=0|4|8 column, 1|5 column, 2|6 column, and 3|7 column, respectively. "solution" is incomplete. category | solution length - s | | s range | | | solution | | | As Bs Cs Ds ending ==== == === =========== ======== 0004 18 0-4 0 7 5 3 ABC (18) \_ all solutions? 2 7 3 3 ABA (18) / 0013 11 0-4 0022 13 0-4 0031 15 0-4 0040 17 0-4 2 0 7 5 ABC (17) \_ all solutions? 4 0 5 5 ABA (17) / 0103 13 0-4 /0112 6 2-4 \0112 15 0-3 /0121 8 0-4 \0121 17 0-2 /0130 10 2-4 \0130 19 0-3 0202 8 0-4 0211 10 0-4 0220 12 0-4 0301 12 0-4 0310 14 0-4 0400 16 0-4 4 2 0 7 ABC (16) - all solutions? 6 2 7 7 ABA (25) - never shortest 1003 15 0-5 1012 8 0-5 1021 10 0-5 1030 12 0-5 1102 10 0-5 /1111 3 0-5 \1111 12 0-3 /1120 5 2-5 \1120 14 0-3 /1201 5 1-5 \1201 14 0-2 /1210 7 0-5 \1210 16 0-2 /1300 9 2-5 \1300 18 0-3 2002 12 0-6 /2011 5 1-6 \2011 14 0-2 2020 7 0-6 /2101 7 0-6 \2101 16 1 2110 9 0-6 2200 11 0-6 /3001 9 1-7 \3001 18 0 /3010 2 1-7 \3010 11 0-3 /3100 4 2-7 \3100 13 0-4 /4000 6 4-8 \4000 15 0-5 Why do 14 of 35 categories have either m or m+9 base number of solution steps? (This question hasn't been answered completely. The following notes are my start of attempting to do so.) Analysis of a 6-base category 4000 start state ============================================== 323 1861 start state +1 pending... +2 +3 ==== 1111 start+pending state 8888 steps to solution (all 4 points in n=8 column) Ways to step forward n (0-8) colors ((n+9*i)/4, quotient & remainder) n=0 1 2 3 4 5 6 7 8 point i q r q r q r q r q r q r q r q r q r * # = ==== ==== ==== ==== ==== ==== ==== ==== ==== = = 0 0 0 0 1 0 2 0 3 1 0 1 1 1 2 1 3 2 0 4 1,3,4 1 2 1 2 2 2 3 3 0 3 1 3 2 3 3 4 0 4 1 3 2 4 2 4 3 5 0 5 1 5 2 5 3 6 0 6 1 6 2 2 2 3 6 3 7 0 7 1 7 2 7 3 8 0 8 1 8 2 8 3 1 4 9 0 9 1 9 2 9 3 10 0 10 1 10 2 10 3 11 0 5 11 1 11 2 11 3 12 0 12 1 12 2 12 3 13 0 13 1 Which is better, last 3 moves = ABC or ABA? ABC: Choose the last three moves = 123 (situation marked "*"). The 123 must be preceeded by 2x4s, 4x3s, 6x2s, 8x1s -- 23 moves total. For example: 2 2 2 2 2 2 1 1 1 1 1 1 1 1 3 3 3 3 4 4 123 ABA: Choose the last 3 moves = 121 (situation marked "#"). This must be preceeded by 6x2s, 2x3s, 2x4s, (2-1)x1s -- 14 moves total, which is known to be the min number for this start state. For example: 2 2 2 2 2 2 3 3 4 4 1 121 For start state 323 1861, the ABA solution is always shorter than the ABC ending. Computer analysis shows there are 270 14-move solutions to 323 1861, all having an ABA ending. Analysis of a 15-base category 4000 start state =============================================== 143 8067 start state +1 pending... +2 +3 ==== 0000 start+pending state 0000 steps to solution (compare to 8888 above) Ways to step forward n (0-8) colors ((n+9*i)/4, quotient & remainder) n=0 1 2 3 4 5 6 7 8 i q r * # q r q r q r q r q r q r q r q r = ==== = = ==== ==== ==== ==== ==== ==== ==== ==== 0 0 0 4 1,3,4 0 1 0 2 0 3 1 0 1 1 1 2 1 3 2 0 1 2 1 3 2 2 2 3 3 0 3 1 3 2 3 3 4 0 4 1 2 4 2 2 2 4 3 5 0 5 1 5 2 5 3 6 0 6 1 6 2 3 6 3 1 7 0 7 1 7 2 7 3 8 0 8 1 8 2 8 3 4 9 0 9 1 9 2 9 3 10 0 10 1 10 2 10 3 11 0 5 11 1 11 2 11 3 12 0 12 1 12 2 12 3 13 0 13 1 Which is better, last 3 moves = ABC or ABA? ABC: Choose the last three moves = 123 (situation marked "*"). The 123 must be preceeded by 0x4s, 2x3s, 4x2s, 6x1s -- 15 moves total. For example: 1 1 1 1 1 1 3 3 2 2 2 2 123 ABA: Choose the last 3 moves = 121 (situation marked "#"). This must be preceeded by 4x2s, 0x3s, 0x4s, (0-1)x1s -- CAN'T HAVE -1 1-MOVES. Instead, point 1 could be moved forward by n=9. 9 mod 4 = 1, so use the n=1 column and add 2 to q. r=0 implies q=7. Add 2, q=9. So a solution is 121 preceeded by 4x2s, 0x3s, 0x4s, (9-1)x1s -- 16 moves total. For example: 1 1 1 1 1 1 1 1 2 2 2 2 121 Can't be physically done, because of adjacent 1s. So in this case, the ABC ending is always shortest. Computer analysis shows there are 270 15-move solutions to 143 8067, all having an ABC ending.