魔方BFS算法提前终止？仅检测到4种排列的问题排查

我实现了广度优先搜索（BFS）算法，用于计算到达带掩码的魔方排列所需的步数，并将结果输出到字典中。测试时使用了仅单个面块（facelet）独特、其余均为默认掩码的魔方，预期能得到该独特面块所有可能位置的步数，但实际仅检测到该面的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")

输出结果 #

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

输出显示独特面块"U"始终停留在U面内。

问题分析与解决 #

核心问题：选中的是魔方中心块 #

魔方的中心块在物理结构上是固定位置的，仅能在所属面内旋转，无法通过任何面旋转操作移动到其他面。你测试用的U0如果是U面的中心块，那自然只会出现U面内的4种旋转位置，这是魔方的物理特性导致的，和代码无关。如果要测试面块跨面移动的情况，应该选择边缘块或角块（比如U1、U3这类非中心的面块）。

深拷贝问题修正 #

你提到的深拷贝怀疑是合理的：Cube的state是三维列表，cube.getState().copy()属于浅拷贝，仅复制了外层列表，内部的子列表仍然是引用，会导致后续修改影响原对象。需要使用copy.deepcopy()来实现真正的深拷贝：

1. 先导入copy模块：import copy
2. 修改BFS中的newCube创建代码：

   newCube = Cube(state=copy.deepcopy(cube.getState()))
   

3. 队列存入时也需要深拷贝：

   queue.put(Cube(state=copy.deepcopy(newCube.getState())))
   

验证建议 #

将测试用的mask改为边缘块，比如mask = ["U1"]，再运行代码，此时BFS应该能搜索到该面块在其他面的位置，得到符合预期的步数结果。

内容的提问来源于stack exchange，提问作者Iby Morris