Sort 3x3 grid by rotating 2x2 subgrids

Question

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'.

This IS a homework, but I'm just not getting this. Brute forcing didn't work; I have to be able to solve all given grids in <= 2000ms. One thing I tried was trying to calculate a value for all 8 possible next moves (rotate all 4 pieces in both directions), and then rotate the piece with the best value. This value was calculated by summing together all the distances of all the numbers from their correct places.

This worked for the above example, but more difficult ones are a no-go.

Could anyone point me into the correct direction? Where should I start? Does this problem have a name?

All grids are 3x3 and the rotating pieces are always 2x2.

Thanks in advance.

EDIT: Forgot to mention the biggest thing: I have to find the smallest possible amount of turns that sorts the grid.

EDIT2:

I implemented a working algorithm with bits of advice from all the suggestion I've received. The annoying thing is, on my machine it runs the worst case scenario (987654321) in 1,5s, but on the server that tests the program it runs >2s, which means I still need to optimize. My working code as it is now

int find(int[][] grid) {

    Queue q = new ArrayDeque<String>();
    Map<String, Boolean> visited = new HashMap<String, Boolean>();

    Object[] str = new Object[] { "", 0 };
    for(int[] row : grid)
        for(int num : row)
            str[0] += Integer.toString(num);

    q.add(str);

    while(!q.isEmpty()) {            
        str = (Object[])q.poll();
        while(visited.containsKey((String)str[0])) str = (Object[])q.poll();

        if(((String)str[0]).equals("123456789")) break;

        visited.put((String)str[0], Boolean.TRUE);

        for(int i = 0; i < 4; i++) {

            String[] kaannetut = kaanna((String)str[0], i);

            Object[] str1 = new Object[] { (String)kaannetut[0], (Integer)str[1]+1 };
            Object[] str2 = new Object[] { (String)kaannetut[1], (Integer)str[1]+1 };

            if(!visited.containsKey((String)str1[0])) q.add((Object[])str1);
            if(!visited.containsKey((String)str2[0])) q.add((Object[])str2);
        }
    }

    return (Integer)str[1];

}

Can anyone come up with any optimizing tips?

EDIT3:

An implementation from the look-up table idea by Sirko, as I understood it:

import java.util.*;

class Permutation {
    String str;
    int stage;
    public Permutation(String str, int stage) {
        this.str = str;
        this.stage = stage;
    }
}

public class Kiertopeli {    
    // initialize the look-up table
    public static Map<String, Integer> 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<String, Integer> createLookup() {
        // will hold the list of permutations we have already visited.
        Map<String, Integer> visited = new HashMap<String, Integer>();

        Queue<Permutation> q = new ArrayDeque<Permutation>();
        q.add(new Permutation("123456789", 0));

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

        Permutation permutation;

        creation:
        while(!q.isEmpty())
        {
            permutation = q.poll();

            // pick the next non-visited permutation.
            while(visited.containsKey(permutation.str)) {
                if(q.isEmpty()) break creation;
                permutation = q.poll();
            }

            // mark the permutation as visited.
            visited.put(permutation.str, permutation.stage);

            // loop through all the rotations.
            for(int i = 0; i < 4; i++) {

                // get a String array with arr[0] being the permutation with clockwise rotation,
                // and arr[1] with counter-clockwise rotation.
                String[] rotated = rotate(permutation.str, i);

                // if the generated permutations haven't been created before, add them to the queue.
                if(!visited.containsKey(rotated[0])) q.add(new Permutation(rotated[0], permutation.stage+1));
                if(!visited.containsKey(rotated[1])) q.add(new Permutation(rotated[1], permutation.stage+1));

            }

            permutations++;
        }

        System.out.println(permutations);

        return visited;
    }

    public static String[] rotate(String string, int place) {

        StringBuilder str1 = new StringBuilder(string);
        StringBuilder str2 = new StringBuilder(string);

        if(place == 0) { // top left piece
            str1.setCharAt(0, string.charAt(3));
            str1.setCharAt(1, string.charAt(0)); // clockwise rotation
            str1.setCharAt(4, string.charAt(1)); //
            str1.setCharAt(3, string.charAt(4));

            str2.setCharAt(3, string.charAt(0));
            str2.setCharAt(0, string.charAt(1)); // counter-clockwise
            str2.setCharAt(1, string.charAt(4)); //
            str2.setCharAt(4, string.charAt(3));
        }
        if(place == 1) { // top right
            str1.setCharAt(1, string.charAt(4));
            str1.setCharAt(2, string.charAt(1));
            str1.setCharAt(5, string.charAt(2));
            str1.setCharAt(4, string.charAt(5));

            str2.setCharAt(4, string.charAt(1));
            str2.setCharAt(1, string.charAt(2));
            str2.setCharAt(2, string.charAt(5));
            str2.setCharAt(5, string.charAt(4));
        }
        if(place == 2) { // bottom left
            str1.setCharAt(3, string.charAt(6));
            str1.setCharAt(4, string.charAt(3));
            str1.setCharAt(7, string.charAt(4));
            str1.setCharAt(6, string.charAt(7));

            str2.setCharAt(6, string.charAt(3));
            str2.setCharAt(3, string.charAt(4));
            str2.setCharAt(4, string.charAt(7));
            str2.setCharAt(7, string.charAt(6));
        }
        if(place == 3) { // bottom left
            str1.setCharAt(4, string.charAt(7));
            str1.setCharAt(5, string.charAt(4));
            str1.setCharAt(8, string.charAt(5));
            str1.setCharAt(7, string.charAt(8));

            str2.setCharAt(7, string.charAt(4));
            str2.setCharAt(4, string.charAt(5));
            str2.setCharAt(5, string.charAt(8));
            str2.setCharAt(8, string.charAt(7));
        }

        return new String[] { str1.toString(), str2.toString() };
    }

    public static void main(String[] args) {

        String grids = "2 8 3 1 4 5 7 9 6 "
                + "1 6 5 8 7 2 3 4 9 "
                + "1 6 5 8 7 2 3 4 9 "
                + "1 7 6 8 2 5 3 4 9 "
                + "8 1 5 7 4 6 3 9 2 "
                + "9 8 7 6 5 4 3 2 1 ";

        Scanner reader = new Scanner(grids);

        System.out.println();
        while (reader.hasNext()) {
            System.out.println("Enter grid:");
            int[][] grid = new int[3][3];
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    grid[i][j] = reader.nextInt();
                }
            }
            System.out.println(" Smallest: " + etsiLyhin(grid));
        }
    }
}

runs for about 1500-1600ms each time.

EDIT4: By following Sirko's advice I was able to cut the execution time down to 600ms. Here is the code as it is now:

import java.util.*;

class Permutation {
    Byte[] value;
    int stage;
    public Permutation(Byte[] value, int stage) {
        this.value = value;
        this.stage = stage;
    }

    public Byte[][] rotate(int place) {

        Byte[] code1 = value.clone();
        Byte[] code2 = value.clone();

        if(place == 0) { // top left piece
            code1[0] = value[3];
            code1[1] = value[0];
            code1[4] = value[1];
            code1[3] = value[4];

            code2[3] = value[0];
            code2[0] = value[1];
            code2[1] = value[4];
            code2[4] = value[3];
        }

        if(place == 1) { // top right
            code1[1] = value[4];
            code1[2] = value[1];
            code1[5] = value[2];
            code1[4] = value[5];

            code2[4] = value[1];
            code2[1] = value[2];
            code2[2] = value[5];
            code2[5] = value[4];
        }
        if(place == 2) { // bottom left
            code1[3] = value[6];
            code1[4] = value[3];
            code1[7] = value[4];
            code1[6] = value[7];

            code2[6] = value[3];
            code2[3] = value[4];
            code2[4] = value[7];
            code2[7] = value[6];
        }
        if(place == 3) { // bottom left
            code1[4] = value[7];
            code1[5] = value[4];
            code1[8] = value[5];
            code1[7] = value[8];

            code2[7] = value[4];
            code2[4] = value[5];
            code2[5] = value[8];
            code2[8] = value[7];
        }

        return new Byte[][] { code1, code2 };
    }

    public Integer toInt() {
        Integer ival = value[8] * 1 + 
                       value[7] * 10 + 
                       value[6] * 100 + 
                       value[5] * 1000 + 
                       value[4] * 10000 + 
                       value[3] * 100000 + 
                       value[2] * 1000000 + 
                       value[1] * 10000000 + 
                       value[0] * 100000000;

        return ival;
    }
}

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

    public static int etsiLyhin(int[][] grid) {
        Integer finale = toInt(grid);

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

    public static Map<Integer, Integer> createLookup() {
        // will hold the list of permutations we have already visited.
        Map<Integer, Integer> visited = new HashMap<Integer, Integer>();
        Map<Integer, Boolean> queued = new HashMap<Integer, Boolean>();

        Queue<Permutation> q = new ArrayDeque<Permutation>();
        q.add(new Permutation(new Byte[] { 1,2,3,4,5,6,7,8,9 }, 0));
        queued.put(123456789, true);

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

        Permutation permutation;

        creation:
        while(!q.isEmpty())
        {
            permutation = q.poll();

            // pick the next non-visited permutation.
            while(visited.containsKey(permutation.toInt())) {
                if(q.isEmpty()) break creation;
                permutation = q.poll();
            }

            // mark the permutation as visited.
            visited.put(permutation.toInt(), permutation.stage);

            // loop through all the rotations.
            for(int i = 0; i < 4; i++) {

                // get a String array with arr[0] being the permutation with clockwise rotation,
                // and arr[1] with counter-clockwise rotation.
                Byte[][] rotated = permutation.rotate(i);

                // if the generated permutations haven't been created before, add them to the queue.
                if(!visited.containsKey(toInt(rotated[0])) && !queued.containsKey(toInt(rotated[0]))) {
                    q.add(new Permutation(rotated[0], permutation.stage+1));
                    queued.put(toInt(rotated[0]), true);
                }
                if(!visited.containsKey(toInt(rotated[1])) && !queued.containsKey(toInt(rotated[1]))) {
                    q.add(new Permutation(rotated[1], permutation.stage+1));
                    queued.put(toInt(rotated[1]), true);
                }

            }

            permutations++;
        }

        System.out.println(permutations);

        return visited;
    }

    public static Integer toInt(Byte[] value) {
        Integer ival = value[8] * 1 + 
                       value[7] * 10 + 
                       value[6] * 100 + 
                       value[5] * 1000 + 
                       value[4] * 10000 + 
                       value[3] * 100000 + 
                       value[2] * 1000000 + 
                       value[1] * 10000000 + 
                       value[0] * 100000000;

        return ival;
    }

    public static Integer toInt(int[][] value) {
        Integer ival = value[2][2] * 1 + 
                       value[2][1] * 10 + 
                       value[2][0] * 100 + 
                       value[1][2] * 1000 + 
                       value[1][1] * 10000 + 
                       value[1][0] * 100000 + 
                       value[0][2] * 1000000 + 
                       value[0][1] * 10000000 + 
                       value[0][0] * 100000000;

        return ival;
    }

    public static void main(String[] args) {

        String grids = "2 8 3 1 4 5 7 9 6 "
                + "1 6 5 8 7 2 3 4 9 "
                + "1 6 5 8 7 2 3 4 9 "
                + "1 7 6 8 2 5 3 4 9 "
                + "8 1 5 7 4 6 3 9 2 "
                + "9 8 7 6 5 4 3 2 1 ";

        Scanner reader = new Scanner(grids);

        System.out.println();
        while (reader.hasNext()) {
            System.out.println("Enter grid:");
            int[][] grid = new int[3][3];
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    grid[i][j] = reader.nextInt();
                }
            }
            System.out.println(" Smallest: " + etsiLyhin(grid));
        }
    }
}

Huge thanks to Sirko and everyone else who gave me suggestions as well!

Answer 1

This question can be reduced to the shortest paths problem in an undirected unweighted graph.

The numbers 1...9 can be arranged into the 9 squares in 9! ways. So there can be a maximum of 9 factorial states. The vertices of the graph will be these 9! states. For each configuration of the 3x3 grid, you can apply 8 different rotations. So from each vertex, there will be 8 edges to 8 other states.

Now you are given the start vertex of the graph and you want to find the shortest way to reach the destination vertex(with the numbers sorted). So simply apply breadth first search from this source vertex to find the shortest path to the destination vertex.

Running time: For each query, the shortest path will be found in worst case O(E + V) time. In the graph described above,

V = 9! = 362880

E = 9! * 8 = 2903040.

But the graph will not contain most of these vertices as not all states are possible from the given starting state. So using the yardstick that 10 million calculations are run on a computer in 1 second, each query can be answered in lesser than 1 second as desired.

Answer 2

A variant of the already proposed solution would be to generate a lookup table.

As already mentioned there are at most

9! = 362880

possible permutations for your matrix.

Each permutation can be represented using a 9-digit number containing each digit between 1 and 9 exactly once. We do this by reading the matrix rowwise, so, for example:

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

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

Starting from this, we could use a simple recursive program to precalculate the number of permutations necessary for each matrix by starting with the solution and generate all permutations. While doings so, we remember how much rotations it took us, to get to a specific permutation. We use a lookup table to store our results and a stack to store the nodes, we still need to process. In the stack we use pairs { node, distance to solution } and initialize it with the pair { 123456789, 0 }, which describes the sorted starting node.

lookup = [];
queue = [ { 123456789, 0 } ]:

while( there is a node in the queue ) {

  take the first node out of the queue

  // skip nodes we already processed
  if( !(node in lookup) ) {

    generate all permutations possible by using 1 rotation starting form node
      push all generated nodes to the queue using a distance + 1
  }
}

Afterwards we can answer for all given matrices by just a doing lookup in our result.

By having the queue always sorted by the distance to the solution, we ensure to find the shortest path. If there was no such ordering, we might find a longer path first and drop shorter ones later on.

---

One could further optimize the algorithm:

• Introduce another lookup, which signals, that a node as already been added to the queue. That way we would decrease the size of the queue drastically.

Answer 3

I apologize for writing a new answer, but I can't comment on invin's answer (due to not having 50 reputation) so I had to do it here.

This BFS algorithm could be additionally optimized by making sure you're not expanding from any already visited states.

With factoradic you can represent any possible state with a number between 1 and 9! (362880). You can use a simple bool array (size 362880) to keep track if you have already visited a state before in the BFS. You only expand into non-visited states which I believe would drastically reduce the operation time in cases with bigger steps.