在矩阵中排列八个连续的数字，使得没有两个数字相邻

Question

需要在下图中编号1到8，使得相邻小区中的两个数字彼此不连续模式：

     *
    ***
    ***
     *

其中每个 * 包含 1 到 8 之间的数字，并且没有两个相邻 * 是连续的数字。

Answer 1

如果您尝试所有可能的选项，则必须尝试 8 个！选项，但如果你想一想，你会注意到有两个单元格有七个邻居（你需要以任何顺序填充 1 和 8）。这些单元格不能用 2 到 7 之间的任何数字填充，因为每个数字 k 都有两个邻居 k+1 和 k-1 但我们只剩下一个单元格可以用邻居填充。

Answer 2

假设邻居水平和垂直（不是对角线），一个贪婪的解决方案是重新洗牌，直到找到解决方案。您的数组足够小，因此您平均需要重试 24 次以上才能找到匹配项。

import java.util.Random;

public class EightPattern {
    private static Random rnd = new Random();

    /*
     * -0-
     * 123
     * 456
     * -7-
     */
    private static boolean isOK(int[] array) {
        if (       Math.abs(array[0] - array[2]) == 1
                || Math.abs(array[1] - array[2]) == 1
                || Math.abs(array[2] - array[3]) == 1
                || Math.abs(array[1] - array[4]) == 1
                || Math.abs(array[2] - array[5]) == 1
                || Math.abs(array[3] - array[6]) == 1
                || Math.abs(array[4] - array[5]) == 1
                || Math.abs(array[5] - array[6]) == 1
                || Math.abs(array[5] - array[7]) == 1) {
            return false;
        }
        return true;
    }

    //shuffle until you find an isOK solution
    public static void patternShuffle(int[] array) {
        do {
            shuffleArray(array);
        }while(!isOK(array));
    }


    //Fisher–Yates shuffle
    static void shuffleArray(int[] ar) {
        for (int i = ar.length - 1; i > 0; i--) {
            int index = rnd.nextInt(i + 1);
            int a = ar[index];
            ar[index] = ar[i];
            ar[i] = a;
        }
    }

    private static void printPattern(int[] array) {
        System.out.println(" " + array[0]);
        System.out.println("" + array[1] + array[2] + array[3]);
        System.out.println("" + array[4] + array[5] + array[6]);
        System.out.println(" " + array[7]);
    }

    public static void main(String args[]) {
        int[] a = new int[]{1,2,3,4,5,6,7,8};
        patternShuffle(a);
        printPattern(a);
    }   
}

在矩阵中排列八个连续的数字，使得没有两个数字相邻

Arrange eight consecutive number in a matrix so that no two number are adjacent

algorithm

dynamic-programming

graph-algorithm

puzzle

sliding-tile-puzzle