使用回溯使2维数组相等

Question

我在python中尝试使用回溯时遇到了问题。问题是:我必须使两个矩阵相等，只需移动零(上、下、左、右)，例如：

Matrix1:  [ [1,2],
            [3,0]]
Matrix2:  [ [1,0],
            [3,2]]

移动次数:3(您不能使用超过x个移动)

matrix1需要等于matrix2。

答案应该是：

'u' (move zero upwards)

我不知道如何开始:c

PS:对不起，这不是我的第一语言，所以请随时纠正我。

Matrix size: Number of movements: First Matrice: Final Matrice:'

如果输入为:3 3 1 2 3 4 5 6 7 8 0

1 2 3 4 0 5 7 8 6

输出应该是：ul (0用6改变位置，向上移动，然后0用5改变位置，向左移动)。

我不知道如何使用回溯。

我正在尝试这样做：

def safe(x, y, n): 
    if x>=0 and x<n and y>=n and y<n:  
        return True  
    return False  

def whereszero(maze): 

    for x in range(len(maze)):  
        for y in range(len(maze)):  
            if maze[x][y]==0:  
              return x, y  



def main():  
    n=int(input("Matrice size:"))  #matrice dimensions  
    matrice1=[int(x) for x in input().split()] for j in range(n)]  
    matrice2=[int(x) for x in input().split()] for j in range(n)]  
    max=int(input("maximum movements:"))  
    zerox, zeroy=whereszero(matrice1) #returns zero index  
    if solved(matrice1, matrice2, zeroX, zeroY, zeroX, zeroY, 0, max, b, list)==False:  
        print("No solution")  
        return False  
    print("Anwser:", list)  
    return True  


def solved(mat1, mat2, zeroinx, zeroiny, x, y, i, max, movements, list):  
    if mat1==mat2:  
        return True  
    if safe(x, y, len(mat1)) and i<=max
        mat1[x][y], mat1[zeroinx][zeroiny]=mat1[zeroinx][zeroiny], mat1[x][y]  
        zeroinx=x  
        zeroint=y  
        list.append("movements")  
            if solved(mat1, mat2, zeroinx, zeroiny, x+1, y, i+1, max, d, list): #try moving downwards  
                return True  
            if solved(mat1, mat2, zeroinx, zeroiny, x-1, y, i+1, max, u, list): #try moving upwards...  
                return True  
            if solve(mat1, mat2, zeroinx, zeroiny, x, y-1, i+1, max, l, list): #left
                return True  
            if solve(mat1, mat2, zeroinx, zeroiny, x, y+1, i+1, max, r, list): #right, i is the number of moviments tried, max is maximum number of movements  
                return True  

        return False # How do I backtrack?  


main()   `

Answer 1

回溯是一种技术，简而言之，你的算法在可能的选择中做出了一些选择，但如果选择没有成功，它就会回来(回溯的名字由此而来)，并尝试下一个可能的选择，直到成功或所有选择都会被尝试。伪代码中的典型解决方案：

func run(state):
    if success: return true
    for choice in possible-choices(state):
        new_state = execute_choice(state, choice)
        if run(new_state):
            return true
    return false

要牢记的事情：

1. 典型的解决方案是递归的，所以有一个最大深度的限制，你可以检查(基于内存)。
2. 你需要在某个时候停止检查新的‘可能选项’。例如，在你的任务中，给定矩阵2x2，你可以想象在永无止境的循环中左，右，左，右0。您需要设置一个硬限制，或者检测到之前出现的state.
3. new_state被命名为这样是有原因的-您需要copy。你需要记住“旧的”状态，这样你才能回到它的状态。如何将其保存在内存中则是另一回事。