All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Games
Shuffle (Posted on 2009-01-09) Difficulty: 3 of 5
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:
                 
1 2 3 4 5 6 7 8 9
      x   x     x

and then after several moves:
U
L
      6   7     1
2 3 x x x 4 9 8 5
                 
R
D
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.

See The Solution Submitted by brianjn    
Rating: 4.5000 (2 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution computer solution | Comment 1 of 4

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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (7)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information