Solve the Rotation puzzle

Question

On some old Nokia phones, there was a variation of the fifteen puzzle called Rotation. In this variation, instead of sliding one tile at a time, you rotated four tiles at a time in one direction.

In this game, you'd start out with a board like this:

4 9 2
3 5 7
8 1 6

And by rotating the lower-left block twice clockwise and the upper-left block once clockwise, you'd get this:

4 9 2
8 3 7
1 5 6

4 9 2
1 8 7
3 5 6

1 4 2
8 9 7
3 5 6

and the 1 tile would be in the top-left corner where it's supposed to be. Eventually, after a few more moves, you'd end up with:

1 2 3
4 5 6
7 8 9

which is the "original" configuration.

Your task is to build a program that will take as input a 3x3 grid of numbers from 1 to 9 (in any format you choose) and return as output a sequence of moves representing the moves you must take to return the board back to its original configuration (again, in any format you choose). The legal moves are defined as moving the [top/bottom]-[left/right] block of 4 tiles [clockwise/counterclockwise].

Your program must be able to solve all possible 3x3 grids (all permutations are solvable).

The shortest code to do this wins.

Answer 1

GolfScript, 39/83 bytes

# Optimized for size:

{.4rand.p.2/+>`{?1420344440`=}+$..$>}do

# Optimized for speed:

6,(7++:t;~{.(1=.@7=9=+4\-rand+..2/+@.@>:s^[3s=0s=2s=4s=1s=]+s|.)9<\t>|}do.$>30764`*

Speed vs size

The size-optimized version randomly chooses clockwise rotations until the desired permutation is achieved. This is sufficient, since a counterclockwise rotation is equivalent to three consecutive clockwise rotations of the same square.

The speed-optimized version does the same, except for the following:

1. If the number 1 is in the upper left corner, it doesn't rotate the upper left square anymore.

2. If the number 9 is in the lower right corner, it doesn't rotate the lower right square anymore.

3. The steps for swapping positions 7 and 8 are hardcoded, so there are two positions that allow the loop to break.

Aside from changing the algorithm, the speed-optimized version achieves the rotation in a straightforward manner, while the size-optimed version uses GolfScript's built-in sort by mapping. It also hardcodes the final state (for comparison) instead of sorting the state in every iteration.

The speed-optimized version requires fewer iterations and every iteration is much faster by itself.

Benchmarks

I have used the following code to randomize the positions of the numbers and perform test runs, uncommenting the line corresponding to the version to be tested:

[{[
    0:c;10,1>{;2 32?rand}$
    #{c):c;.4rand.2/+>`{?1420344440`=}+$..$>}do
    #6,(7++:t;{.(1=.@7=9=+4\-rand+..2/+@.@>:s^[3s=0s=2s=4s=1s=]+s|.)9<\t>|}do.$>30764`*
],c+}\~*]

$.0='Min: '\+puts .-1='Max: '\+puts ..{+}*\,/'Avg: '\+puts .,2/='Med: '\+

The output shows the minimum and maximum number of steps it took to order the numbers, the the average and the median of all runs, as well as the elapsed time in seconds:

$ TIME='\n%e s' time golfscript rotation-test-size.gs <<< 100
Min: 4652
Max: 2187030
Avg: 346668
Med: 216888

21500.10 s
$
$ TIME='\n%e s' time golfscript rotation-test-speed.gs <<< 1000
Min: 26
Max: 23963
Avg: 3036
Med: 2150

202.62 s

On my machine (Intel Core i7-3770), the mean execution time of the size-optimized version was 3.58 minutes. The mean execution time of the speed-optimized version was 0.20 seconds. Thus, the speed-optimized version is approximately 1075 times faster.

The speed-optimized version yields 114 times less rotations. Performing each rotation is 9.4 times slower, which is mainly due to how the state is updated.

I/O

The output consists of 3-bit numbers. The MSB is set for counterclockwise rotations, the middle bit is set for lower squares and the LSB is set for right squares. Thus, 0 (4) is the upper left square, 1 (5) the upper right one, 2 (6) the lower left and 3 (7) the lower right one.

The speed-optimized version prints all rotations on a single line. The size-optimized version prints one rotation per line, followed by the final position of the numbers.

For the speed-optimized version, the input has to yield an array containing the numbers from 1 to 9 when evaluated. For the size-optimized version, the input has to be a string without final newline; it does not get evaluated.

Example runs:

$ echo -n '253169748' | golfscript rotation-size.gs
3
0
123456789
$ golfscript rotation-speed.gs <<< '[5 4 7 1 2 9 3 8 6]'
2210300121312212222212211121122211122221211111122211211222112230764

Size-optimized code

{               #
  .             # Duplicate the state.
  4rand         # Push a randomly chosen integers between 0 and 3.
  .p            # Print that integer.
  .2/+          # Add 1 to it if it is grater than one. Possible results: 0, 1, 3, 4
  >`            # Slice the state at the above index.
  {             # Push a code block doing the following:
    ?           # Get the index of the element of the iteration in the sliced state.
    1420344440` # Push the string "14020344440".
    =           # Retrieve the element at the position of the computed index.
  }+            # Concatenate the code block with the sliced state.
  $             # Sort the state according to the above code block. See below.
  ..$>          # Push two copies of the state, sort the second and compare the arrays.
}do             # If the state is not sorted, repeat the loop.

Updating the state is achieved in the following fashion:

Rotation 2 yields the integer 3 after adding 1. If the state is “123456789”, slicing the state yields “456789”.

Right before executing “$”, the topmost elements of the stack are:

[ 1 2 3 4 5 6 7 8 9 ] { [ 4 5 6 7 8 9 ] ? "1420344440" = }

“$” executes the block once for every element of the array to be sorted, after pushing the element itself.

The index of 1 in “[ 4 5 6 7 8 9 ]” is -1 (not present), so the last element of "1420344440" is pushed. This yields 48, the ASCII code corresponding to the character 0. For 2 and 3, 48 gets pushed as well.

The integers pushed for 4, 5, 6, 7, 8 and 9 are 49, 52, 50, 48, 51 and 52.

After sorting, the first element of the state will be one of the elements yielding 48; the last will be one of those yielding 52. The built-in sort is unstable in general, but I've verified empirically that it is stable in this particular case.

The result is “[ 1 2 3 7 4 6 8 5 9 ]”, which corresponds to a clockwise rotation of the lower left square.

Speed-optimized code

6,(7++:t;       # Save [ 1 2 3 4 5 7 ] in variable “t” and discard it.
~               # Interpret the input string.
{               #
  :s            # Duplicate the current state.
  (1=           # Unshift the first element and push 1 if it is equal to 1 and 0 otherwise.
  .@            # Duplicate the boolean and rotate the unshifted array on top of it.
  7=9=          # Push 1 if the eighth element of “s” is equal to 9 and 0 otherwise.
  +4\-          # Add the booleans and subtract their sum from 4.
  rand          # Push a randomly chosen integers between 0 and the result from above.
  +.            # Add this integer to the first boolean and duplicate it for the output.
  .2/+          # Add 1 to the result if it is grater than one. Possible results: 0, 1, 3, 4
  @.            # Rotate the state on top of the stack and duplicate it.
  @>:s          # Slice the state at the integer from above and save the result in “s”.
  ^             # Compute the symmetric difference of state and sliced state.
  [             # Apply a clockwise rotation to the sliced array:
    3s=         # The fourth element becomes the first.
    0s=         # The first element becomes the second.
    2s=         # The third element remains the same.
    4s=         # The fifth element becomes the fourth.
    1s=         # The second element becomes the fifth.
  ]             # Collect the results into an array.
  +             # Concatenate with array of elements preceding the slice.
  s|            # Perform set union to add the remaining elements of “s”.
  .             # Duplicate the updated state.
  )9<           # Pop the last element; push 0 if it is equal to 9 and 1 otherwise.
  \t            # Swap the popped state on top and push [ 1 2 3 4 5 7 ].
  >             # Push 0 if the state begins with [ 1 2 3 4 5 6 ] and 1 otherwise.
  |             # Take the logical OR of the booleans.
}do             # If the resulting boolean is 1, repeat the loop.
.$              # Duplicate the state and sort it.
>30764`*        # If the state was not sorted, 7 and 8 are swapped, so push "30764".

Observe that the rotations 3, 0, 7, 6 and 4 swap the elements in positions 7 and 8, without altering the positions of the remaining seven elements.

Answer 2

Python with Numpy – 158

from numpy import*
A=input()
while any(A.flat>range(1,10)):i,j,k=random.randint(0,2,3);A[i:i+2,j:j+2]=rot90(A[i:i+2,j:j+2],1+2*k);print"tb"[i]+"lr"[j]+"wc"[k]

Input has to be of the following format:

array([[1,2,5],[4,3,6],[7,8,9]])

Each output line is a move encoded in strings like trw or blc and to be read as follows:

• t: top
• b: bottom
• l: left
• r: right
• c: clockwise
• w: counter-clockwise (widdershins)

---

This program performs random moves until the target configuration is reached. Under the approximative assumption that every move has an independent probability of 1/9! to hit the target configuration¹, the number of rotations before a solution is exponentially distributed with a mean (i.e., the average number of moves) of 9! ≈ 3.6·10⁵. This is in accordance with a short experiment (20 runs).

^{¹ 9! being the total number of configurations.}

Answer 3

C++ fewest moves solution -- breadth first (1847 chars.)

After a bit more thought, I think I have this done much more efficiently and more sensibly. This solution, while it is certainly not winning this golf, is so far the only one that will attempt to find the shortest number of rotations that will solve the board. So far, it solves every random board I've thrown at it in nine or fewer moves. It also performs significantly better than my last one and, hopefully, addresses Dennis's comments below.

From the previous solution, the largest change was to move the key history from the board state (BS) into a new class that stores the history at a given depth (DKH). Any time the application makes a move, it checks the history at that depth and all depths prior to see if it's ever been evaluated, if so, it won't be added to the queue again. This seems to significantly reduce the storage on the queue (by removing all this history from the board state itself) and therefore reduces pretty much all the stupid pruning I had to do to keep the code from running out of memory. Plus it runs a lot faster since there is much less to copy onto the queue.

Now, it's a simple breadth first search on the various board states. Plus, as it turns out, my want to change the key set (currently stored as set of numbers in base-9, each of which are computed by BS::key as the base-9 representation of the board) over to a bitset having 9! bits seems to be needless; though I did find out how to compute a key in the "factorial number system" which could have been used to compute the bit in the bitset to test/toggle.

So, the newest solution is:

#include <iostream>
#include <list>
#include <set>
#include <vector>
using namespace std;
struct BS{
#define LPB(i) for(int*i=b;i-b<9;i++)
struct ROP{int t, d;};
typedef vector<ROP> SV;
typedef unsigned int KEY;
typedef set<KEY> KH;
BS(const int*d){const int*x=d;int*y=b;for(;x-d<9;x++,y++)*y=*x;}
BS(){LPB(i)*i=i-b+1;}
bool solved(){LPB(i)if(i-b+1!=*i)return 0;return 1;}
void rot(int t, int d){return rot((ROP){t,d});}
void rot(ROP r){rotb(r);s.push_back(r);}
bool undo(){if (s.empty())return false;ROP &u=s.back();u.d*=-1;rotb(u);s.pop_back();return true;}
SV &sol(){return s;}
KEY key(){KEY rv=0;LPB(i){rv*=9;rv+=*i-1;}return rv;}
int b[9];
SV s;
void rotb(ROP r){int c=r.t<2?r.t:r.t+1;int bi=(r.d>0?3:4)+c;const int*ri=r.d>0?(const int[]){0,1,4}:(const int[]){1,0,3};for(int i=0;i<3;i++)swap(b[bi],b[c+ri[i]]);}
};
ostream &operator<<(ostream &o, BS::ROP r){static const char *s[]={"tl","tr","bl","br"};o<<s[r.t]<<(r.d<0?"w":"c");return o;}
struct DKH{
~DKH(){for(HV::iterator i=h.begin();i<h.end();++i)if(*i!=NULL)delete *i;}
void add(int d,BS b){h.resize(d+1);if(h[d]==NULL)h[d]=new BS::KH();h[d]->insert(b.key());}
bool exists(BS &b){BS::KEY k=b.key();size_t d=min(b.sol().size(),h.size()-1);do if (h[d]->find(k)!=h[d]->end())return true;while(d--!=0);return false;}
typedef vector<BS::KH *> HV;HV h;
};
static bool solve(BS &b)
{
const BS::ROP v[8]={{0,-1},{0,1},{1,-1},{1,1},{2,-1},{2,1},{3,-1},{3,1}};
DKH h;h.add(0,b);
list<BS> q;q.push_back(b);
while (!q.empty())
{
BS qb=q.front();q.pop_front();
if (qb.solved()){b=qb;return true;}
int d=qb.sol().size()+1;
for (int m=0;m<8;++m){qb.rot(v[m]);if (!h.exists(qb)){h.add(d,qb);q.push_back(qb);}qb.undo();}
}
return false;
}
int main()
{
BS b((const int[]){4,9,2,3,5,7,8,1,6});
if (solve(b)){BS::SV s=b.sol();for(BS::SV::iterator i=s.begin();i!=s.end();++i)cout<<*i<<" ";cout<<endl;}
}

Answer 4

CJam - 39

l{4mr_o_1>+_@m<_[Z0Y4X]\f=\5>+m>__$>}g;

Another random solver :)
It takes a string such as 492357816 and outputs a (long) series of digits from 0 to 3, each representing a clockwise rotation of a block: 0=top-left, 1=top-right, 2=bottom-left, 3=bottom-right.

Brief explanation:

4mr generates a random number from 0 to 3
_1>+ increments the number if it's greater than 1 (so we end up with 0, 1, 3 or 4 - the starting indexes of the 4 blocks)
m< rotates the string to the left (such as 492357816 -> 923578164, not the block rotation) in order to bring the block to rotate in the first position
[Z0Y4X]\f= does the block rotation which affects the first 5 characters, such as 12345 -> 41352;
X=1, Y=2, Z=3 so [Z0Y4X] is actually [3 0 2 4 1] and those are the 0-based indexes of the rotated tiles
5> copies the rest of the string
m> rotates the (modified) string back to the right
__$> checks if the string is sorted (it's the stopping condition)

Answer 5

Mathematica, 104 chars

We can interpret the task in the language of permutation groups. The four rotations are just four permutations that generate the symmetric group S₉, and the task is just to write a permutation as a product of the generators. Mathematica has a built-in function to do this.

i={1,2,5,4};GroupElementToWord[PermutationGroup[Cycles/@({i}+#&/@i-1)],Input[]~FindPermutation~Range@9]

Example:

Input:

{4, 9, 2, 8, 3, 7, 1, 5, 6}

Output:

{-2, -3, -4, 2, 4, 1, 4, -1, -2, 3, 2, -4, 3, 4, -3, -3, -4, -4, -2, -2, -3, -2, 3, -1}

• 1: top-left clockwise
• 2: top-right clockwise
• 3: bottom-right clockwise
• 4: bottom-left clockwise
• -1: top-left counterclockwise
• -2: top-right counterclockwise
• -3: bottom-right counterclockwise
• -4: bottom-left counterclockwise