Algoritmo para resolver sudoku incomprensible

[kutcher]

Buenas me he topado con un código un poco complicado de seguir, la cuestión es que se me hace difícil entender como logra aislar el número exacto en la posición requerida sin la necesidad (según veo) de una búsqueda exhaustiva como es común en este tipo de algoritmos, aquí el código :

Código C++:

int trycell(int *x, int pos)
{
    int row = pos / 9;
    int col = pos % 9;
    int i, j, used = 0;
 
    if (pos == 81)
        return 1;
    if (x[pos])
        return trycell(x, pos + 1);
 
    for (i = 0; i < 9; i++)
        used |= 1 << (x[i * 9 + col] - 1);
 
    for (j = 0; j < 9; j++)
        used |= 1 << (x[row * 9 + j] - 1);
 
    row = row / 3 * 3;
    col = col / 3 * 3;
 
    for (i = row; i < row + 3; i++)
        for (j = col; j < col + 3; j++)
            used |= 1 << (x[i * 9 + j] - 1);
 
    for (x[pos] = 1; x[pos] <= 9; x[pos]++, used >>= 1)
        if (!(used & 1) && trycell(x, pos + 1))
            return 1;
    x[pos] = 0;
    return 0;
}
 

Si pudieran aclararme como funciona mas o menos este código

Saludos kutcher

[eferion]

1er paso: comprueba los números que están siendo utilizados en la misma fila (primer bucle) y en la misma columna (segundo bucle)

Código C++:

for (i = 0; i < 9; i++)
        used |= 1 << (x[i * 9 + col] - 1);
 
    for (j = 0; j < 9; j++)
        used |= 1 << (x[row * 9 + j] - 1);
 

"used" sirve para almacenar los elementos existentes. Esto lo consigue usando "used" de forma binaria: "si hay un "1", se pone a 1 el bit 1, si hay un "2", se pone a 1 el bit 2, ...

2º paso: recorre la matriz de 3x3 en la que se ubica el número en cuestión y repite la operación de recolectar los números ya usados:

Código C++:

for (i = row; i < row + 3; i++)
        for (j = col; j < col + 3; j++)
            used |= 1 << (x[i * 9 + j] - 1);
 

3er paso: Para cada número que no ha sido utilizado comprueba "trycell" (que no se que hace) y si el resultado es positivo, entonces ha encontrado una solución:

Código C++:

for (x[pos] = 1; x[pos] <= 9; x[pos]++, used >>= 1)
        if (!(used & 1) && trycell(x, pos + 1))
            return 1;
 

[kutcher]

Perfecto ahora todo queda claro, solo una consulta mas el operador OR inclusivo que función cumple en este caso

Saludos

[eferion]

operador or exclusivo??

[kutcher]

Iniciado por eferion

operador or exclusivo??

Que quieres decir con eso me refiero al operador or inclusivo (|) no al exclusivo (^) este ultimo no tiene ninguna aparición en el código que publique.

[eferion]

Vale, jejeje, lo leí mal.

El operador or que ves es un operador binario. Hace una operación or bit a bit.

Un ejemplo:

Código C++:

int x = 10; // en binario: 0000 0000 0000 1010
x |= 18;    // 20 en binario: 0000 0000 0001 0010
std::cout << x; // imprime 26, es decir 0000 0000 0001 1010
 

[baqpqfyq]

Iniciado por eferion

3er paso: Para cada número que no ha sido utilizado comprueba "trycell" (que no se que hace) y si el resultado es positivo, entonces ha encontrado una solución:

trycell es la propia función que estás destripando. Recursividad.

Saludos.

[eferion]

Iniciado por baqpqfyq

trycell es la propia función que estás destripando. Recursividad.

Saludos.

cierto... mira que revisé el código varias veces pero no me fijé en el nombre de la función.