Llop Site Home > Visual Studio .NET > Sudoku
Este es un proyecto que hice el entre 2005 y 2006, especialmente interesante porque combina Java con .NET. La interfaz gráfica está en VisualBasic.NET, mientras que la lógica interna se gestiona con Java.
Y es que Visual Studio (ahora el 2005) es una herramienta superpotente. En resumidas cuentas, lo que hace es crear unas DLLs con las clases Java, para que luego VisualBasic.NET (o cualquiera de los lenguajes soportados por la plataforma) pueda tirar de ellas.
Lo mejor del proyecto es, sin duda alguna, el algoritmo utilizado para resolver y montar sudokus. Basado en una observación de Hitotumatu y Noshita, en 1979, sobre las listas doblemente enlazadas, Donald Knuth popularizó el algoritmo, y lo llamó 'DLX' o 'dancing links' (enlaces en danza) por cómo los nodos de la lista interpretan un baile exquisítamente coreografiado.
Resolver un sudoku es un problema 'NP-Completo' -es decir, no existe un 'camino más corto' que funcione en todos los casos. Por eso, muchos lo han intentado resolver programáticamente con fuerza bruta, de la siguiente forma:
1 - Busca una casilla vacía en el sudoku.
2 - Rellénala con un número, por ejemplo, 1.
3 - Comprueba si el sudoku tiene sentido (no hay números repetidos en la misma fila, etc...).
4 - Si el sudoku es válido, vuelve a ejecutar las instrucciones a partir de la 1.
5 - Si no es válido, ejecuta las instrucciones a partir de la 2, pero cambia el valor de la casilla.
La idea es ir probando todos los valores posibles (normalmente de 1 a 9) hasta dar con uno bueno.
6 - Si ningún valor da un sudoku válido, vacía la casilla, y ejecuta los pasos a partir del 2, pero con la casilla anterior.
Ten en cuenta que el valor que antes se ha dado por bueno no lo es, así que sólo hay que probar con los valores restantes.
7 - Al final, después de cantidad de comprobaciones redundantes, vueltas p'alante y p'atrás, das con la solución. |
Bastante bestia, ¿no? Por fortuna, Knuth encontró un enfoque inteligentísimo. Se dió cuenta que, al igual que con las N-reinas y los pentominos, el sudoku se puede considerar un 'exact cover problem' (problema de cobertura exacta). Y para resolver este tipo de problemas pensó un algoritmo llamado 'algorithm X'. Consulta su artículo para tener todos los detalles.
Tamaño de la cuadrícula:
Elige el tamaño del sudoku, desde una cuadrícula de 4x4 hasta una de 16x16.
Generación sudoku:
El botón 'Nuevo sudoku' genera automáticamente el puzzle, con el número de pistas especificadas.
Creación sudoku:
Puedes crear tu propio sudoku -pulsa el botón 'Nuevo sudoku vacío' para limpiar la cuadrícula; marca la casilla 'Poniendo pistas' para rellenar la cuadrícula; y desmarca la casilla cuando estés listo para empezar a resolver el problema.
Exportar:
Pulsa el botón para crear un archivo .pdf con el problema en pantalla, que se abrirá automáticamente con el 'Adobe Acrobat'.
Evaluación:
Botón '¿Qué tal voy?' - Comprueba si hay errores en las casillas que has llenado.
Botón 'Añadir pista' - Rellena una casilla vacía.
Botón 'Volver a empezar' - Vuelve a comenzar el sudoku sólo con las pistas iniciales.
Solución:
Pulsa 'Resolver sudoku' para obtener instantáneamente su solución -no importa que haya más de una (aunque eso es que el sudoku está mal hecho).
Descarga Llop_Sudoku v1.0. Se trata de un fichero .zip que contiene los siguientes archivos:
El código fuente está también disponible bajo la licencia GNU GPL. Mencióname si lo utilizas, y menciona a Knuth si implementas su algoritmo.
La implementación de los dancing links para el sudoku está en Java:
La interfaz gráfica de usuario es en .NET:
El código no está comentado ni documentado, así que si tienes alguna duda, siempre puedes enviarme un mail.
¿Comentarios, sugerencias?: llopsite.at.yahoo.es | © 2005-07 Albert Lobo
Última actualización: 24-Feb-2007