19

我正在阅读此处发布的问题: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;
}

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

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

4

6 回答 6

22

真是个好主意。

基本上,它使用一个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;
}
于 2011-02-24T22:43:19.840 回答
5

让我们通过它。 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这评估为真,这意味着我们找到了一个双精度,并返回假

于 2011-02-24T22:53:54.400 回答
3

这个想法是设置nth一个数字的位,其中n是单元格值。由于数独值的范围是 1-9,因此所有位都在 0-512 的范围内。对于每个值,检查该nth位是否已设置,如果是,我们找到了重复项。如果没有,请设置nth我们的校验号码上的位,在这种情况下flag,以累积已使用的号码。这是一种比数组更快的数据存储方式。

于 2011-02-24T22:43:33.863 回答
2

有趣的。它通过在标志整数中设置该位来存储它已经找到的数字。例子:

  • 它发现了一个 4
  • 然后将数字 1 移动 4 位,得到位数组 00010000b
  • 或者将其放入 flag-int(以前为 0)导致 flag-int 为 00010000b
  • 它发现了一个 2
  • 然后将数字 1 移动 2 位,得到位数组 00000100b
  • 或者它进入 flag-int(以前是 00010000b)导致 flag-int 为 00010100b

如果该位已在 flag-int 中设置,它还会测试每个数字。

于 2011-02-24T22:47:25.927 回答
2

它检查数组中的值是否唯一。为此,它创建一个整数 - 标志 - 并根据值数组中的值设置标志中的位。它检查是否已经设置了特定位;如果是,则存在重复并且失败。否则,它设置该位。

这是一个细分:

public static bool IsValid(int[] values) {
        int flag = 0; // <-- Initialize your flags; all of them are set to 0000
        foreach (int value in values) { // <-- Loop through the values
                if (value != 0) { // <-- Ignore values of 0
                        int bit = 1 << value; // <-- Left-shift 1 by the current value
// Say for example, the current value is 4, this will shift the bit in the value of 1
// 4 places to the left. So if the 1 looks like 000001 internally, after shifting 4 to the 
// left, it will look like 010000; this is how we choose a specific bit to set/inspect
                        if ((flag & bit) != 0) return false; // <-- Compare the bit at the
// position specified by bit with the corresponding position in flag. If both are 1 then
// & will return a value greater than 0; if either is not 1, then & will return 0. E.g.
// if flag = 01000 and bit = 01000, then the result will be 01000. If flag = 01000 and 
//bit = 00010 then the result will be 0; this is how we check to see if the bit 
// is already set. If it is, then we've already seen this value, so return false, i.e. not
// a valid solution
                        flag |= bit; // <-- We haven't seen this value before, so set the 
// corresponding bit in the flag to say we've seen it now. e.g. if flag = 1000 
// and bit = 0100, after this operation, flag = 1100
                }
        }
        return true; // <-- If we get this far, all values were unique, so it's a valid
// answer.
}
于 2011-02-24T22:50:55.360 回答
1
 int bit = 1 << value; //left bit shift - selects the bit that corresponds to value
 if ((flag & bit) != 0) return false; //bitwise AND - checks the flag to see whether bit is already set
 flag |= bit; // bitwise OR - sets the bit in the flag
于 2011-02-24T22:49:30.463 回答