数独有效性检查算法 - 请问这是怎么code的作品？ [英] Sudoku validity check algorithm - how does this code works?

问题描述

我在阅​​读张贴在这里的一个问题：数独算法的C＃

I was reading a question posted here: Sudoku algorithm in C#

和发布的解决方案之一是这片code。

And one of the solutions posted was this piece of code.

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

的想法是，它会检测是否有重复的值的阵列中;但我不知所措多少我不知道。有人可以解释这样对我？

The idea is that it will detect duplicates in the array of values; but I'm overwhelmed by how much I don't know. Can someone explain this to me?

编辑：谢谢大家。因此，许多伟大的答案，我不知道该如何选择。现在是非常合情合理的。

Thanks everyone. So many great answers, I don't know how to select one. It now makes perfect sense.

推荐答案

真是一个不错的主意。

基本上，它使用了一个 INT 标志（初始设置为0）作为位列;每个值，它会检查是否在标志对应的位被置位，如果它不是，它设置它。

Basically, it uses an int flag (initially set to zero) as a "bit array"; for each value, it checks if the corresponding bit in the flag is set, and if it's not, it sets it.

如果相反，该比特位置已被设置时，它知道对应的值已经见到的那样，因此片独的是无效的。

If, instead, that bit position is already set, it knows that the corresponding value has already been seen, so the piece of Sudoku is invalid.

更多细节：

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

这篇关于数独有效性检查算法 - 请问这是怎么code的作品？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！