java - 通过旋转 2x2 子网格对 3x3 网格进行排序

Question

我正在尝试解决以下问题:

给定一个包含数字 1-9 的 3x3 网格，例如:

2 8 3
1 4 5
7 9 6

我必须通过顺时针或逆时针旋转 2x2 子网格来对网格进行排序。上面的例子可以这样解决:

顺时针旋转左上角:

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

逆时针旋转右下角:

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

网格现在已“排序”。

这是一个家庭作业，但我只是不明白。暴力破解没有用；我必须能够在 <= 2000 毫秒内解决所有给定的网格。我尝试的一件事是尝试计算所有 8 个可能的下一步移动的值(在两个方向上旋转所有 4 个棋子)，然后旋转具有最佳值的棋子。该值是通过将所有数字与其正确位置的所有距离相加计算得出的。

这对上面的例子有效，但更难的是不行的。

谁能指出我正确的方向？我应该从哪里开始？这个问题有名字吗？

所有的网格都是 3x3，旋转的棋子总是 2x2。

提前致谢。

编辑:忘记提及最重要的事情:我必须找到对网格进行排序的尽可能少的转弯数。

编辑2:

我根据收到的所有建议中的一些建议实现了一个工作算法。烦人的是，在我的机器上，它在 1.5 秒内运行了最坏情况 (987654321)，但在测试程序的服务器上它运行了 >2 秒，这意味着我仍然需要优化。我现在的工作代码

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];

}

谁能提出任何优化建议？

编辑3:

根据我的理解，Sirko 的查找表想法的实现:

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));
        }
    }
}

每次运行约1500-1600ms。

EDIT4:按照 Sirko 的建议，我能够将执行时间缩短到 600 毫秒。这是现在的代码:

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));
        }
    }
}

非常感谢 Sirko 和其他给我建议的人!

Answer 1

这个问题可以简化为无向未加权图中的最短路径问题。

数字 1...9 可以排列成 9 中的 9 个正方形!方法。所以最多可以有 9 个阶乘状态。图的顶点将是这 9 个!状态。对于 3x3 网格的每个配置，您可以应用 8 种不同的旋转。所以从每个顶点开始，将有 8 条边到其他 8 个状态。

现在你得到了图的起始顶点，你想找到到达目的地顶点的最短路径(对数字进行排序)。所以只需申请 breadth first search从这个源顶点找到到目标顶点的最短路径。

运行时间:对于每个查询，最短路径将在最坏情况下找到 O(E + V) 时间。在上面描述的图表中，

V = 9! = 362880

E = 9! * 8 = 2903040.

但是该图不会包含大多数这些顶点，因为并非所有状态都可以从给定的起始状态开始。因此，以计算机在 1 秒内运行 1000 万次计算为标准，可以在不到 1 秒的时间内根据需要回答每个查询。