How to think about permutation puzzles?

Question

I know this is a very general question, but these kinds of puzzles are the only ones I can't figure out on my own. Rubik's cube, Twiddle, 16... (the last two are in Simon Tatham's Puzzle collection.)

Is there a general thinking principle that applies to puzzles like these? If not, can you give me an example of how to arrive at the solution for any one of these puzzles? I just can't even begin to think about something with so many interconnected parts.

Answer 1

Permutation puzzles are puzzles in which a random permutation needs to be restored to the identity permutation by using a limited (or 'clumsy') set of moves.

For example, with the Rubik's cube, you would like to be able to swap two corners by themselves, but you can't do this directly - you can only rotate faces.

A key feature is then to find - and hopefully optimize - the solving process.

For example, consider that you are only allowed to rotate three elements of a permutation forwards, e.g. $abc\to cab\to bca\to abc$. The three elements do not need to be consecutive.

Then $1234\to4321$ can be done in four steps:

 1234
 3124
 3412
 3241
 4321

Or:

 1234
 1423
 2143
 4213
 4321

But can it be done in three moves or less? And if not, why not?

It can:

 1234
 4132
 4213
 4321

And, as the OP found, a solution in 2:

 1234
 4213
 4321

The challenge is now to find the shortest solution to reverse n numbers, but that's a different question!

My example shows how the straightforward approach is not necessarily the shortest, but the easiest to construct. So to solve a permutation puzzle, construct the 'obvious' solution first, and then try to find shortcuts.