魔方的BFS提前终止？

Question

我正在尝试完成广度优先搜索，以找到达到（屏蔽的）魔方排列所需的移动次数，然后将其输出到字典中。

为了测试，我给了它一个立方体，其中所有面（面段）都具有相同的“颜色”，除了一个（这是蒙版立方体） - 因此它应该返回一个字典，其中包含这个唯一面的所有可能位置，并且需要多少步才能到达那里。然而，由于某种原因，它只能找到 4 种排列——小面所在的面每旋转 90 度就有一种排列。我测试了其他面的旋转，它们有效。

我认为这可能与Python没有制作cube/newCube变量的深层副本有关 - 我尝试解决这个问题但无济于事。

from cube import *
from solutionTools import *
from queue import Queue
import json

class Masker:
    def __init__(self):
        pass

    def mask(self, cube: Cube, mask: list, maskTo: list, defaultMask: str="X") -> Cube:
        ifCube = ifCubeGen(cube).constructIFCube().getState()
        outCube = Cube().getState()
        for i in range(6):
            for j in range(3):
                for k in range(3):
                    if ifCube[i][j][k] in mask:
                        outCube[i][j][k] = maskTo[mask.index(ifCube[i][j][k])]
                    else:
                        outCube[i][j][k] = defaultMask
        
        return Cube(state=outCube)
    
class GeneratePruningTable:
    def __init__(self):
        pass

    def BFS(self, start: Cube) -> dict:
        queue: Queue[Cube] = Queue()
        depth = 0
        table = {}
        queue.put(start)
        while queue.qsize() > 0:
            layer_size = queue.qsize()
            while layer_size > 0:
                cube = queue.get()
                key = cube.generateKey()
                if key not in table:
                    table[key] = depth
                    for i in range(6):
                        for j in range(2):
                            newCube = Cube(state=cube.getState().copy())
                            if j == 0:
                                dir = 1
                            else:
                                dir = -1
                            newCube.rotateFace(i, dir)
                            queue.put(Cube(state=newCube.getState().copy()))
                layer_size -= 1
            print(f"Depth {depth} complete")
            depth += 1
        return table
    
    def writeTableToFile(self, table: dict, directory: str):
        with open(directory, "w") as f:
            json.dump(table, f)

cube = Cube()

mask = ["U0"]
maskTo = ["U"]

m = Masker()
masked = m.mask(cube, mask, maskTo)
#masked.rotateFace(4, 1)

#print(masked.generateKey())

gen = GeneratePruningTable()

table = gen.BFS(masked)
gen.writeTableToFile(table, r"testDB.json")

输出（在 testDB.json 中）： - 这表明“U”面保持在 U 面内。

{"UXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX": 0, "XXXXXUXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX": 1, "XXUXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX": 1, "XXXXXXXUXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX": 2}

Answer 1

找到解决方案

我的怀疑是正确的，但我愚蠢地认为我正在使用 list.copy() 进行深度复制。

相反，导入 copy 并使用 copy.deepcopy(list)。

现在可以了。