Un Sudoku estándar contiene 81 celdas, en una cuadrícula de 9x9, y tiene 9 casillas, cada casilla es la intersección de la primera, la del medio o las últimas 3 filas, y la primera, la del medio 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 casilla. 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. [ cita requerida ] Los jugadores e investigadores utilizan una amplia gama de algoritmos informáticos para resolver Sudokus, estudiar sus propiedades y crear nuevos rompecabezas, incluidos Sudokus con simetrías interesantes y otras propiedades.
Hay varios algoritmos informáticos que resuelven rompecabezas de 9×9 ( n = 9) en fracciones de segundo, pero la explosión combinatoria ocurre a medida que n aumenta, lo que crea límites a las propiedades de los Sudokus que se pueden construir, analizar y resolver a medida que n aumenta.
Algunos aficionados han desarrollado programas informáticos que resolverán los sudokus utilizando un algoritmo de retroceso , que es un tipo de búsqueda de fuerza bruta . [2] El retroceso es una búsqueda en profundidad (en contraste con una búsqueda en amplitud ), porque explorará por completo una rama hasta una posible solución antes de pasar a otra rama. Aunque se ha establecido que existen aproximadamente 5,96 x 10 26 cuadrículas finales, un algoritmo de fuerza bruta puede ser un método práctico para resolver los sudokus.
Un algoritmo de fuerza bruta visita las celdas vacías en algún orden, completando dígitos secuencialmente o retrocediendo cuando se descubre que el número no es válido. [3] [4] [5] [6] Brevemente, un programa resolvería un rompecabezas 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 casilla), entonces el algoritmo avanza a la siguiente celda y coloca un "1" en esa celda. Al verificar las violaciones, si se descubre que el "1" no está permitido, el valor avanza a "2". Si se descubre una celda en la que no se permite ninguno de los 9 dígitos, entonces el algoritmo deja esa celda en blanco y retrocede 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 (la 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 no resuelta con una posible solución. Tenga en cuenta que el algoritmo puede descartar todos los valores probados anteriormente si descubre que el conjunto existente no cumple con las restricciones del sudoku.
Las ventajas de este método son:
La desventaja de este método es que el tiempo de resolución puede ser lento en comparación con los algoritmos basados en métodos deductivos. Un programador informó que un algoritmo de este tipo puede requerir típicamente tan sólo 15.000 ciclos, o tanto como 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]
Un enfoque diferente que también utiliza el retroceso se basa en el hecho de que en la solución de un sudoku estándar la distribución de cada símbolo individual (valor) debe ser uno de solo 46656 patrones. En la resolución manual de sudokus, esta técnica se conoce como superposición de patrones o uso de plantillas y se limita a completar solo los últimos valores. Se puede cargar o crear una biblioteca con todos los patrones posibles al inicio del programa. Luego, a cada símbolo dado se le asigna un conjunto filtrado con esos patrones, que están de acuerdo con las pistas dadas. En el último paso, la parte del retroceso real, se intenta combinar o superponer los patrones de estos conjuntos de una manera no conflictiva hasta que se llega a la única combinación permitida. La implementación es excepcionalmente fácil cuando se utilizan vectores de bits, porque para todas las pruebas solo se necesitan operaciones lógicas bit a bit, en lugar de iteraciones anidadas en filas y columnas. Se puede lograr una optimización significativa reduciendo aún más los conjuntos de patrones durante el filtrado. Al probar cada patrón cuestionable contra todos los conjuntos reducidos que ya fueron aceptados para los otros símbolos, el número total de patrones que quedan para retroceder se reduce enormemente.
Y como ocurre con todas las técnicas de fuerza bruta para resolver sudokus, el tiempo de ejecución se puede reducir enormemente si primero se aplican algunas de las prácticas de resolución más simples, que pueden completar algunos valores "fáciles".
Se puede construir un sudoku para que funcione contra el retroceso. Suponiendo que el solucionador trabaje de arriba hacia abajo (como en la animación), un rompecabezas con pocas pistas (17), ninguna pista en la fila superior y que tenga una solución "987654321" para la primera fila, funcionaría en contra del algoritmo. Por lo tanto, el programa dedicaría un tiempo significativo a "contar" 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 necesitaba seis horas para llegar a la solución de un sudoku de este tipo (aunque utilizando una computadora de la era de 2008). Un sudoku de este tipo se puede resolver hoy en día en menos de un segundo utilizando una rutina de búsqueda exhaustiva y procesadores más rápidos. [ cita requerida ]
El sudoku se puede resolver utilizando algoritmos estocásticos (basados en el azar). [9] [10] Un ejemplo de este método es:
Luego se encuentra una solución al rompecabezas. Los enfoques para barajar los números incluyen recocido simulado , algoritmo genético y búsqueda tabú . Se sabe que los algoritmos basados en estocásticos son rápidos, aunque quizás no tanto como las técnicas deductivas. Sin embargo, a diferencia de estas últimas, los algoritmos de optimización no necesariamente requieren que los problemas sean solucionables lógicamente, 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 entera . Estos enfoques se acercan a una solución rápidamente y luego pueden usar ramificaciones hacia el final. El algoritmo simplex puede resolver Sudokus adecuados, indicando si el Sudoku no es válido (sin solución). Si hay más de una solución (Sudokus no adecuados), el algoritmo simplex generalmente producirá una solución con cantidades fraccionarias de más de un dígito en algunos cuadrados. Sin embargo, para resolver correctamente los sudokus, las técnicas de presolución de programación lineal por sí solas deducirán la solución sin necesidad de iteraciones símplex. Las reglas lógicas que se utilizan con las técnicas de presolución para la reducción de problemas de programación lineal incluyen el conjunto de reglas lógicas que utilizan los humanos para resolver sudokus.
Un sudoku también puede modelarse como un problema de satisfacción de restricciones . En su artículo Sudoku as a Constraint Problem [12] , Helmut Simonis describe muchos algoritmos de razonamiento basados en restricciones que pueden aplicarse 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 - del orden de unos pocos milisegundos [15] - y la capacidad de resolver todos los sudokus. [4]
Los sudokus pueden describirse como un problema de cobertura exacta o, más precisamente, un problema de conjunto de golpes exactos . Esto permite una descripción elegante del problema y una solución eficiente. Modelar el sudoku como un problema de cobertura exacta y utilizar un algoritmo como el Algoritmo X de Knuth y su técnica Dancing Links "es el método de elección para encontrar rápidamente [medido en microsegundos] todas las posibles soluciones a los sudokus". [16] Un enfoque alternativo es el uso de la eliminación de Gauss en combinación con golpes de columna y fila.
Sea Q la matriz de sudoku de 9x9, N = {1, 2, 3, 4, 5, 6, 7, 8, 9}, y X representa una fila, columna o bloque genérico. N proporciona símbolos para rellenar Q así como el conjunto de índices para los 9 elementos de cualquier X . Los elementos dados q en Q representan una relación univalente de Q a N . La solución R es una relación total y por lo tanto una función . Las reglas del sudoku requieren que la restricción de R a X sea una biyección , por lo que cualquier solución parcial C , restringida a una X , es una permutación parcial de N .
Sea T = { X : X es una fila, columna o bloque de Q }, por lo que T tiene 27 elementos. Un arreglo es una permutación parcial o una permutación en N . Sea Z el conjunto de todos los arreglos en N . Una solución parcial C puede reformularse para incluir las reglas como una composición de relaciones A (uno a tres) y B que requieren arreglos compatibles:
Solución del rompecabezas, sugerencias para que entren nuevos q en Q , provienen de arreglos prohibidos , el complemento de C en Q x Z : herramientas útiles en el cálculo de relaciones son los residuos :
Documento presentado en la Undécima Conferencia Internacional sobre Principios y Prácticas de Programación con Restricciones.
