当前位置: 动力学知识库 > 问答 > 编程问答 >

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

问题描述:

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;

}

网友答案:

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.

分享给朋友:
您可能感兴趣的文章:
随机阅读: