数独有效性检查算法 – 此代码如何工作?
我正在阅读这里发布的一个问题: 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; }
这个想法是它将检测值数组中的重复项; 但是我不知道有多少我不知所措。 谁可以给我解释一下这个?
编辑:谢谢大家。 这么多很棒的答案,我不知道如何选择一个。 它现在非常有意义。
真是个好主意。
基本上,它使用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; }
让我们通过它。 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
想法是设置数字的nth
位,其中n
是单元格值。 由于数独值的范围为1-9,因此所有位都在0-512的范围内。 使用每个值,检查nth
位是否已设置,如果是,我们发现重复。 如果不是,请在我们的支票号上设置第nth
位,在这种情况下为flag
,以累计已经使用过的数字。 这是一种比数组更快的存储数据的方法。
有趣。 它通过在标志整数中设置该位来存储已找到的数字。 例:
- 它找到了4
- 然后将1号移位4位,得到位arrays00010000b
- 或者它进入flag-int(之前为0)导致flag-int为00010000b
- 它找到了2
- 然后将数字1移位2位,得到位arrays00000100b
- 或者它进入flag-int(以前是00010000b)导致flag-int为00010100b
如果已经在flag-int中设置了该位,它还会测试每个数字。
它会检查数组中的值是否唯一。 为此,它创建一个整数 – 标志 – 并根据值数组中的值设置标志中的位。 它检查是否已设置特定位; 如果是,那么就有重复但它失败了。 否则,它设置位。
这是一个细分:
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. Eg // 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, ie 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. eg 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. }
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