The graphic represents an unfolded cylinder that has a rotatable ring around its girth. Nine blocks, labeled 1 to 9 in order, occupy that band initially. There are three vertical grooves which intersect this band; the slots will always carry 2 blocks although the slot length is for three.
At any one time, if a block in one vertical is moved up or down, the blocks in the other slots move simultaneously in the same direction. Horizontal bands may be rotated left or right as many places as you wish (but one place per mouseover).
Position at initialisation:
and then after several moves:
Note: All of the links provide interaction.
1. Suggest how I can "backtrack" to the initial position in the shortest possible moves.
Consider R4, 4R or RRRR, all being equivalent, as 4 moves.
2. Then, is it possible to reverse the order of the digits? If so, how?
Reset to the download position.
Set to the initialisation position.
Note: mouseover on links is very sensitive.
The program written for part 1 yielded:
D 3R U 1R D 1L U 1R D 2L U 2L D
1 2 3 4 5 6 7 8 9
D 4R U 2L D 1R U 1L D 1R U 3L D
1 2 3 4 5 6 7 8 9
D 4R U 1L D 1L U 2L D
1 2 3 4 5 6 7 8 9
so the shortest is D 4R U 1L D 1L U 2L D, or, spelled out, DRRRRULDLULLD, which is 13 moves. The first two have 17 and 19 moves respectively when spelled out.
There are two "shortest" ways of reversing the 9 blocks:
U 4R D 4L U 3R D 1R U 2L D 2L U 3R D
9 8 7 6 5 4 3 2 1
U 3L D 2R U 2R D 1L U 3L D 4R U 4L D
9 8 7 6 5 4 3 2 1
They are shortest under the consideration that 4R for example counts as one move. There's no guarantee that another solution might not be shorter in the sense that the total individual L's and R's might be lower when they are spelled out (they amount to 27 here). A later version was run to a depth of 9 groups of R's and L's and found, among others
U 2R D 1L U 4R D 1L U 1L D 3R U 4L D 1R U
4 3 2 1 9 8 7 6 5
which has only 26 individual moves when spelled out, but it requires 4 additional L's to get to an actual 987654321 starting at position 1, bringing the total moves to 30. It also leaves the grooves' contents in the up position, rather than the down.
Note that the two 27-move solutions are mirror images of one another, with the initial 4R in the first solution corresponding to the final 4L in the second solution. That's of course the case, as backtracking to change 987654321 into 123456789 uses the same moves as a different way to change 123456789 into 987654321.
In the programs below, note that:
1. It's assumed that the sequence begins with a U or a D. If that had failed, we'd have tweaked the program to start with an L or R.
2. It's assumed that the sequence also ends with a U or a D. In that case, manual intervention would just add the final sequence of L's or R's.
Initially the difference between U and D was ignored, as that does not matter for the solution--just that certain positions are exchanged with holding places between sets of L or R moves.
The programs are essentially the same, just with different starting points and goals:
For part 1:
DECLARE SUB twist (lvl!)
DIM SHARED hold(3), offset
DIM SHARED ring(9)
DIM SHARED h(10), sCt
hold(1) = 6
hold(2) = 7
hold(3) = 1
ring(1) = 2
ring(2) = 3
ring(6) = 4
ring(7) = 9
ring(8) = 8
ring(9) = 5
CLS
twist 1
PRINT sCt
SUB twist (lvl)
REDIM hh(3), hr(9)
FOR i = 1 TO 3
hh(i) = hold(i)
NEXT
FOR i = 1 TO 9
hr(i) = ring(i)
NEXT
pa = (4 + offset) MOD 9: IF pa = 0 THEN pa = 9
pb = (6 + offset) MOD 9: IF pb = 0 THEN pb = 9
pc = (9 + offset) MOD 9: IF pc = 0 THEN pc = 9
SWAP hold(1), ring(pa)
SWAP hold(2), ring(pb)
SWAP hold(3), ring(pc)
good = 1
FOR i = 1 TO 8
IF (ring(i + 1) - ring(i) + 9) MOD 9 <> 1 THEN good = 0: EXIT FOR
NEXT
IF good THEN
PRINT "D ";
FOR i = 1 TO lvl - 1
IF h(i) > 4 THEN
PRINT LTRIM$(STR$(9 - h(i))); "L ";
ELSE
PRINT LTRIM$(STR$(h(i))); "R ";
END IF
IF i MOD 2 = 1 THEN PRINT "U "; : ELSE PRINT "D ";
NEXT
PRINT
FOR i = 1 TO 9
PRINT ring((i + offset - 1) MOD 9 + 1);
NEXT
PRINT : PRINT
sCt = sCt + 1
GOTO eSub
END IF
IF lvl > 6 THEN GOTO eSub
FOR amt = 1 TO 8
offset = offset - amt: IF offset < 0 THEN offset = offset + 9
h(lvl) = amt
twist lvl + 1
offset = (offset + amt) MOD 9
NEXT
eSub:
FOR i = 1 TO 3
hold(i) = hh(i)
NEXT
FOR i = 1 TO 9
ring(i) = hr(i)
NEXT
END SUB
For part 2:
DECLARE SUB twist (lvl!)
DIM SHARED hold(3), offset
DIM SHARED ring(9)
DIM SHARED h(10), sCt
FOR i = 1 TO 9: ring(i) = i: NEXT
CLS
twist 1
PRINT sCt
SUB twist (lvl)
REDIM hh(3), hr(9)
FOR i = 1 TO 3
hh(i) = hold(i)
NEXT
FOR i = 1 TO 9
hr(i) = ring(i)
NEXT
pa = (4 + offset) MOD 9: IF pa = 0 THEN pa = 9
pb = (6 + offset) MOD 9: IF pb = 0 THEN pb = 9
pc = (9 + offset) MOD 9: IF pc = 0 THEN pc = 9
SWAP hold(1), ring(pa)
SWAP hold(2), ring(pb)
SWAP hold(3), ring(pc)
good = 1
FOR i = 1 TO 8
IF (ring(i) - ring(i + 1) + 9) MOD 9 <> 1 THEN good = 0: EXIT FOR
NEXT
IF good THEN
PRINT "U ";
FOR i = 1 TO lvl - 1
IF h(i) > 4 THEN
PRINT LTRIM$(STR$(9 - h(i))); "L ";
ELSE
PRINT LTRIM$(STR$(h(i))); "R ";
END IF
IF i MOD 2 = 1 THEN PRINT "D "; : ELSE PRINT "U ";
NEXT
PRINT
FOR i = 1 TO 9
PRINT ring((i + offset - 1) MOD 9 + 1);
NEXT
PRINT : PRINT
sCt = sCt + 1
GOTO eSub
END IF
IF lvl > 7 THEN GOTO eSub
FOR amt = 1 TO 8
offset = offset - amt: IF offset < 0 THEN offset = offset + 9
h(lvl) = amt
twist lvl + 1
offset = (offset + amt) MOD 9
NEXT
eSub:
FOR i = 1 TO 3
hold(i) = hh(i)
NEXT
FOR i = 1 TO 9
ring(i) = hr(i)
NEXT
END SUB
|
|
Posted by Charlie
on 2009-01-09 20:29:22 |
computer solution
