Sort a 3x3 grid by rotating 2x2 subgrids

Question

I am 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 need to sort the grid by turning the 2x2 substrate clockwise or counterclockwise. The above example can be solved as follows:

Turn the upper left side clockwise:

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

Turn the lower right side counterclockwise:

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

Now the grid is sorted.

This is homework, but I just don't get it. Brute-force did not work; I must be able to solve all the grid data in <= 2000 ms. One thing I tried was to try to calculate the value for all 8 possible next moves (rotate all 4 parts in both directions) and then rotate the figure with the best value. This value was calculated by summing all the distances of all numbers from their correct places.

This worked for the above example, but more complex ones are non-go.

Can someone point me in the right direction? Where to begin? Does this problem have a name?

All grilles are 3x3, and the rotating parts are always 2x2.

Thanks in advance.

EDIT: Forgot to mention the biggest thing: I need to find the smallest possible number of turns that sort the grid.

EDIT2:

I implemented a working algorithm with pieces of advice from the whole offer I received. It is annoying that on my machine it runs in the worst case (987654321) for 1.5 s, but on the server that is testing the program, it runs> 2 s, which means that I still need to optimize. My working code is as of 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 optimization tips?

EDIT3:

The implementation of the idea of ​​the Sirko look-up table, as I understand 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 1500-1600 ms every time.

EDIT4: Following Sirko's advice, I was able to reduce the execution time to 600 ms. 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)); } } } 

Many thanks to Sirko and everyone else who also gave me suggestions!

Answer 1

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

As already mentioned, no more

 9! = 362880 

possible permutations for your matrix.

Each permutation can be represented using a 9-digit number containing each digit from 1 to 9 exactly once. We do this by reading the layout, for example,

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

Starting with this, we could use a simple recursive program to pre-calculate the number of permutations needed for each matrix, starting from the solution and generating all the permutations. While this is the case, we remember how many rotations we needed to go to a certain permutation. We use a lookup table to store our results and a stack to store nodes; we still need to process it. On the stack, we use the { node, distance to solution } pairs and initialize it with the { 123456789, 0 } pair, which describes the sorted start of the 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 } } 

Subsequently, we can answer for all given matrices by simply performing a search in our result.

If the queue is always sorted by distance to the solution, we provide a search for the shortest path. If there was no such order, we could first find a longer path and later fall.

---

The algorithm could be further optimized:

• Imagine another search that signals that node has already been added to the queue. Thus, we will significantly reduce the size of the queue.

Answer 2

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

The numbers 1 ... 9 can be arranged in 9 squares in 9! the way. Thus, there can be a maximum of 9 factorial states. The vertices of the graph are these 9! condition. For each 3x3 grid configuration, you can apply 8 different revolutions. Thus, from each vertex there will be 8 edges for 8 other states.

Now you are given the starting vertex of the graph, and you want to find the shortest path to the destination vertex (with sorted numbers). Therefore, simply apply the width of the first search from this source vertex to find the shortest path to the destination vertex.

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

V = 9! = 362880

E = 9! * 8 = 2903040.

But the graph will not contain most of these vertices, since not all states are possible from this initial state. Thus, using the criterion that 10 million calculations are performed on a computer in 1 second, each request can be received in less than 1 second.

Answer 3

I apologize for writing a new answer, but I can not comment on the invin answer (due to the lack of 50 reputation), so I had to do it here.

This BFS algorithm could be further optimized by making sure that you are not expanding from any states you have already visited.

With factoradic, you can imagine any possible condition with a number from 1 to 9! (362880). You can use a simple bool array (size 362880) to track if you have already visited the state before in BFS. You expand only into unvisited conditions, which, in my opinion, significantly reduce the time spent in cases with large steps.