Sort 3x3 grid by rotating 2x2 subgrids

This question originates from this post.

Anyway, I'm trying to solve the following problem:

Given a 3x3 grid with numbers 1-9, for example:

2 8 3
1 4 5
7 9 6

I have to sort the grid by rotating a 2x2 subgrid clockwise or counter-clockwise. The above example could be solved like this:

Rotate the top left piece clockwise:

2 8 3        1 2 3
1 4 5   =>   4 8 5
7 9 6        7 9 6

Rotate the bottom right piece counter-clockwise:

1 2 3        1 2 3
4 8 5   =>   4 5 6
7 9 6        7 8 9

The grid is now 'sorted'.

I have to find the number of least possible moves to get from situation B to situation A (sorted)

My current implementation consists of creating a look-up table for all the possible permutations of the grid (idea from the original thread by user Sirko). The look-up table is a HashMap. I reduce the grids to strings like this:

1 2 3
4 5 6   =>   "123456789"
7 8 9

My current implementation (in Java):

```
import java.util.*;

public class Kiertopeli {
// initialize the look-up table
public static Map lookUp = createLookup();

public static int etsiLyhin(int[][] grid) {
String finale = "";
for(int[] row : grid)
for(int num : row)
finale += Integer.toString(num);

// fetch the wanted situation from the look-up table
return lookUp.get(finale);
}

public static Map createLookup() {
// will hold the list of permutations we have already visited.
Map visited = new HashMap();

Queue q = new ArrayDeque();
q.add(new Object[] { "123456789", 0 });

// just for counting. should always result in 362880.
int permutations = 0;

Object[] str;

creation:
while(!q.isEmpty())
{
str = (Object[])q.poll();

// pick the next non-visited permutation.
while(visited.containsKey((String)str[0])) {
if(q.isEmpty()) break creation;

I guess you could get quite some performance from changing your main data type from String to an byte or integer array like, e.g.:

byte[] sorted = new byte[]() { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

Then you could easily change the identifying code for each permutation to an integer as well. Which could be computed out of the above array like this:

int code =  sorted[8] * 1 +
            sorted[7] * 10 +
            sorted[6] * 100 +
            sorted[5] * 1000 +
            sorted[4] * 10000 +
            sorted[3] * 100000 +
            sorted[2] * 1000000 +
            sorted[1] * 10000000 +
            sorted[0] * 100000000;

This would keep you from using String comparisons inside the Map visited. Generally int operations are faster than the equivalent String operations.

As I already mentioned in my answer to the original question, another improvement would be to look, if a permutation was already added to the queue before. If so, we don't have to do this again as it will yield no new information. This will reduce the put()/poll() operations on the queue by a lot.

You could do this, by introducing a new Set and using this to verify, if a specific permutation has been added to the queue before.

StackExchange Code Review Q#48855, answer score: 3