数独有效性检查算法 - 此代码如何工作？

Question

我正在阅读这里发布的一个问题: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标志(最初设置为零)作为"位数组"; 对于每个值,它检查是否设置了标志中的相应位,如果不是,则设置它.

相反,如果已经设置了该位位置,则它知道已经看到相应的值,因此该数据块无效.

更详细:

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

Answer 2

让我们通过它. values = 1,2,3,2,5

迭代1:

bit = 1 << 1 bit = 10

if(00 & 10 != 00) false

flag |= bit flag = 10

迭代2:

bit = 1 << 2 bit = 100

if(010 & 100 != 000) false

flag |= bit flag = 110

迭代3:

bit = 1 << 3 bit = 1000

if(0110 & 1000 != 0000) false

flag |= bit flag = 1110

迭代4:

bit = 1 << 2 bit = 100

if(1110 & 0100 != 0000) TRUE 这个计算结果为true,意味着我们找到了一个double,并返回false