Si encuentras algún fallo con tu código o proyecto, recuerda probar siempre en un entorno de testing antes subir el código al trabajo final.
Solución:
El algoritmo rápido para resolver sudoku es Algorithm X de Donald Knuth. Usted representa la resolución de sudoku como un problema de cobertura exacto y luego usa el Algoritmo X para resolver el problema de EC. Luego use DLX como implementación eficiente del Algoritmo X.
Hay una gran explicación en wikipedia sobre cómo aplicar la cobertura exacta para resolver sudoku.
Puedo decirte que DLX es extremadamente rápido para resolver sudokus y se usa comúnmente en el algoritmo más rápido.
http://www.setbb.com/phpbb/index.php?mforum=sudoku es un gran foro con probablemente los mejores programadores de sudoku.
Entre llenar los cuadrados con una sola opción y volverse completamente recursivo en el tablero, hay acciones más avanzadas que puedes hacer. Supongamos que “región” es una fila, una columna o una región cuadrada (3×3 o 4×4).
Táctica 1
Si hay K cuadrados en una región que solo pueden tomar K números idénticos (por ejemplo, dos cuadrados que solo pueden tomar 2 y 5, o tres cuadrados que solo pueden tomar 1, 7 y 8), entonces todos los demás cuadrados en esa región no pueden. No tome esos números específicos. Debe iterar cada región para eliminar los números “tomados”, de modo que pueda encontrar un cuadrado con solo una opción lógica (por ejemplo, el tercer cuadrado con 2, 4 y 5 lógicamente puede tomar solo 4, o el cuarto cuadrado con 1, 3, 7 y 8 lógicamente solo pueden tomar 3).
Esto tiene que resolverse con iteración si considera el siguiente ejemplo. Una región tiene cuadrados con estos posibles números:
R: 1 2 3
segundo: 2 3
do: 2 3 4 5
re: 4 5
E: 4 5
El algoritmo debe detectar que los cuadrados D y E contienen los números 4 y 5, por lo que 4 y 5 se excluyen de otros cuadrados de la región. Luego, el algoritmo detecta que los cuadrados B y C contienen los números 2 y 3, por lo que los excluye de otros cuadrados. Esto deja el cuadrado A con solo el número 1.
Táctica 2
Si un número aparece en la región en un solo cuadrado, lógicamente ese cuadrado contiene ese número.
Táctica 3
Las Tácticas 1 y 2 son solo casos especiales de la Táctica 3 que tienen K cuadrados con solo K números idénticos. Puede tener K cuadrados y un conjunto de K números y esos K cuadrados pueden contener cualquier subconjunto de esos K números. Considere el siguiente ejemplo de una región:
R: 1 2
segundo: 2 3
do: 1 3
D: 1 2 3 4
Los cuadrados A, B y C solo pueden contener los números 1, 2 y 3. Eso es K por K. Eso significa que ningún otro cuadrado puede contener lógicamente estos números, lo que deja al cuadrado D con solo el número 4.
La Táctica 2 es un caso especial de la Táctica 3 cuando K = N – 1.
táctica 4
Aproveche la superposición de regiones. Supongamos que algún número puede existir solo en ciertos cuadrados de la región. Si todos esos cuadrados pertenecen a otra región superpuesta, ese número debe excluirse de todos los demás cuadrados en esta otra región.
táctica 5
Caché de resultados. Todas las regiones deben tener un indicador “sucio” que indica que algo en la región ha cambiado desde la última vez que se procesó la región. No es necesario que procese la región con este indicador no establecido.
Los seres humanos usan todas esas tácticas y realmente odian adivinar un número, porque retroceder es un verdadero dolor. En realidad, la dificultad de un tablero se mide con el número mínimo de intentos que se deben hacer para resolver el tablero. Para la mayoría de los tableros “extremos”, una buena suposición es suficiente.
Comentarios y calificaciones
Al final de la artículo puedes encontrar las interpretaciones de otros gestores de proyectos, tú igualmente tienes el poder insertar el tuyo si lo deseas.