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!