在 while 循环期间字典值未正确更新

Question

我目前正在尝试为数独求解器编写时间回溯算法。我有几个位置存储为FlexiblePositions，它在数组中表示为两个整数。每个值都存储在一个字典中，其中包含从 1 到 9 的数字列表。

该算法获取位置，将其填充到字典中并获取可能的数字列表（域）。他应该获取一个数字，使用 Checker 布尔方法检查它，然后将其删除。如果域为空，他会移至之前的位置。

然而，当他获取域时，他并没有从字典中获取域，而是在算法的整个运行过程中仅使用一个列表。

我不知道如何使循环获取我请求的域。

int[,] ChronologicalBacktracking(int[,] s, List<int[]>FlexPositions)
{
    var domains = new Dictionary<int[], List<int>>();
    int[,] sudoku = (int[,])s.Clone();
    List<int> options = new List<int> { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    foreach (var i in FlexPositions)
    {
        domains.Add(i, options);
    }
    int pointer = 0;
    while(pointer<FlexPositions.Count())
    {
        int[] pos = FlexPositions[pointer];
        if (domains[pos].Count == 0)
        { 

这里的代码应该填写之前的 pos 列表，然后移动到前一个，但是他对于上面的 if 检查仍然使用相同的域列表。

            domains[pos] = new List<int> { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
            pointer--;
            if (pointer>=0)
            {
                int[] prev = FlexPositions[pointer];
                sudoku[prev[0],prev[1]] = 0;
            }
        }
        else
        {

PrintList2 打印列表中所有数字的列表，尽管 pos 已更改，但每次迭代都会减少一个数字。

            pos = FlexPositions[pointer];
            PrintList2(domains[pos]);
            int number = domains[pos][domains[pos].Count-1];
            Console.WriteLine(pos[0] + "" + pos[1] + " " + number);
            //PrintSudoku(sudoku);

            if (Checker(sudoku, pos, number))
            {
                Console.WriteLine(pointer);
                sudoku[pos[0], pos[1]] = number;
                domains[pos].RemoveAt(domains[pos].Count-1);
                pointer++;

                if (pointer == FlexPositions.Count())
                {
                    return (sudoku);

                }
            }
            else
            {
                domains[pos].RemoveAt(domains[pos].Count-1);
            }


        }
        
    }
    return (sudoku);
}

我过去在参考文献方面也遇到过类似的问题，所以我认为就是这样。但是我对 C# 的经验不足以解决这个问题。 另外，我知道这段代码接缝是最佳的，或者可能有其他问题，因为一旦我让它工作，我仍然需要对其进行改进，但是我无法解决我的字典列表未正确更新的问题。

如有任何帮助，我们将不胜感激。

Answer 1

您在 C# 中使用数独求解器遇到的问题似乎与您处理

domains

字典和

FlexPositions

的方式有关。在 C# 中，当您使用数组 (

int[]

) 作为字典中的键时，字典对键使用引用相等，而不是值相等。这意味着即使两个数组包含相同的整数，如果它们是内存中的不同对象，它们也会被视为不同的键。

在您的情况下，每次您为某个位置创建

int[]

时，即使它与前一个位置具有相同的内容，它也会被视为不同的键。因此，当您更新一个职位的域名时，它不会更新技术上应该相同的其他职位。

要解决此问题，您需要对位置使用正确处理基于值的相等性的数据结构，或者需要更仔细地管理数组引用。一种常见的方法是对位置使用自定义类或结构，重写相等方法以确保具有相同值的两个位置被视为相等。这是使用结构的快速实现：

public struct Position
{
    public int X;
    public int Y;

    public Position(int x, int y)
    {
        X = x;
        Y = y;
    }

    public override bool Equals(object obj)
    {
        if (obj is Position other)
        {
            return X == other.X && Y == other.Y;
        }
        return false;
    }

    public override int GetHashCode()
    {
        return HashCode.Combine(X, Y);
    }
}

// Usage in your method
Dictionary<Position, List<int>> domains = new Dictionary<Position, List<int>>();

// Convert FlexPositions to Position structs
List<Position> positions = FlexPositions.Select(p => new Position(p[0], p[1])).ToList();

foreach (var position in positions)
{
    domains[position] = new List<int> { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
}

// Rest of your code...

在此实现中，我们定义了一个具有

Position

和

X

属性的

Y

结构体，并重写

Equals

和

GetHashCode

方法，以确保两个

Position

实例在具有相同的 ` 时被视为相等。

X

and

Y

values. This way, when you use a

Position

instance as a key in your dictionary, the dictionary will correctly identify different instances of

Position` 与相同的键具有相同的值。

您还需要将

FlexPositions

从

List<int[]>

转换为

List<Position>

，如示例所示。此转换可确保您的代码的其余部分可以使用这个新的

Position

结构。

请记住更新其余代码以使用

Position

结构而不是

int[]

来表示位置。这包括更新

Checker

方法以及处理仓位的代码的任何其他部分。

此外，请考虑递减

pointer

时的逻辑。确保您有适当的边界检查以避免访问列表中的负索引。

此更改应该可以解决字典未正确更新的问题，因为现在字典将根据其值而不是内存中的引用正确识别位置。