在递归调用中更改列表，同时将列表的克隆作为参数传递 (C#)

Question

我正在创建一种算法来使用约束传播和局部搜索（类似于 Norvig 的）来解决数独问题。为此，我跟踪数独中每个方块的可能值列表。对于每次尝试为正方形分配新值的尝试，我都会克隆数组并将其递归地传递给算法的搜索方法。然而，不知何故这个列表仍在被改变。它涉及的方法是：

List<int>[,] search(List<int>[,] vals)
{
    if (vals == null)
        return null;
    if (isSolved(vals))
        return vals;
    //get square with lowest amt of possible values
    int min = Int32.MaxValue;
    Point minP = new Point();
    for (int y = 0; y < n * n; y++)
    {
        for (int x = 0; x < n * n; x++)
        {
            if (vals[y, x].Count < min && vals[y, x].Count > 1)
            {
                min = vals[y, x].Count;
                minP = new Point(x, y);
            }
        }
    }
    for(int i=vals[minP.Y, minP.X].Count-1; i >= 0; i--)
    {
        //<Here> The list vals[minP.Y, minP.X] is altered within this for loop somehow, even though the only thing done with it is it being cloned and passed to the assign method for another (altered) search afterwards
        Console.WriteLine(vals[minP.Y, minP.X].Count + "-" + min);
        int v = vals[minP.Y, minP.X][i];
        List<int>[,] newVals = (List<int>[,])vals.Clone();
        List<int>[,] l = search(assign(minP, v, newVals));
        if (l != null)
            return l;
    }
    return null;
}

列表 vals[minP.Y, minP.X] 在 for 循环中以某种方式被改变，导致它最终尝试将正方形传递给具有 1（或最终甚至为 0）的 assign 方法可能的值。 Console.Writeline 语句显示 vals[minP.Y, minP.X].Count 最终将不同于 'min' 变量（在 for 循环上面定义相同）。

如果有人可以帮助我了解如何在此 for 循环中更改列表以及如何修复它，我们将不胜感激！

此致。

编辑：编辑这些列表的方法（但是在克隆版本中）：

List<int>[,] assign(Point p, int v, List<int>[,] vals)
{
    int y = p.Y, x = p.X;
    for (int i = vals[y, x].Count - 1; i >= 0; i--)
    {
        int v_ = vals[y, x][i];
        if (v_ != v && !eliminate(p, v_, vals))
            return null;
    }
    return vals;
}

bool eliminate(Point p, int v, List<int>[,] vals)
{
    if (!vals[p.Y, p.X].Remove(v))
        return true; //al ge-elimineerd

    // Update peers when only 1 possible value left
    if (vals[p.Y, p.X].Count == 1)
        foreach (Point peer in peers[p.Y, p.X])
            if(!eliminate(peer, vals[p.Y, p.X][0], vals))
                return false;
    else if (vals[p.Y, p.X].Count == 0)
        return false;

    // Update units
    List<Point> vplaces = new List<Point>();
    foreach (Point unit in units[p.Y, p.X])
    {
        if (vals[unit.Y, unit.X].Contains(v))
        {
            vplaces.Add(unit);
            if (vplaces.Count > 1)
                continue;
        }
    }

    if (vplaces.Count == 0)
        return false;
    else if (vplaces.Count == 1)
    {
        Console.WriteLine("test");
        if (assign(vplaces[0], v, vals) == null)
            return false;
    }

    return true;
}

Answer 1

你的问题在于

List<int>[,] newVals = (List<int>[,])vals.Clone();

Array.Clone() 并没有按照您认为的那样进行。 List<int>[,] 表示 List<int> 个对象的二维数组 - 实际上是一个三维数组。由于 List<int> 不是基本值类型，.Clone() 创建数组的 浅拷贝 。

换句话说，它创建了一个全新的二维数组，其中每个值都有一个指向与旧数组相同的 List<int> 的指针。如果 C# 让您直接操作指针，您可以开始更改它们，但由于它不允许，任何时候您访问底层 List<int>，无论它是否在 [=18= 之前，您都会得到相同的指针] 或之后。

查看文档here, and some solutions are here and here。

实际上，您需要重写该行，而不是复制数组本身，而是将所有值复制到新的 List<int> 中。

在递归调用中更改列表，同时将列表的克隆作为参数传递 (C#)

List being altered in recursive calls while passing clones of the list as argument (C#)

c#

recursion

search

constraints

sudoku