# Permutation Puzzle Swap Cubies

I've recently launched an online puzzle RAVEL. It's a 3D array of cubes that must be arranged in color-order. A legal move is to slide a row, column, or lane any number of spaces. The cubes that are pushed out the end are inserted at the other end.

I suggest that you visit RAVEL, click the "Experimenter" tab and try some RAVELs of various dimensions so you can better appreciate what follows.

I conjecture that all permutations are solvable but because I don't know for sure, I shuffle the RAVEL with a series of random legal moves.

### Question one:

Is it necessary to shuffle with legal moves? Or could I simply shuffle it with random swaps and have it still be solvable? Put another way: is the conjecture true, are all permutations solvable?

My second question has to do with solution techniques. I solve RAVELs layer-by-layer using ad hoc methods to move cubies into place without altering the positions of already-placed ones. But in the last layer, I use formalized methods for the last several cubies.

### The Cycle 3 algorithm

This algorithm cycles the positions of three cubies leaving all the other cubies in place. The space between the three cubies doesn't matter so long as they form a right angle: cubies 1 & 2 on the same row, cubies 2 & 3 on the same column.

### The algorithm:

• Drag the green cubie to the apex (blue position).
• Drag the red one to the apex position.
• Drag the apex to where green started.
• Drag the apex to where red started.

The numbers in the image show the sequence of moves. To cycle in the opposite direction, switch 1 with 2, and switch 3 with 4.

### Swap Two Cubies

Often you can finish solving the RAVEL using just the procedures above. But sometimes pairs of swapped cubies remain. I don't know of a general algorithm for swapping pairs that works for all sizes of RAVEL. I have managed to solve some examples by just flailing away, trying anything.

I found a procedure to do a pair swap on RAVELs where one of the dimensions equals 4.

The picture shows the sequence of moves to swap the red and green cubies. The vertical dimension must be four.

### Question two:

Can you create a pair swap algorithm that works for all sized RAVELs?

# ☺ ☺ ☺

This puzzle is a 3d version of one that is available in Simon Tatham's puzzle collection under the name Sixteen. This puzzle has been discussed here before: Techniques for solving row column sliding puzzles

The answer there applies here as well, so I won't go into great detail.

Question 1:

Every permutation with even parity is possible, and easily solvable using the 3-cycles. If all dimensions are odd, then every move is an even permutation, so then no odd permutations are possible. In particular, no single swap is possible in that case. If at least one dimension is even, then odd permutations are available too so then all permutations are solvable.

Question 2:

If one or more dimensions is even, then a shift along such a dimension is an odd permutation. Therefore you can do such a shift, and solve most of the shifted pieces with 3-cycles, and be left with a single swap.
Suppose A is a move that shifts a line containing $$2n$$ blocks, B is a shift of an intersecting line of blocks, and B' is the reverse of B. Then the move sequence BAB'A repeated $$n-1$$ times, followed by BAAB'A, will have the effect of swapping two adjacent blocks in the A line.

• Thanks for your knowledgeable, concise, and rapid reply! Having trouble confirming BAB'A repeated n times. Vertical dim=6, Horizontal = 3. n = 6/2 = 3. So I do BAB'ABAB'ABAB' then the A line is all out of order. If I then do AA, there is then a swapped pair -- one one the B line and one on the A line, both next to the intersection. (I'm shifting by one space) I hope it's my bad, 'cause your answer is so clean! – CoolRoar Sep 16 '20 at 22:28
• @CoolRoar: You're right I messed up the move sequence, as I wrote it up off the top of my head without thoroughly checking. Instead of omitting an A move at the end, you have to put an extra one in. I think I fixed it now. – Jaap Scherphuis Sep 17 '20 at 4:48
• Answered! And I'll link here from RAVEL page. Thanks! – CoolRoar Sep 17 '20 at 13:24