c# - 数独有效性检查算法 - 这段代码是如何工作的？

Question

我正在阅读此处发布的问题:Sudoku algorithm in C#

发布的解决方案之一就是这段代码。

public static bool IsValid(int[] values) {
        int flag = 0;
        foreach (int value in values) {
                if (value != 0) {
                        int bit = 1 << value;
                        if ((flag & bit) != 0) return false;
                        flag |= bit;
                }
        }
        return true;
}

这个想法是它将检测值数组中的重复项；但我不知所措。谁可以给我解释一下这个？

编辑:谢谢大家。这么多好的答案，我不知道如何选择一个。现在它完全有道理。

Answer 1

真是个好主意。

基本上，它使用int 标志(初始设置为零)作为“位数组”；对于每个值，它检查标志中的相应位是否已设置，如果未设置，则设置它。

相反，如果那个位的位置已经设​​置，它就知道相应的值已经被看到了，所以这 block 数独是无效的。

更详细:

public static bool IsValid(int[] values)
{
    // bit field (set to zero => no values processed yet)
    int flag = 0;
    foreach (int value in values)
    {
        // value == 0 => reserved for still not filled cells, not to be processed
        if (value != 0)
        {
            // prepares the bit mask left-shifting 1 of value positions
            int bit = 1 << value; 
            // checks if the bit is already set, and if so the Sudoku is invalid
            if ((flag & bit) != 0)
                return false;
            // otherwise sets the bit ("value seen")
            flag |= bit;
        }
    }
    // if we didn't exit before, there are no problems with the given values
    return true;
}