graph - 通过交换转换矩阵的最小步骤数

Question

我偶然发现了以下问题，但无法解决，有人可以告诉我这里的方法是什么

标签： graphdepth-first-searchbreadth-first-search

Answer 1

没有办法做到这一点，除非通过暴力，递归。对于每个位置不正确的图块，最多可以进行 4 次交换。您进行交换，然后将此新位置添加到您未尝试过的列表中，确保不要回到您以前见过的任何位置。跟踪递归的深度，当你得到最终位置时，深度就是答案。

incoming = (7,3,2,4,1,5,6,8,9)
answer = (1,2,3,4,5,6,7,8,9)
primes = (2,3,5,7,11,13,17)

def solve(base, depth):
    seen = set()
    untried = [(base,0)]

    while untried:
        array,depth = untried.pop(0)
        print(depth, array)
        if array == answer:
            print( "ANSWER!", depth )
            return depth
        if array in seen:
            print("seen")
            continue
        seen.add( array )

        for n in range(9):
            if array[n] == n+1:
                continue
            for dx in (-1, -3, 1, 3):
                if 0 <= n+dx < 9 and array[n]+array[n+dx] in primes:
                    # attempt a swap.
                    a = list(array)
                    a[n],a[n+dx] = a[n+dx],a[n]
                    untried.append((tuple(a),depth+1))
    print( "fail" )
    return -1
                
solve( incoming, 0 )