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

Я читал вопрос, размещенный здесь: алгоритм Судоку в 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; } 

Идея состоит в том, что он обнаружит дубликаты в массиве значений; но я ошеломлен тем, насколько я не знаю. Может кто-то объяснить это мне?

EDIT: Спасибо всем. Столько замечательных ответов, я не знаю, как их выбрать. Теперь это имеет смысл.

    Действительно хорошая идея.

    В принципе, он использует флаг 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 – значение ячейки. Так как значения sudoku варьируются от 1 до 9, все биты соответствуют диапазону 0-512. С каждым значением проверьте, установлен ли nth бит, и если да, мы нашли дубликат. Если нет, установите nth бит на наш номер чека, в этом случае flag , чтобы скопировать числа, которые уже были использованы. Это гораздо более быстрый способ хранения данных, чем массив.

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

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

    Он также проверяет каждый номер, если этот бит уже установлен во флаг-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