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

Question

I'm creating an algorithm to solve sudoku's using Constraint Propagations and Local Search ( similar to Norvig's ). For this I keep track of lists of possible values for each of the squares in the sudoku. For each attempt to try to assign a new value to a square I clone the array and pass it to the algorithm's search method recursively. However, somehow this the list is still being altered. The method it concerns is:

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

The list vals[minP.Y, minP.X] is somehow altered within the for loop which causes it to eventually try to pass squares to the assign method that have 1 (or eventually even 0) possible values. The Console.Writeline statement shows that the vals[minP.Y, minP.X].Count will eventually differ from the 'min' variable (which is defined as the same above the for loop).

If anyone could help me out on how the list is altered within this for loop and how to fix it it'd be much appreciated!

Best regards.

EDIT: The methods in which these lists are edited (in a cloned version however):

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

Please provide standalone code sample (see [MCVE] for guidance) - there are variables/methods used in you sample that are not show. — Alexei Levenkov, Jun 27 '16 at 20:37
@AlexeiLevenkov I'll try to updating my question, however the problem should be within the for loop shown as nowhere else the specific list is edited. — user2273652, Jun 27 '16 at 20:41
Note that instead of making sample code smaller you just pasted whole bunch more code... :( — Alexei Levenkov, Jun 27 '16 at 22:37

score 3 · Accepted Answer · edited May 23 '17 at 11:58

Your problem is with

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

Array.Clone() doesn't do what you think it does here. List<int>[,] represents a two-dimensional Array of List<int> objects - effectively a three-dimensional array. Since List<int> isn't a basic value type, .Clone() creates a shallow copy of the array.

In other words, it creates a brand new two-dimensional Array which has, for each value, a pointer to the same List<int> that the old one does. If C# let you manipulate pointers directly, you could start changing those, but since it doesn't, any time you access the underlying List<int>, you're getting the same one regardless of whether it's before the Clone() or after.

See the documentation on it here, and some solutions are here and here.

Effectively, you need to rewrite that line so that rather than copying the array itself, it copies all the values into new List<int>'s.

Ahh I did not know that thank you! I tried creating a seperate deepCopy method which goes through all lists of the array and recreates them like newArray[y, x] = new List(oldArray[y, x]) but somehow this results in a stack overflow exception. Should this work though? EDIT: Nevermind, fixed that problem it works now! Thank you. — user2273652, Jun 27 '16 at 20:57
@user2273652 - Glad that worked for you. It's definitely a non-obvious issue. — Bobson, Jun 27 '16 at 21:25

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

1 Answers1