Un Sudoku estándar contiene 81 celdas, en una cuadrícula de 9 × 9, y tiene 9 casillas, cada casilla es la intersección de la primera, media o las últimas 3 filas, y la primera, media o las últimas 3 columnas. Cada celda puede contener un número del uno al nueve, y cada número solo puede aparecer una vez en cada fila, columna y cuadro. Un Sudoku comienza con algunas celdas que contienen números ( pistas ) y el objetivo es resolver las celdas restantes. Los sudokus adecuados tienen una solución. Los jugadores e investigadores utilizan una amplia gama de algoritmos informáticos para resolver Sudokus, estudiar sus propiedades y crear nuevos acertijos, incluidos Sudokus con interesantes simetrías y otras propiedades.
Hay varios algoritmos de computadora que resolverán acertijos de 9 × 9 ( n = 9) en fracciones de segundo, pero la explosión combinatoria ocurre cuando n aumenta, creando límites a las propiedades de los Sudokus que se pueden construir, analizar y resolver a medida que n aumenta. .
Técnicas
Retroceso
Algunos aficionados han desarrollado programas de computadora que resolverán acertijos de Sudoku utilizando un algoritmo de retroceso , que es un tipo de búsqueda de fuerza bruta . [2] El retroceso es una búsqueda en profundidad primero (en contraste con una búsqueda en amplitud ), porque explorará completamente una rama hacia una posible solución antes de pasar a otra rama. Aunque se ha establecido que existen aproximadamente 5.96 x 11 26 cuadrículas finales, un algoritmo de fuerza bruta puede ser un método práctico para resolver acertijos de Sudoku.
Un algoritmo de fuerza bruta visita las celdas vacías en algún orden, completando los dígitos secuencialmente o retrocediendo cuando se determina que el número no es válido. [3] [4] [5] [6] Brevemente, un programa resolvería un acertijo colocando el dígito "1" en la primera celda y verificando si se permite que esté allí. Si no hay violaciones (verificando las restricciones de fila, columna y cuadro), el algoritmo avanza a la siguiente celda y coloca un "1" en esa celda. Al verificar las infracciones, si se descubre que el "1" no está permitido, el valor se avanza a "2". Si se descubre una celda en la que no se permite ninguno de los 9 dígitos, el algoritmo deja esa celda en blanco y vuelve a la celda anterior. El valor en esa celda luego se incrementa en uno. Esto se repite hasta que se descubre el valor permitido en la última celda (81ª).
La animación muestra cómo se resuelve un Sudoku con este método. Las pistas del rompecabezas (números rojos) permanecen fijas mientras el algoritmo prueba cada celda sin resolver con una posible solución. Tenga en cuenta que el algoritmo puede descartar todos los valores previamente probados si encuentra que el conjunto existente no cumple con las restricciones del Sudoku.
Las ventajas de este método son:
- Se garantiza una solución (siempre que el rompecabezas sea válido).
- El tiempo de resolución no guarda relación con el grado de dificultad .
- El algoritmo (y por lo tanto el código del programa) es más simple que otros algoritmos, especialmente en comparación con algoritmos fuertes que aseguran una solución a los acertijos más difíciles.
La desventaja de este método es que el tiempo de resolución puede ser lento en comparación con los algoritmos modelados a partir de métodos deductivos. Un programador informó que tal algoritmo normalmente puede requerir tan solo 15.000 ciclos, o hasta 900.000 ciclos para resolver un Sudoku, siendo cada ciclo el cambio de posición de un "puntero" a medida que se mueve a través de las celdas de un Sudoku. [7] [8]
Se puede construir un Sudoku para evitar el retroceso. Suponiendo que el solucionador funciona de arriba a abajo (como en la animación), un rompecabezas con pocas pistas (17), sin pistas en la fila superior y tiene una solución "987654321" para la primera fila, funcionaría en oposición al algoritmo . Por lo tanto, el programa pasaría un tiempo considerable "contando" hacia arriba antes de llegar a la cuadrícula que satisface el rompecabezas. En un caso, un programador descubrió que un programa de fuerza bruta requería seis horas para llegar a la solución para tal Sudoku (aunque usando una computadora de la era de 2008). Un Sudoku de este tipo se puede resolver hoy en día en menos de 1 segundo utilizando una rutina de búsqueda exhaustiva y procesadores más rápidos. [ cita requerida ]
Métodos estocásticos de búsqueda / optimización
El sudoku se puede resolver utilizando algoritmos estocásticos (basados en el azar). [9] [10] Un ejemplo de este método es:
- Asigne números aleatoriamente a las celdas en blanco de la cuadrícula.
- Calcule el número de errores.
- "Mezcle" los números insertados hasta que el número de errores se reduzca a cero.
Luego se encuentra una solución al rompecabezas. Los enfoques para mezclar los números incluyen el recocido simulado , el algoritmo genético y la búsqueda tabú . Se sabe que los algoritmos basados en estocásticos son rápidos, aunque quizás no tan rápidos como las técnicas deductivas. Sin embargo, a diferencia de este último, los algoritmos de optimización no requieren necesariamente que los problemas tengan solución lógica, lo que les da el potencial de resolver una gama más amplia de problemas. También se sabe que los algoritmos diseñados para colorear gráficos funcionan bien con Sudokus. [11] También es posible expresar un Sudoku como un problema de programación lineal de números enteros . Estos enfoques se acercan a una solución rápidamente y luego pueden usar la ramificación hacia el final. El algoritmo simplex es capaz de resolver Sudokus adecuado, indicando si el Sudoku no es válido (no hay solución). Si hay más de una solución (Sudokus incorrecto), el algoritmo simplex generalmente producirá una solución con cantidades fraccionarias de más de un dígito en algunos cuadrados. Sin embargo, para los Sudokus adecuados, las técnicas de resolución previa de programación lineal por sí solas deducirán la solución sin necesidad de iteraciones simplex. Las reglas lógicas utilizadas por las técnicas de resolución previa para la reducción de problemas LP incluyen el conjunto de reglas lógicas utilizadas por los humanos para resolver Sudokus.
Programación de restricciones
Un Sudoku también puede modelarse como un problema de satisfacción de restricciones . En su artículo El sudoku como problema de restricción , [12] Helmut Simonis describe muchos algoritmos de razonamiento basados en restricciones que se pueden aplicar para modelar y resolver problemas. Algunos solucionadores de restricciones incluyen un método para modelar y resolver Sudokus, y un programa puede requerir menos de 100 líneas de código para resolver un Sudoku simple. [13] [14] Si el código emplea un algoritmo de razonamiento fuerte, la incorporación de retroceso solo es necesaria para los Sudokus más difíciles. Un algoritmo que combine un algoritmo basado en modelos de restricciones con retroceso tendría la ventaja de un tiempo de resolución rápido y la capacidad de resolver todos los sudokus.
Cobertura exacta
Los rompecabezas de Sudoku pueden describirse como un problema de cobertura exacta . Esto permite una descripción elegante del problema y una solución eficiente. Modelar el Sudoku como un problema de cobertura exacto y usar un algoritmo como el Algoritmo X de Knuth normalmente resolverá un Sudoku en unos pocos milisegundos. Un enfoque alternativo es el uso de la eliminación de Gauss en combinación con el marcado de columnas y filas.
Desarrollar (buscar) Sudokus
Los programas de computadora se utilizan a menudo para "buscar" Sudokus con ciertas propiedades, como una pequeña cantidad de pistas o ciertos tipos de simetría . Se han encontrado más de 49,000 Sudokus con 17 pistas, pero descubrir nuevos Sudokus distintos (no transformaciones de Sudokus conocidos existentes) se está volviendo más difícil a medida que los desconocidos se vuelven más raros. [15]
Un método común de búsqueda de Sudokus con una característica particular se llama búsqueda de vecinos . Usando esta estrategia, uno o más Sudokus conocidos que satisfacen o casi satisfacen la característica que se busca se utilizan como punto de partida, y estos Sudokus luego se modifican para buscar otros Sudokus con la propiedad que se busca. La alteración puede ser reubicar una o más posiciones de pistas, o eliminar una pequeña cantidad de pistas y reemplazarlas con una cantidad diferente de pistas. Por ejemplo, de un Sudoku conocido, se puede realizar una búsqueda de uno nuevo con una pista menos eliminando dos pistas y agregando una pista en una nueva ubicación. (Esto se puede llamar una búsqueda {-2, + 1}). Luego, se buscaría exhaustivamente en cada nuevo patrón todas las combinaciones de valores de pista, con la esperanza de que uno o más arroje un Sudoku válido (es decir, que se pueda resolver y tenga una única solución). También se pueden emplear métodos para evitar que los Sudokus esencialmente equivalentes se prueben de forma redundante.
Como ejemplo específico, la búsqueda de un Sudoku de 17 pistas podría comenzar con un Sudoku conocido de 18 pistas y luego alterarlo eliminando tres pistas y reemplazándolas con solo dos pistas , en diferentes posiciones (ver las últimas dos imágenes). Esto puede descubrir nuevos Sudokus, pero no hay garantía inmediata de que sean esencialmente diferentes de los Sudokus ya conocidos. Si busca Sudokus realmente nuevo (no descubierto), se necesitará una confirmación adicional para asegurarse de que cada hallazgo no sea una transformación de un Sudoku ya conocido. [16] [se necesita una mejor fuente ]
Ver también
- Sudoku
- Matemáticas del Sudoku
- § Sudokus con pocas pistas (número mínimo de datos)
- § Sudokus automórficos
- Explosión combinatoria (con resumen del recuento de cuadrículas de Sudoku en comparación con cuadrados latinos)
- Glosario de Sudoku
Referencias
- ^ "Star Burst - Polar Graph" Un gráfico polar que muestra una ruta de solución para un Sudoku (Star Burst) utilizando una rutina de búsqueda exhaustiva y un comentario sobre el Sudoku de 17 pistas.
- ^ http: //intelligence.worldofcomputing/brute-force-search Brute Force Search, 14 de diciembre de 2009.
- ^ "Retroceso - Conjunto 7 (Sudoku)" . GeeksforGeeks . GeeksforGeeks. Archivado desde el original el 28 de agosto de 2016 . Consultado el 24 de diciembre de 2016 .
- ^ Norvig, Peter. "Resolver todos los rompecabezas de Sudoku" . Peter Norvig (sitio web personal) . Consultado el 24 de diciembre de 2016 .
- ^ "Gráfico de celdas visitadas para solución" Un gráfico que muestra una ruta de solución a un Sudoku difícil.
- ^ Zelenski, Julie (16 de julio de 2008). Conferencia 11 | Programación de abstracciones (Stanford) . Departamento de Ciencias de la Computación de Stanford.
- ^ "Star Burst Leo - Polar Graph" Un gráfico polar que muestra una ruta de solución para un Sudoku (Star Burst Leo) utilizando una rutina de búsqueda exhaustiva.
- ^ "Gráfico de celdas visitadas para solución" Un gráfico que muestra una ruta de solución para un Sudoku difícil utilizando una rutina de búsqueda exhaustiva.
- ^ Lewis, R (2007) Metaheuristics puede resolver Sudoku Puzzles Journal of Heuristics, vol. 13 (4), págs. 387-401.
- ^ Pérez, Meir y Marwala, Tshilidzi (2008) Enfoques de optimización estocástica para resolver Sudoku arXiv: 0805.0697.
- ^ Lewis, R. Una guía para colorear gráficos: algoritmos y aplicaciones . Springer International Publishers, 2015.
- ^ Simonis, Helmut (2005). "Sudoku como un problema de restricción". Centro de Computación de Restricciones de Cork en University College Cork: Helmut Simonis. CiteSeerX 10.1.1.88.2964 .
documento presentado en la XI Conferencia Internacional sobre Principios y Práctica de la Programación de Restricciones
Cite journal requiere|journal=
( ayuda ) - ^ Varios autores. "Solucionador de programación de restricciones de Java" (Java) . JaCoP . Krzysztof Kuchcinski y Radoslaw Szymanek . Consultado el 8 de diciembre de 2016 .
- ^ Rhollor. "Sudokusolver" (C ++) . GitHub . Rhollor . Consultado el 8 de diciembre de 2016 .
- ^ Royle, Gordon. "Sudoku mínimo" . Archivado desde el original el 19 de octubre de 2013 . Consultado el 20 de octubre de 2013 .
- ^ http://forum.enjoysudoku.com El foro de nuevos jugadores de Sudoku "No hay 17 nuevos dentro de {-3 + 3}".
enlaces externos
- http://diuf.unifr.ch/pai/people/juillera/Sudoku/Sudoku.html Sudoku Explainer por Nicolas Juillerat (Popular por calificar Sudokus en general)
- http://gsf.cococlyde.org/download/sudoku sudoku de Glenn Fowler (Popular por calificar los Sudokus más difíciles, entre otras cosas)
- Un algoritmo de lápiz y papel para resolver rompecabezas de Sudoku