Cobertura exacta

Sudoku se puede describir como una instancia de la cobertura exacta problema. Esto permite que tanto para una elegante descripción del problema y una solución eficiente utilizando un algoritmo de retroceso. Mientras que la cobertura exacta no garantiza tiempos de solución eficientes para grandes redes, las implementaciones de Sudoku usando algoritmos para la cobertura exacta, tales como enlaces de baile , por lo general resuelven 9x9 Sudokus con tiempo de cálculo mínima del orden de segundos.

Fuerza bruta Algoritmo

Algunos aficionados han desarrollado programas de ordenador que va a resolver los rompecabezas de Sudoku usando un algoritmo de fuerza bruta . Aunque se ha establecido que aproximadamente 6,67 x 10 ²¹ existen rejillas finales, un algoritmo informático fuerza bruta puede ser un método práctico para resolver los puzzles si el código está bien diseñado.

Las ventajas de este método son:

• una solución está garantizado (siempre que el rompecabezas es válida)

• tiempo a resolver es en su mayoría sin relación con el grado de dificultad

La desventaja de este método es que puede ser comparativamente lento cuando se compara con métodos de solución ordenador modelados después de métodos deductivos.

Un algoritmo de fuerza bruta visita las celdas vacías en algún orden, llenando secuencialmente los dígitos de las opciones disponibles, y dar marcha atrás (la eliminación de opciones fallidas) que se hayan alcanzado los callejones sin salida. En cada una de retroceso, se repite el algoritmo del dígito en la célula más recientemente llenó antes de la celda en la que se ve el callejón sin salida. Si esa célula en particular se trató con todos los dígitos posibles, el algoritmo da un paso atrás a la segunda célula antes de llenado antes de la última iteración callejón sin salida y el dígito de las células.

Por ejemplo, un programa de fuerza bruta podría resolver un rompecabezas colocando el dígito "1" en la primera celda y comprobar si se le permite estar allí. Si no hay violaciónes (comprobación de restricciones fila, columna y caja) entonces el algoritmo avanza a la siguiente celda, y coloca un "1" en esa celda. Cuando la comprobación de violaciónes, se descubre que no está permitido el "1", por lo que el valor se hace avanzar hacia un "2". Si una célula se descubre donde se permite que ninguno de los 9 dígitos, entonces el algoritmo deja que la celda en blanco y se mueve de nuevo a la celda anterior. El valor en esa celda se aumenta entonces en 1. El algoritmo se repite hasta que se encuentre una solución válida para todas las 81 células.

Estocásticos métodos de búsqueda / optimización

Sudoku se puede resolver utilizando estocástico (aleatorio)-búsqueda basados métodos. Un ejemplo de este enfoque es:

1. Al azar asignar números a las celdas vacías de la cuadrícula

2. calcular el número de errores

3. "Shuffle" estos números insertados en los alrededores de la red hasta que el número de errores se reduce a cero

A continuación, se ha encontrado una solución al rompecabezas. Enfoques para barajar las cifras incluyen el recocido simulado , algoritmos genéticos y búsqueda tabú . Algoritmos de optimización basado en estocásticos son conocidos por ser bastante rápida, a pesar de que son quizás no tan rápido como algunas de las técnicas basadas en la lógica. A diferencia de este último, sin embargo, los algoritmos de optimización no requieren necesariamente problemas para ser lógica solucionable, dándoles el potencial para resolver una gama más amplia de instancia problema. También se conocen algoritmos diseñados para colorear gráfico para llevar a cabo muy bien con los rompecabezas de Sudoku.

También es posible expresar un Sudoku como programación lineal entera problema. Tales enfoques parecen acercarse a una solución con bastante rapidez, y luego se pueden utilizar ramificación hacia el final. El algoritmo Simplex parece capaz de manejar situaciones sin soluciones o múltiples soluciones bastante bien.

Programación con restricciones

Sudoku es un problema de restricción. En su papel de Sudoku como un problema de restricción , Helmut Simonis describe muchos algoritmos de razonamiento disponibles en forma de restricciones que se pueden aplicar para modelar y resolver el problema. Algunos solucionadores de restricciones incluyen un ejemplo de cómo modelar y resolver problemas de Sudoku. El programa de modelado de la restricción y la solución de Sudoku en la mayoría de solucionadores tienen menos de 100 líneas de código. Si el código emplea un algoritmo fuerte razonamiento, la incorporación de una rutina de búsqueda sólo es necesario para los rompecabezas más difíciles.

Tiempo de cálculo

Algoritmos informáticos trabajan a través de cada vez más ciclos en la búsqueda de Sudokus con 20 pistas o menos. De hecho, los rompecabezas con 17 pistas son muy difíciles de encontrar. Cuando se aplica la restricción de simetría, el tiempo de búsqueda esperada aumentará dramáticamente aún más.

En blanco Sudokus

Aunque Sudokus que vienen con algunas de sus células precargadas a menudo puede ser muy difícil de resolver, en blanco Sudokus en realidad se pueden resolver muy rápidamente. Tal vez la forma más fácil de hacer esto es para producir la solución de la raíz , que se puede conseguir utilizando la siguiente sencillo algoritmo de tiempo polinómico .

Para el estándar N ² xn ² (9 x 9) parrilla de este algoritmo (implementaciones equivalentes en Java y Haskell ) es como sigue:

última int n = 3 ; última int [] [] campo = nueva int [ n * n ] [ n * n ]; para ( int i = 0 ; i < n * n ; i ++) para ( int j = 0 ; j < n * n ; j ++) campo [ i ] [ j ] = ( i * n + i / n + j ) % ( n * n ) + 1 ;

Sol :: [[ Int ]] sol = [ [ testigo ( construir i j ) | j <- [ 0 .. heightGame ] ] | i <- [ 0 .. heightGame ] ] , donde la acumulación i j = ( i * heightRegion ) + ( i ` div ` heightRegion ) + j testigo = ( ' mod ' heightGame ) . ( + 1 ) heightRegion = 3 heightGame = heightRegion ^ 2

El procedimiento anterior produce el siguiente Sudoku 9x9:

----------------------- + + | 1 2 3 | 4 5 6 | 7 8 9 | | 4 5 6 | 7 8 9 | 1 2 3 | | 7 8 9 | 1 2 3 | 4 5 6 | | ------- + ------- + ------- | | 2 3 4 | 5 6 7 | 8 9 1 | | 5 6 7 | 8 9 1 | 2 3 4 | | 8 9 1 | 2 3 4 | 5 6 7 | | ------- + ------- + ------- | | 3 4 5 | 6 7 8 | 9 1 2 | | 6 7 8 | 9 1 2 | 3 4 5 | | 9 1 2 | 3 4 5 | 6 7 8 | ----------------------- + +