Another overlapping-orbits puzzle

Most of you will probably have heard of Rubik's Cube. (Who'm I kidding, it's all but certain that anyone reading my blah knows of the Cube; some of you are probably pretty good Cubemeisters.)

The essence of the Cube, to me, is overlapping orbits. That is, there are various things (cubie faces, for the Cube) that occupy spaces (cubicles faces) and can be moved through those spaces in various ways that overlap. (To be sure, the Cube is one of the best of the overlapping-orbits puzzles, for various reasons.)

Another example, one that perhaps makes the overlapping-orbits nature of such puzzles even clearer, is one I saw consisting of two circles with small balls in them, overlapping at two points. Either circle can be rotated either direction, shifting balls into and out of the overlap points.

That one is relatively uninteresting, because there are only two overlapping points out of many (40?) objects. The Cube is much more interesting, in that most possible orbits overlap heavily (three out of eight cubies overlap; if you ignore face centres, eight out of twenty facies).

I have an old cellphone, a Nokia 5190. It has a few games built in. One of them is an overlapping-orbits puzzle. On its (supposedly) easiest setting, it consists of a 3x3 grid, filled with the numbers 1 through 9, which you are supposed to put in numerical order. The motions you have available are to rotate one of the four 2x2 contiguous sub-grids either of the two possible directions. (On harder settings, the grid gets larger and, for 4x4 and larger grids, some settings use rotations of 3x3 subgrids instead of 2x2.)

I was looking at this and found myself not infrequently ending up just a single exchange from solved. I know that in some such puzzles, a single exchange is not solvable (the so-called 15 puzzle is an example; it permits only even permutations if you fix the location of the empty space). Looking at this one in more detail, it looked to me as though a single rotation was an odd permutation and, thus, all possible permutations likely are achievable.

I did some back-of-the-envelope calculations and concluded that the 3x3 version should be within reach of simple brute-force search. There are at most 9!, or 362880, possible orderings of those nine numbers, and even a trivial representation as base-9 numbers has a space of only 387420489 possible values.

I just did this. It's a mathematically small puzzle, smaller than even the 2x2x2 Cube, even though all of those possible permutations are actually reachable (the 3-Cube has only one-twelfth of the possible arrangements accessible from any given start state; while I'd have to think more to be sure, I think for 2-Cube it's one-sixth).

Most positions are either 7 or 8 rotations from the goal state, and none are further than 11. The full breakdown is, in order of increasing distance: 1, 8, 52, 328, 1996, 11336, 51582, 130042, 125929, 39706, 1880, 20. If we restrict ourselves to rotations in only one direction, the breakdown is 1, 4, 16, 64, 250, 960, 3553, 12324, 37308, 84234, 116769, 82197, 23529, 1656, 14, 1; the commonest distance is 10 turns, and, surprisingly (at least to me), there is a unique pattern at maximal distance. Symmetry constraints mean there are only a few possibilities for it; it turns out to be the one formed by rotating the four corners among themselves. Which way you rotate them depends on which kind of rotation you permit (of course) and on whether you want the pattern that is hardest to get to from start or the one that is hardest to get to start from (which are not the same in the case where we allow only one direction of rotation). For example, if our goal state is

1 2 3
4 5 6
7 8 9

3 2 9
4 5 6
1 8 7

7 2 1
4 5 6
9 8 3

I had a brief look at the 4x4 version; it has 16! = 20922789888000 states, of which I expect all to be reachable. This is out of reach for the techniques I've used here; it would take something much more sophisticated to analyze it to the point of knowing God's algorithm for it as my program does for the 3x3.