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 valuesint 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 afterwardsConsole.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 leftif (vals[p.Y, p.X].Count == 1)foreach (Point peer in peers[p.Y, p.X])if(!eliminate(peer, vals[p.Y, p.X], vals))return false;else if (vals[p.Y, p.X].Count == 0)return false;// Update unitsList<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, v, vals) == null)return false;}return true;}``

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.

Top