Analysis of "Luminations",
a 1989 puzzle from Random House
by Rick Nungester
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.