Foros del Web » Programación para mayores de 30 ;) » C/C++ »

Algoritmo para resolver sudoku incomprensible

Estas en el tema de Algoritmo para resolver sudoku incomprensible en el foro de C/C++ en Foros del Web. 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 ...
  #1 (permalink)  
Antiguo 04/11/2014, 12:21
 
Fecha de Ingreso: noviembre-2014
Mensajes: 36
Antigüedad: 9 años, 8 meses
Puntos: 13
Algoritmo para resolver sudoku incomprensible

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++:
Ver original
  1. int trycell(int *x, int pos)
  2. {
  3.     int row = pos / 9;
  4.     int col = pos % 9;
  5.     int i, j, used = 0;
  6.  
  7.     if (pos == 81)
  8.         return 1;
  9.     if (x[pos])
  10.         return trycell(x, pos + 1);
  11.  
  12.     for (i = 0; i < 9; i++)
  13.         used |= 1 << (x[i * 9 + col] - 1);
  14.  
  15.     for (j = 0; j < 9; j++)
  16.         used |= 1 << (x[row * 9 + j] - 1);
  17.  
  18.     row = row / 3 * 3;
  19.     col = col / 3 * 3;
  20.  
  21.     for (i = row; i < row + 3; i++)
  22.         for (j = col; j < col + 3; j++)
  23.             used |= 1 << (x[i * 9 + j] - 1);
  24.  
  25.     for (x[pos] = 1; x[pos] <= 9; x[pos]++, used >>= 1)
  26.         if (!(used & 1) && trycell(x, pos + 1))
  27.             return 1;
  28.     x[pos] = 0;
  29.     return 0;
  30. }

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

Saludos kutcher
  #2 (permalink)  
Antiguo 05/11/2014, 01:26
 
Fecha de Ingreso: octubre-2014
Ubicación: Madrid
Mensajes: 1.212
Antigüedad: 9 años, 9 meses
Puntos: 204
Respuesta: Algoritmo para resolver sudoku incomprensible

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++:
Ver original
  1. for (i = 0; i < 9; i++)
  2.         used |= 1 << (x[i * 9 + col] - 1);
  3.  
  4.     for (j = 0; j < 9; j++)
  5.         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++:
Ver original
  1. for (i = row; i < row + 3; i++)
  2.         for (j = col; j < col + 3; j++)
  3.             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++:
Ver original
  1. for (x[pos] = 1; x[pos] <= 9; x[pos]++, used >>= 1)
  2.         if (!(used & 1) && trycell(x, pos + 1))
  3.             return 1;
  #3 (permalink)  
Antiguo 06/11/2014, 18:57
 
Fecha de Ingreso: noviembre-2014
Mensajes: 36
Antigüedad: 9 años, 8 meses
Puntos: 13
Respuesta: Algoritmo para resolver sudoku incomprensible

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

Saludos
  #4 (permalink)  
Antiguo 07/11/2014, 00:59
 
Fecha de Ingreso: octubre-2014
Ubicación: Madrid
Mensajes: 1.212
Antigüedad: 9 años, 9 meses
Puntos: 204
Respuesta: Algoritmo para resolver sudoku incomprensible

operador or exclusivo??
  #5 (permalink)  
Antiguo 07/11/2014, 08:32
 
Fecha de Ingreso: noviembre-2014
Mensajes: 36
Antigüedad: 9 años, 8 meses
Puntos: 13
Respuesta: Algoritmo para resolver sudoku incomprensible

Cita:
Iniciado por eferion Ver Mensaje
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.
  #6 (permalink)  
Antiguo 07/11/2014, 13:34
 
Fecha de Ingreso: octubre-2014
Ubicación: Madrid
Mensajes: 1.212
Antigüedad: 9 años, 9 meses
Puntos: 204
Respuesta: Algoritmo para resolver sudoku incomprensible

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++:
Ver original
  1. int x = 10; // en binario: 0000 0000 0000 1010
  2. x |= 18;    // 20 en binario: 0000 0000 0001 0010
  3. std::cout << x; // imprime 26, es decir 0000 0000 0001 1010
  #7 (permalink)  
Antiguo 23/01/2015, 05:38
 
Fecha de Ingreso: enero-2015
Mensajes: 1
Antigüedad: 9 años, 5 meses
Puntos: 0
Respuesta: Algoritmo para resolver sudoku incomprensible

Cita:
Iniciado por eferion Ver Mensaje
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.
  #8 (permalink)  
Antiguo 26/01/2015, 09:09
 
Fecha de Ingreso: octubre-2014
Ubicación: Madrid
Mensajes: 1.212
Antigüedad: 9 años, 9 meses
Puntos: 204
Respuesta: Algoritmo para resolver sudoku incomprensible

Cita:
Iniciado por baqpqfyq Ver Mensaje
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.

Etiquetas: funcion, int, resolver, sudoku
Atención: Estás leyendo un tema que no tiene actividad desde hace más de 6 MESES, te recomendamos abrir un Nuevo tema en lugar de responder al actual.
Respuesta




La zona horaria es GMT -6. Ahora son las 07:32.