Как найти все возможные состояния восьмерки?

Question

Я знаю, что их 9! возможных состояний и 9!/2 разрешимых состояний, но я хочу иметь возможность написать алгоритм, использующий поиск в глубину, чтобы найти все возможные состояния и записать их в массив. Я буду использовать Java, но это больше теория, которая мне нужна, если кто-нибудь может помочь?

Answer 1

Вы можете использовать итеративный алгоритм, такой как итеративная форма алгоритма Heap, для повторения всех перестановок массива посредством свопов.

Своп будет переключать паритет, когда "разрыв" не участвует в свопе. Другими словами, если вы решите головоломку, а затем выньте две части и положите их на место друг друга, головоломка больше не будет решаемой. Повторите это с любыми двумя частями, и загадка снова станет решаемой.

Обмен фишки с "зазором" изменит паритет только тогда, когда расстояние между этими двумя позициями будет одинаковым.

Итак, если вы реализуете алгоритм кучи и поддерживаете четность в соответствии с двумя указанными выше правилами, вы можете решить для каждой перестановки, включать ее или нет:

int[] a = {1,2,3,4,5,6,7,8,0}; // 0 represents "gap"
int[] stack = {0,0,0,0,0,0,0,0,0};

System.out.println(Arrays.toString(a));

boolean parity = true;
int i = 0;
int n = a.length;
while (i < n) {
    if (stack[i] < i) {
        int j = i % 2 > 0 ? stack[i] : 0;
        // SWAP a[i], a[j] 
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
        // Toggle parity when "gap" is not moved
        // or it is moved with even taxicab distance
        if (a[i] > 0 && a[j] > 0 || ((i^j)&1) == 0) parity = !parity;
        if (parity) System.out.println(Arrays.toString(a));
        stack[i]++;
        i = 0;
    } else {
        stack[i++] = 0;
    }
}