如何找到 8-puzzle 的所有可能状态？

Question

我知道有9个！可能状态和 9!/2 可解状态，但我希望能够使用深度优先搜索编写算法来查找所有可能状态并将它们记录在数组中。我将使用 Java 但如果有人可以提供帮助，我更喜欢的是理论？

Answer 1

您可以使用迭代算法，例如 Heap's algorithm 的迭代形式，用于通过交换迭代数组的所有排列。

当 "gap" 不参与交换时，交换将切换奇偶校验。换句话说，如果你解决了这个难题，然后取出两块并将它们放回彼此的位置，这个难题就无法再解决了。对任意两块重复此操作，拼图再次可解。

只有当这两个位置之间的出租车距离为偶数时，与 "gap" 交换一块才会切换奇偶校验。

所以如果你实现了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;
    }
}

如何找到 8-puzzle 的所有可能状态？

How to find all possible states of 8-puzzle?

java

algorithm

depth-first-search

sliding-tile-puzzle