Algoritmo de verificación de validez de sudoku: ¿cómo funciona este código?

Question

Estaba leyendo una pregunta publicada aquí: Sudoku algorithm in C#

Y una de las soluciones publicadas fue esta pieza de código.

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

La idea es que detectará duplicados en la matriz de valores; pero estoy abrumado por lo mucho que no sé. ¿Alguien me puede explicar esto?

EDIT: Gracias a todos. Tantas respuestas excelentes, no sé cómo seleccionar una. Ahora tiene perfecto sentido.

Answer 1

Realmente una buena idea.

Básicamente, utiliza un indicador int (inicialmente configurado en cero) como una "matriz de bits"; para cada valor, comprueba si se establece el bit correspondiente en el indicador, y si no lo está, lo establece.

Si, en cambio, esa posición de bit ya está configurada, sabe que el valor correspondiente ya se ha visto, por lo que la pieza de Sudoku no es válida.

Más en detalle:

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

La idea es establecer el bit nth de un número, donde n es el valor de la celda. Como los valores de sudoku van del 1 al 9, todos los bits se ajustan dentro de un rango de 0 a 512. Con cada valor, verifique si el bit nth ya está configurado, y de ser así, hemos encontrado un duplicado. De lo contrario, configure el bit nth en nuestro número de cheque, en este caso flag, para acumular los números que ya se han utilizado. Es una forma mucho más rápida de almacenar datos que una matriz.

Answer 3

Interesante. Almacena los números que ya encontró al establecer ese bit en el entero de la bandera. Ejemplo:

• Se encontró una Shift 4
• entonces número 1 por 4 bits resultantes en el bit-array 00010000b
• O en la bandera-int (que era previamente 0) resultados en el FLAG- int ser 00010000b
• se encontró una Shift 2
• entonces número 1 por 2 bits resultantes en el bit-array 00000100b
• O en la bandera-int (que fue previamente 00010000b) da como resultado el ser flag-int 00010100b

También prueba para cada número si ese bit ya está configurado en flag-int.

Answer 4

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 

Answer 5

Comprueba si los valores en la matriz son únicos. Para hacer esto, crea un entero - bandera - y establece bits en el indicador según los valores en la matriz de valores. Comprueba si un bit en particular ya está configurado; si es así, entonces hay un duplicado y falla. De lo contrario, establece el bit.

He aquí un desglose:

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 6

permite trabajar a través de él. values = 1,2,3,2,5

iteración 1:

bit = 1 << 1bit = 10

if(00 & 10 != 00)false

flag |= bitflag = 10

iteración 2:

bit = 1 << 2bit = 100

if(010 & 100 != 000)false

flag |= bitflag = 110

iteración 3:

bit = 1 << 3bit = 1000

if(0110 & 1000 != 0000)false

flag |= bitflag = 1110

iteración 4:

bit = 1 << 2bit = 100

if(1110 & 0100 != 0000)TRUE Esto da como resultado true, lo que significa que encontramos un doble, y volver falsa