Алгоритм проверки действительности судоку - как работает этот код?

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, что означает, что мы нашли двойное значение, и возвращаем false = 1054 *

Answer 3

Идея состоит в том, чтобы установить nth бит числа, где n - это значение ячейки.Поскольку значения судоку находятся в диапазоне от 1 до 9, все биты укладываются в диапазон от 0 до 512.С каждым значением проверяйте, установлен ли бит nth, и если да, то мы нашли дубликат.Если нет, установите бит nth на нашем контрольном номере, в данном случае flag, чтобы накапливать числа, которые уже были использованы.Это гораздо более быстрый способ хранения данных, чем массив.

Answer 4

Проверяет, являются ли значения в массиве уникальными.Для этого он создает целое число - флаг - и устанавливает биты во флаге в соответствии со значениями в массиве значений.Он проверяет, установлен ли конкретный бит;если это так, то есть дубликат, и он терпит неудачу.В противном случае он устанавливает бит.

Вот разбивка:

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

Answer 5

Интересно. Он хранит числа, которые он уже нашел, установив этот бит в флаг-целое число. Пример:

• Найдено 4
• Смещение числа 1 на 4 бита, в результате чего получается битовый массив 00010000b
• Или в flag-int (который ранее был 0) приводит к тому, что flag-int будет 00010000b
• Найдено 2
• Смещение числа 1 на 2 бита, в результате чего получается битовый массив 00000100b
• Или это в flag-int (который ранее был 00010000b) приводит к тому, что flag-int становится 00010100b

Он также проверяет для каждого номера, установлен ли этот бит в flag-int.

Answer 6

 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