## Nokia Rotation Game - Solution

The Nokia Rotation game has two major modes: 2x2 and 3x3; each mode can have several board sizes (3x3 or bigger in the 2x2 mode, 4x4 or bigger in the 3x3 mode).

### 2x2 Mode

To solve a game in the 2x2 mode, if the board size is greater than 3x3, first you have to put all numbers that should be outside the upper left 3x3 square to their positions (this is easy). Then put numbers that should be in the upper 2 rows to their positions (this is also easy, practice on a 3x3 game).

Now let's talk about game notation. In the 3x3 square, the rotation frame can be in one of the 4 positions. In each of these positions, the rotation may be done clockwise or counterclockwise. Clockwise rotations are denoted by upper case letters, counterclockwise rotations - by lower case letters.

Here is the table depicting the correspondence between frame positions and letters (for boards sizes greater than 3x3, do the appropriate substitutions, e.g. it will be 1-2-3, 5-6-7, and 9-10-11 for a 4x4 board, but for the sake of simplicity, I'll use numbers 1 to 9):

 1 2 3 A B 4 5 6 C D 7 8 9

After you put all the numbers but 7, 8, and 9 into their final positions, if you have not won the game yet (the probability of winning by chance is 1/6), you will have one of the five combinations: 798, 879, 897, 978, or 987. Here is how to solve them:

CombinationMoves
798cbCDB
879DAdca
897bdBAca
978CabDBA
987cbdcBCC

There are 362,880 possible combinations of 9 numbers. All of them can be solved in 11 moves or less. Here is a C++ program that prints the solutions for all the combinations:

```
#include <map>
#include <deque>
#include <cstdio>

struct pos {
struct pos * parent;
char val;
char conv;
pos(struct pos * p, char v, char c) : parent(p), conv(c) {
memcpy(val, v, 9);
}
void print(bool start = true) {
if (start) printf("%.9s ", val);
if (conv) {
putchar(conv);
parent->print(false);
} else putchar('\n');
}
};

struct poscmp {
bool operator()(char * p, char * q) {
return memcmp(p, q, 9) < 0;
}
};

std::map<char *, pos *, poscmp> full;
std::deque<pos *> active;

void rev(int start, bool dir, char p, char q) {
for (int i = 0; i < 9; i++) {
switch (i - start) {
case 0: p[i] = dir ? q[i+1] : q[i+3]; break;
case 1: p[i] = dir ? q[i+3] : q[i-1]; break;
case 3: p[i] = dir ? q[i-3] : q[i+1]; break;
case 4: p[i] = dir ? q[i-1] : q[i-3]; break;
default:
p[i] = q[i];
}
}
}

void add_permutations(pos * p) {
char perm;
for (char conv = 'A'; conv <= 'D'; conv++) {

// Index of top left corner of rotating frame is
// 0 for A, 1 for B, 3 for C, and 4 for D
int offset = conv - 'A' + (conv >= 'C');

// Skip the rotation that is the opposite of the last in chain
if (p->conv != conv + ('a' - 'A')) {
rev(offset, true, perm, p->val);
if (full.find(perm) == full.end()) {
pos * x = new pos(p, perm, conv);
full[x->val] = x;
active.push_back(x);
}
}

// Same here, try rotating the other way
if (p->conv != conv) {
rev(offset, false, perm, p->val);
if (full.find(perm) == full.end()) {
pos * x = new pos(p, perm, conv + ('a' - 'A'));
full[x->val] = x;
active.push_back(x);
}
}
}
}

int
main(int argc, const char *argv[]) {
pos * x = new pos(0, "123456789", '\0');
full[x->val] = x;
active.push_front(x);

while (!active.empty()) {
pos * p = active.front();
p->print();
active.pop_front();
add_permutations(p);
}
}

```

To get a solution, enter a combination:

If this information helped to provide you peace of mind, or to win a bet, or to impress your friends, relatives, or co-workers, please consider donating a quarter from your PayPal balance:

### 3x3 Mode

Here I'm using a 4x4 game as an example. For bigger boards, do the appropriate substitution.

To solve a game in the 3x3 mode, first put all numbers greater than 8 to their final positions (this is easy). Then, if you're not extremely lucky (the chance of winning at this stage is 1/40320), you'll be left with one of the 40319 permutations of the first 8 numbers. From now on, the rotating frame does not need to leave the top left 4x3 rectangle that contains the numbers 1 to 12. In this rectangle, the rotating frame can only be in two positions: left (A), or right (B). The clockwise rotations are denoted by upper case letters, the counterclockwise rotations - by lower case letters.

All the permutations can be solved by repeatedly applying the basic permutations, like flipping two adjacent numbers.

To flip numbers in positionsDo
1 and 2BaabaBBabaaBAAbabAA
2 and 3aBaabaBBabaaBAAbabAAA
3 and 4aBBABaaBABaaBABaabA
4 and 5bbaaBBabaBBabaBaBAB
5 and 6BabaBBabaBBabaB
6 and 7aBBBABaaBABaaBABaabbA
7 and 8AbabAAbabAAbabA
8 and 1AABABaaBABaaBABAAAA
1 and 5babAABaabaBBabaaBAA
2 and 6aaBabaBBabaBBabaBAA
3 and 7BBaBABaaBABaaBBAbab
4 and 8bAAbAAbAAbbABBAbbAA

Here are some more useful operations:
To achieveDo
Flipping first and second row (56781234)bbbABAbbbaaaBABaaa
Mirroring (43218765)BaaBAABBABABAbaabAbA
Flipping left half and right half (34127856)BaBBAAbABaBBAAbA
Mirroring upper row (43215678)bbaaaBAABaababAAABBA
Mirroring lower row (12348765)ABaabbaBAABBaBBBAAAA

All permutations of the first 8 numbers can be solved in 22 moves or less, the full list is here (350K), or enter a combination:

If this information helped to provide you peace of mind, or to win a bet, or to impress your friends, relatives, or co-workers, please consider donating a quarter from your PayPal balance:

Copyright 2003 Leonid Broukhis -- all rights reserved. Direct linking to this page from any web site, as well as not-for-profit reproduction of this page in its entirety, including this copyright notice, is hereby granted. Any other use of this information is by permission only. (Drop q's and x's before mailing.)
Last modified: June 06, 2003 