数独有效性检查算法--这段代码是如何工作的？
我在这里读到了一个问题：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;
}它的想法是它将检测值数组中的重复项；但我被我所不知道的东西弄得不知所措。有人能给我解释一下吗？
编辑:谢谢大家。答案太多了，我都不知道该怎么选了。现在这就说得通了。
回答 5
Stack Overflow用户
发布于 2011-02-25 06:43:20
真是个好主意。
基本上，它使用一个int标志(最初设置为0)作为“位数组”；对于每个值，它检查标志中的相应位是否已设置，如果没有，则设置它。
相反，如果该位位置已经设置，则它知道已经看到了相应的值，因此该数独块无效。
更多详细信息：
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;
}Stack Overflow用户
发布于 2011-02-25 06:53:54
让我们一起来解决这个问题。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，意味着我们找到了一个双精度值，并返回false
Stack Overflow用户
发布于 2011-02-25 06:43:34
其思想是设置数字的nth位，其中n是单元格值。由于sudoku值的范围是1-9，所以所有的位都在0-512的范围内。对于每个值，检查是否已经设置了nth位，如果已经设置，则我们发现了一个重复的值。如果不是，则在我们的校验号上设置nth位，在本例中为flag，以累加已经使用的数字。这是一种比数组更快的数据存储方式。
https://stackoverflow.com/questions/5111434
复制相似问题