Algoritmos para resolver Sudoku

Algunos aficionados han desarrollado programas informáticos para resolver puzles de Sudoku mediante un algoritmo de retroceso , un tipo de búsqueda por fuerza bruta . ^{[ 3 ]} El retroceso es una búsqueda en profundidad (a diferencia de la búsqueda en amplitud ), ya que explora completamente una rama hasta encontrar una posible solución antes de pasar a otra. Aunque se ha establecido que existen aproximadamente 5,96 × 10²⁶ cuadrículas ^finales , un algoritmo de fuerza bruta puede ser un método práctico para resolver puzles de Sudoku.

Un algoritmo de fuerza bruta visita las celdas vacías en algún orden, rellenando dígitos secuencialmente o retrocediendo cuando se encuentra que el número no es válido. ^{[ 4 ] [ 5 ] [ 6 ] [ 7 ]} Brevemente, un programa resolvería un rompecabezas colocando el dígito "1" en la primera celda y comprobando si está permitido allí. Si no hay violaciones (verificando las restricciones de fila, columna y caja), entonces el algoritmo avanza a la siguiente celda y coloca un "1" en esa celda. Al comprobar violaciones, si se descubre que el "1" no está permitido, el valor avanza a "2". Si se encuentra una celda donde ninguno de los 9 dígitos está permitido, entonces el algoritmo deja esa celda en blanco y regresa a la celda anterior. El valor en esa celda se incrementa en uno. Esto se repite hasta que se descubre el valor permitido en la última (81.ª) celda.

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. Cabe destacar que el algoritmo puede descartar todos los valores probados previamente si considera que el conjunto existente no cumple con las restricciones del Sudoku.

Las ventajas de este método son:

• Se garantiza una solución (siempre y cuando el rompecabezas sea válido).
• El tiempo de resolución no guarda relación, en su mayor parte, con el grado de dificultad .
• El algoritmo (y por lo tanto el código del programa) es más sencillo que otros algoritmos, especialmente en comparación con algoritmos robustos que garantizan la solución a los rompecabezas 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 basados ​​en métodos deductivos. Un programador informó que un algoritmo de este tipo 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" al moverse por las celdas del Sudoku. ^{[ 8 ] [ 9 ]}

Un enfoque diferente, que también utiliza retroceso, se basa en el hecho de que, en la solución de un sudoku estándar, la distribución de cada símbolo (valor) individual debe ser uno de solo 46656 patrones. En la resolución manual de sudoku, esta técnica se conoce como superposición de patrones o uso de plantillas y se limita a completar únicamente los últimos valores. Al inicio del programa, se puede cargar o crear una biblioteca con todos los patrones posibles. A continuación, a cada símbolo se le asigna un conjunto filtrado con aquellos patrones que coinciden con las pistas proporcionadas. En el último paso, la parte de retroceso propiamente dicha, se intenta combinar o superponer patrones de estos conjuntos de forma no conflictiva hasta encontrar la única combinación permitida. La implementación es excepcionalmente sencilla al usar vectores de bits, ya que para todas las pruebas solo se necesitan operaciones lógicas a nivel de bits, en lugar de iteraciones anidadas a través de filas y columnas. Se puede lograr una optimización significativa reduciendo aún más los conjuntos de patrones durante el filtrado. Al contrastar cada patrón cuestionable con todos los conjuntos reducidos que ya fueron aceptados para los demás símbolos, el número total de patrones que quedan por rastrear se reduce considerablemente.

Y como ocurre con todas las técnicas de fuerza bruta para resolver sudokus, el tiempo de ejecución se puede reducir enormemente aplicando primero algunas de las prácticas de resolución más sencillas, que pueden completar algunos valores "fáciles".

Se puede diseñar un Sudoku para que funcione contra el retroceso. Suponiendo que el programa funcione de arriba hacia abajo (como en la animación), un rompecabezas con pocas pistas (17), sin pistas en la fila superior y con la solución "987654321" para la primera fila, funcionaría en contra del algoritmo. Por lo tanto, el programa invertiría un tiempo considerable en "contar" hacia arriba antes de llegar a la cuadrícula que resuelve el rompecabezas. En un caso, un programador descubrió que un programa de fuerza bruta requería seis horas para encontrar la solución de dicho Sudoku (aunque utilizando una computadora de 2008). Hoy en día, un Sudoku de este tipo se puede resolver en menos de 1 segundo utilizando una rutina de búsqueda exhaustiva y procesadores más rápidos. ^{[ 10 ] p:25}

El Sudoku se puede resolver utilizando algoritmos estocásticos (basados ​​en aleatoriedad). ^{[ 11 ] [ 12 ]} Un ejemplo de este método es:

1. Asigna números al azar a las celdas en blanco de la cuadrícula.
2. Calcula el número de errores.
3. "Mezcla" los números introducidos hasta que el número de errores se reduzca a cero.

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ástica 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 resolubles 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 grafos funcionan bien con Sudokus. ^{[ 13 ]} También es posible expresar un Sudoku como un problema de programación lineal entera . Estos enfoques se acercan rápidamente a una solución y luego pueden usar ramificaciones hacia el final. El algoritmo simplex puede resolver Sudokus propios, indicando si el Sudoku no es válido (sin solución). Si hay más de una solución (Sudokus no propios), 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 un Sudoku, las técnicas de preprocesamiento de programación lineal por sí solas permiten obtener la solución sin necesidad de iteraciones del método simplex. Las reglas lógicas que emplean estas técnicas 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 como problema de restricciones» ^{[ 14 ]} , 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. ^{[ 15 ] [ 16 ]} Si el código emplea un algoritmo de razonamiento robusto, 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 ^{[ 17 ]} — y la capacidad de resolver todos los Sudokus. ^{[ 5 ]}

Los rompecabezas de Sudoku pueden describirse como un problema de cobertura exacta , o más precisamente, un problema de conjunto de colisión exacto. 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 de Enlaces Danzantes "es el método de elección para encontrar rápidamente [en microsegundos] todas las posibles soluciones a los rompecabezas de Sudoku". ^{[ 18 ]} Un enfoque alternativo es el uso de la eliminación de Gauss en combinación con la colisión de columnas y filas.

Sea Q la matriz de Sudoku de 9x9, N = {1, 2, 3, 4, 5, 6, 7, 8, 9}, y X represente una fila, columna o bloque genérico. N proporciona los símbolos para rellenar Q, así como el conjunto de índices para los 9 elementos de cualquier X. Los elementos q dados 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 un 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. Una disposición es una permutación parcial o una permutación en N. Sea Z el conjunto de todas las disposiciones en N. Una solución parcial C puede reformularse para incluir las reglas como una composición de relaciones A (de uno a tres) y B que requieren disposiciones compatibles:

${\displaystyle Q\xrightarrow {A} T\xrightarrow {B} Z\quad {\text{con}}\quad A;B\subseteq C.}$

La solución del rompecabezas, sugerencias para que una nueva q entre en Q , proviene de arreglos prohibidos.${\displaystyle {\bar {C}},}$, el complemento de C en Q x Z : herramientas útiles en el cálculo de relaciones son los residuos :

${\displaystyle A\backslash C={\overline {A^{T};{\bar {C}}}}}$mapas T a Z y

${\displaystyle C/B={\overline {{\bar {C}};B^{T}}}}$asigna Q a T.​