¿Cómo resuelvo el sudoku más difícil del mundo '?

Adivinar valores individuales en una búsqueda en profundidad es subóptimo.

Entonces, aquí hay una cadena de razonamiento basada en un método de hipótesis / refutación que da prioridad a la amplitud (que mi hijastro llama de mala gana «adivinación educada»).

Solo seguir la cadena, incluidas las contradicciones, requiere para resolver 23 variantes del sudoku, por lo que es mejor usarlo con un solucionador asistido por computadora. Sin embargo, no requiere ningún algoritmo sofisticado para seguirlo. (Yo uso mi propio programa de Python no optimizado de cosecha propia, por lo que no hay el poder involucrado).

La notación sigue las convenciones de la hoja de cálculo (columna = letra, fila = número) (o ajedrez si lo desea).

STA Original Sudoku G8: 3,9 HYP # I8: 3,9 DIS # I8: 3,9 # B1: 1,2 => CTR => B1: 6 STA # I8: 3,9 + B1: 6 DIS # I8: 3,9 + B1: 6 # A2: 1,2 => CTR => A2: 5,9 STA # I8: 3,9 + B1: 6 + A2: 5,9 DIS # I8: 3,9 + B1: 6 + A2: 5,9 # B5: 1,2 => CTR => B5: 3,8 DIS # I8: 3,9 + B1: 6 + A2: 5,9 + B5: 3,8 => CTR => I8: 2,7 STA I8: 2,7 HYP I8: 2,7 # G7: 5 DIS I8: 2,7 # G7: 5 # G4: 6 => CTR => G4: 1,8 STA I8: 2,7 # G7: 5 + G4: 1,8 DIS I8: 2,7 # G7: 5 + G4: 1,8 # C5: 2,9 => CTR => C5: 6 STA I8: 2,7 # G7: 5 + G4: 1,8 + C5: 6 DIS I8: 2,7 # G7: 5 + G4: 1,8 + C5: 6 # H3: 4,5 => CTR => H3: 8 DIS I8: 2,7 # G7: 5 + G4: 1,8 + C5: 6 + H3: 8 => CTR => G7: 3,9 STA I8: 2,7 + G7: 3,9 HYP I8: 2,7 + G7: 3,9 # A8: 3,4,6 DIS I8: 2,7 + G7: 3,9 # A8: 3,4,6 # A9: 3 => CTR => A9: 6,7 STA I8: 2,7 + G7: 3,9 # A8: 3,4,6 + A9: 6,7 DIS I8: 2,7 + G7: 3,9 # A8: 3,4,6 + A9: 6,7 # D7: 2,7 => CTR => D7: 4,9 STA I8: 2,7 + G7: 3,9 # A8: 3,4,6 + A9: 6,7 + D7: 4,9 PRF I8: 2,7 + G7: 3,9 # A8: 3,4,6 + A9: 6,7 + D7: 4,9 => SOL 

He puesto capturas de pantalla de los pasos y una explicación rápida del método en el World «s Hardest Sudoku . Dado que solo estoy interesado en resolver acertijos difíciles mediante «suposiciones informadas», descubrí que este sudoku en realidad no es tan difícil como se anuncia (1 nivel de hipótesis + 1 anticipación = 2 niveles de hipótesis). De hecho, todavía no he encontrado un sudoku que requiera más de 2 niveles de hipótesis + una anticipación (= 3 niveles de hipótesis).

Comentarios

• ¿Qué tan bueno es su solucionador contra los sudoku ‘ s con 17 entradas? P.ej. theconversation.com/…
• @SimonStreicher El sudoku de 17 pistas, que estás citando es difícil, pero no entre los sudokus más difíciles en el contexto de mi algoritmo. Generalmente, no hay correlación entre el número de pistas y la dureza de un sudoku. He puesto algunas estadísticas sobre los sudokus que he analizado.
• @SimonStreicher Tengo analizó la lista de los 95 sudokus principales (es decir, los 95 acertijos difíciles ). Hay 5 sudukos con nivel difícil (son necesarios 2 niveles de hipótesis), que todavía está 2 niveles por debajo del 101 sudokus más difícil I encontrado.
• Gracias por la información, ‘ todavía estoy tratando de darle sentido a todo esto, afortunadamente su sitio web es bastante completo.
• @SimonStreicher El núcleo de esto consiste en reducir el espacio de búsqueda de la activación de valores únicos a patrones (pares) fácilmente reconocibles que se utilizan para generar decisiones binarias con una mayor eliminación de posibilidades. P.ej.cell1 permite 2 valores posibles v1 y v2, cell2 permite los mismos valores posibles, pero adicionalmente una o más posibilidades v3, v4, v5. Por lo tanto, celda1 y celda2 son un par (ambos contienen v1 y v2) o la celda 2 solo puede ser una de v3, v4, v5. Luego se verifica esta hipótesis.

Para este acertijo, si bien tiene una y solo una solución, ningún patrón conocido funciona en él, aparte de una conjetura y verificación un poco más inteligente. El número de pasos que uno tiene que mirar hacia adelante para reducir las pistas es la métrica aquí, y este rompecabezas necesita nueve conjeturas secuenciales para alcanzar un estado solucionable.

El solucionador de SudokuWiki no puede obtenerlo porque simplemente tomaría demasiado tiempo hacerlo en Javascript y no está programado para adivinar números.

La solución requiere que uno asuma los valores de los cuadrados y luego reduzca el acertijo para ver si necesita más suposiciones; si lo hace, haga otra y continúe. Es una búsqueda profunda de las posibles soluciones, en esencia. El solucionador de sudoku-solutions encuentra la solución a este rompecabezas, pero cuando se le pide que proporcione los pasos, declara:

Este solucionador no pudo resolver el rompecabezas completamente por lógica, esto no significa que no haya una solución lógica.

y luego rápidamente falla al enumerar cualquiera de los pasos que usó para resolverlo. Esto solo sucede cuando el solucionador debe usar adivinanzas de ramificación de fuerza bruta para encontrar la solución.

Como resultado, no hay forma de que yo mismo pueda proporcionar razonablemente una respuesta de «cómo resolver este rompecabezas», ya que haciendo así que implicaría encontrar estas cadenas específicas y explicar por qué la otra gran cantidad de cadenas no funcionan.

Pero así es como se hace: suponga que un cuadrado es un número, luego otro, luego otro, y siga revisando hasta que haya llegado a una secuencia que todavía tenga sentido y le permita resolver el acertijo, o haya llegado a una contradicción y necesite retroceder e intentarlo de nuevo. Me temo que creo que esta es la mejor respuesta que puede obtener a esta pregunta.

Sin embargo, dado que solicitó una solución al rompecabezas, puedo proporcionarla (coloque el mouse sobre el bloque de spoiler):

Comentarios

• Buena recursividad.
• Me las arreglé para resolverlo con una profundidad de recursividad de 2 conjeturas como máximo. El Naked Singles » se ejecutó un total de 61812 veces (después de un almacenamiento en caché realizado en un nivel superior, sin que el recuento de ejecuciones sea de millones), » Hidden Singles » estrategia 32892 veces (más otras 28920 que se entregaron desde un caché) y se ejecutó una búsqueda con profundidad de solo 1 256 veces y se sirvió desde el caché otras 15 veces (en cada punto solo se hizo una suposición, aunque creo que la mayoría de estas ejecuciones sucedieron en la siguiente), y la búsqueda de dos niveles (donde ‘ realiza 2 intentos) solo se ejecutó una vez y la obtuvo.
• (también este es el único acertijo que no ‘ t crackear con mi programa con solo UN nivel de adivinación)

Descargue el solucionador de Sudoku del primer ministro de Singapur y aliméntelo con este rompecabezas (SOLO si está REALMENTE estancado). Lo crea o no, ese primer ministro hizo un programa bastante sólido, y aunque parece que se atasca por un tiempo allí, finalmente sale con la siguiente solución:

862 || 751 || 349
943 || 628 || 157 de 571 || 493 || 286
============
159 || 387 || 624
386 || 245 || 791
724 || 169 || 835
============
217 || 934 || 568
438 || 576 || 912
695 || 812 || 473

Sin embargo, aparentemente es posible resolverlo con lógica, según el tipo que inventó este rompecabezas. Los solucionadores tardaron 24 horas en hacerlo.

Nota: este rompecabezas tiene el 1 en la séptima línea en una posición diferente a la de las preguntas. Este rompecabezas tiene múltiples soluciones.

Comentarios

• Dudo que este rompecabezas original tenga múltiples soluciones (si eso es lo que está implícito). Su entrada al PM ‘ probablemente sea incorrecto: la fila 3, la columna 7 se proporciona como entrada como » 1 «, no » 7 » (una de las observaciones). Dada la entrada correcta al exe, genera la solución conocida.
• @SimonStreicher, la entrada incorrecta está en la fila 7, columna 3, donde el 7 debería ser un 1
• ¿Se atasca durante más de 5 segundos? Mi solucionador muy simple se las arregla para entrar en eso cantidad de tiempo.

Solo para agregar otra solución basada en computadora, luego use el Lenguaje de modelado MiniZinc puede escribir el siguiente programa:

int: n; array[1..n, 1..n] of 0..n: initial_grid; int: reg; array[1..n, 1..n] of 1..reg: regions; array[1..n, 1..n] of var 1..n: final_grid; include "alldifferent.mzn"; constraint forall(r, c in 1..n)(initial_grid[r, c] = 0 \/ initial_grid[r, c] = final_grid[r, c]); constraint forall(r in 1..n)(alldifferent([ final_grid[r, c] | c in 1..n ])); constraint forall(c in 1..n)(alldifferent([ final_grid[r, c] | r in 1..n ])); constraint forall(region in 1..reg)(alldifferent([ final_grid[r, c] | r, c in 1..n where regions[r, c] = region ])); solve satisfy; output [ show_int(1, final_grid[r, c]) ++ if c = n then ("\n" ++ if (r mod 3 = 0 /\ r < n) then "---------------------\n" else "" endif ) elseif c mod 3 = 0 then " | " else " " endif | r, c in 1..n ]; 

Junto con los datos apropiados file:

n = 9; reg = 9; regions = array2d(1..9, 1..9, [ 3 * (row div 3) + col div 3 + 1 | row, col in 0..8 ]); initial_grid = [| 8, 0, 0, 0, 0, 0, 0, 0, 0, | 0, 0, 3, 6, 0, 0, 0, 0, 0, | 0, 7, 0, 0, 9, 0, 2, 0, 0, | 0, 5, 0, 0, 0, 7, 0, 0, 0, | 0, 0, 0, 0, 4, 5, 7, 0, 0, | 0, 0, 0, 1, 0, 0, 0, 3, 0, | 0, 0, 1, 0, 0, 0, 0, 6, 8, | 0, 0, 8, 5, 0, 0, 0, 1, 0, | 0, 9, 0, 0, 0, 0, 4, 0, 0 |] ; 

Y usando el solucionador predeterminado en una computadora portátil bastante estándar, la solución sale en 100 ms, lo que supera la implementación de C ++ de PM Lee por una considerable margen.

Comentarios

• ¿Este algoritmo se basa en programación lineal?
• It ‘ s en el mismo ámbito: el solucionador es un solucionador de programación de restricciones, que funciona bien ya que el problema no es ‘ t realmente lineal, pero es un montón de restricciones. Utiliza un combinación de heurísticas para reducir el espacio de posibles soluciones con algunos métodos de búsqueda bastante básicos.
• Estoy ‘ estoy impresionado. Mi manual, muy simple lver en Kotlin lo supera en aproximadamente 5 segundos en mi computadora portátil, usando una profundidad de búsqueda de máximo 2.