リストのクローンを引数（C＃）として渡している間に再帰呼び出しでリストが変更される

Question

私は、制約伝播とローカル検索（Norvigと似ています）を使ってsudokuを解くアルゴリズムを作成しています。このために、私はスードクの四角形のそれぞれについて可能な値のリストを追跡します。正方形に新しい値を代入しようとするたびに、配列を複製し、それをアルゴリズムの検索メソッドに再帰的に渡します。しかし、どういうわけか、このリストはまだ変更されています。それが関係する方法がある。

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; 
} 

[minP.Y、minP.X]は何とかそれが最終的に1（又はを有する割り当て方法に正方形を通過しようとさせるforループ内で変更されたリストヴァルス最終的には0も可能な値）。 Console.Writelineステートメントは、vals [minP.Y、minP.X] .Countが最終的に 'min'変数（これはforループの上に同じものとして定義されています）とは異なることを示しています。

誰かがこのforループ内でどのようにリストが変更されているかについて助けてくれたら、それを修正する方法は大変ありがとう！

よろしくお願いいたします。

EDIT：（但しクローン化されたバージョンでは）これらのリストを編集する方法：

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>オブジェクトの2次元配列を表します。事実上、3次元配列です。 List<int>は基本値型ではないため、.Clone()は、の浅いコピーを作成します。

つまり、新しい値の2次元配列を作成します。これは、値ごとに、古いものと同じList<int>へのポインタを持ちます。 C＃でポインタを直接操作できる場合は、ポインタを変更することができますが、それ以来、List<int>にアクセスするときはいつでも、Clone()より前であるかどうかにかかわらず同じものを取得します。

hereのドキュメントを参照してください。いくつかの解決策はhereとhereです。

効果的には、配列自体をコピーするのではなく、の値をすべて新しいList<int>にコピーするように、その行を書き直す必要があります。