1

隣接セルの 2 つの番号が互いに連続しないように、次の図の 1 から 8 までの番号を付ける必要があります。

     *
    ***
    ***
     *

各 * には 1 から 8 までの数字が含まれており、隣接する * は連続した数字ではありません。

4

2 に答える 2

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);
    }   
}
于 2016-02-06T15:24:22.500 に答える
2

可能なすべてのオプションを試す場合は、8 を試す必要があります。オプションですが、しばらく考えてみると、隣接する 7 つのセルが 2 つあることに気付きます (1 と 8 を任意の順序で埋める必要があります)。これらのセルは、2 から 7 までの任意の数値で埋めることはできません。それぞれの数値 k には 2 つの隣接 k+1 と k-1 があるためです。

_ 2 _
5 8 6
3 1 4
_ 7 _
于 2016-02-06T14:27:28.243 に答える