回溯算法解谜题时重复走相同路径的问题排查

• 全局候选列表被递归覆盖：你的possibleTracks是类级别的全局变量，每次进入新一层递归调用tryFirstTrack时，都会执行possibleTracks = new List<>()清空并重建列表，上层递归未遍历完的候选项直接丢失，回到上层时无剩余路径可走，自然会重复之前的路径。
• 候选解共用同一个对象引用：你在生成possibleTracks元素时，直接把当前ps对象反复加入列表，没有做拷贝。所有列表元素指向同一个对象实例，后续修改ps的坐标、轨道类型等属性时，列表中所有候选解的属性会同步被修改，等于你存的所有候选项都是同一个状态，每次取到的都是相同路径。
• 缺少回溯状态回滚逻辑：递归调用返回上层时，你没有把当前层修改的ps属性（坐标、轨道值）、网格绘制状态恢复到递归前的状态，下一个候选项遍历使用的是被上一条路径污染的脏状态，逻辑必然出错。

核心修改思路为：每一层递归的候选列表独立维护，每个候选解单独拷贝状态，递归返回后回滚当前层所有修改。

1. 首先给PotentialSolution类添加Clone方法，实现深拷贝，确保新对象的所有属性（h、w、nextSide、单元格状态等）和原对象一致且互不影响。
2. 替换全局候选列表逻辑，改为每层递归生成独立的候选列表：

// 直接返回当前节点的所有合法候选解，不再使用全局列表
private List<PotentialSolution> getValidTracks(PotentialSolution currentPs)
{
    List<PotentialSolution> validTracks = new List<PotentialSolution>();
    for (Track trytrack = Track.Empty + 1; trytrack < Track.MaxVal; trytrack++)
    {
        if (validMove(currentPs.nextSide, trytrack))
        {
            // 深拷贝当前状态，不修改原对象
            PotentialSolution newPs = currentPs.Clone();
            newPs.SetCell(trytrack);
            validTracks.Add(newPs);
        }
    }
    return validTracks;
}

3. 修改回溯主逻辑，增加状态回滚步骤：

private bool backtrackTracks(PotentialSolution ps)
{
    if (canExit)
    {
        return true;
    }
    if (checkOccupiedCells(ps))
    {
        // 每层递归生成独立的候选列表，不会被下层递归覆盖
        List<PotentialSolution> possibleTracks = getValidTracks(ps);
        foreach (PotentialSolution candidate in possibleTracks)
        {
            // 记录当前格子原始值，用于回溯回滚
            var originalTrack = testCells[candidate.h, candidate.w].TrackValue;
            testCells[candidate.h, candidate.w].DrawTrack(g, candidate.GetCell());
            
            // 检查是否找到出口
            if (candidate.TestForExit(endColumn, ref canExit) != Track.MaxVal)
            {
                drawRowColTotals(candidate);
                return true;
            }
            
            // 计算下一个坐标
            int nextH = candidate.h, nextW = candidate.w;
            Track nextSide = findNextSide(candidate.nextSide, candidate.GetCell(), ref nextH, ref nextW);
            candidate.nextSide = nextSide;
            candidate.h = nextH;
            candidate.w = nextW;
            
            // 递归进入下一层
            if (nextH >= 0 && nextH < cellsPerSide && nextW >= 0 && nextW < cellsPerSide)
            {
                if (backtrackTracks(candidate))
                {
                    return true;
                }
            }
            
            // 回溯回滚：恢复当前层的网格状态
            testCells[candidate.h, candidate.w].DrawTrack(g, originalTrack);
        }
        // 所有候选遍历完无合法解，返回false
        return false;
    }
    return false;
}

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