Alguien puede producir un rompecabezas de sudoku donde adivinar más de un valor de la celda en un tiempo se requiere?

Question

Actualmente tengo un rompecabezas de sudoku solver del programa y he probado todos los puzzles que puedo encontrar que están etiquetados como "los más duros" en varios sudoku juegos de video y libros de rompecabezas. Mi solver ha resuelto todos ellos. Se utiliza en la actualidad las siguientes 4 reglas en tiempo polinomial (es decir, el polinomio de tiempo si la junta se $N^2 \times N^2$ en lugar de $9 \times 9$).

1) cada celda para ver si sólo uno de los valores es posible para el celular

2) Compruebe para cada fila/columna/bloque si hay un valor que sólo una célula puede tener

3) Compruebe para cada fila/columna/bloque si hay 2, las células que sólo puede tener el mismo 2 valores. (Luego hay otras plazas en el mismo grupo puede tener los valores)

4) Para cada fila/columna y bloque que se cruza con ella, a ver si hay un valor que sólo puede aparecer en la intersección de 3 células, ya sea para la fila/columna o para el bloque. Entonces no hay otras plazas en la fila/columna o bloque puede tener ese valor.

Después de que estas reglas se aplican repetidamente, si el rompecabezas no está resuelto, entonces el programa adivina un valor de una celda y ve si esto conduce a una solución o contradicción cuando los cuatro reglas se aplican repetidamente. Si la contradicción es la que se encuentra, entonces se quita el valor de los valores posibles para la célula. Esta adivinanza se aplica por separado para cada celda+valor posible si el número de valores posibles para la celda es de 3 o menos. No hay simultánea en vilo durante varias celdas. Si al menos un valor posible es removido por algunas células, los 4 reglas se aplicó de nuevo varias veces hasta que adivinar es necesario de nuevo. Y repetir. Si es que alguna vez sucede que las 4 reglas y adivinar no proporcionen ningún tipo de información adicional, entonces el programa se da por vencido y se imprime la solución parcial que se encuentran.

Ahora, hay alrededor de 10 o de 20 diferentes polinomio tiempo las reglas que se han ideado para descartar posibilidades y deducir de las células de los valores en el sudoku, y sólo he aplicado la 4. Además, la adivinación sólo se adivina una celda del valor en un momento y simplemente quita el valor de los valores posibles para el celular si existe una contradicción se encuentra. Así que es extraño para mí que este resuelve todos los puzzles más difíciles que puedo encontrar. Alguien puede producir un rompecabezas bastante difícil que mi programa no puede resolver?

Answer 1

No hay rompecabezas que no puede ser resuelto por sólo una suposición de una célula en un tiempo y volver atrás. Este método es llamado simplemente búsqueda en profundidad, y claramente siempre tendrá éxito, porque se va a tratar de cada posibilidad. Este método también es un algoritmo de tiempo exponencial, que es el más lento verá para problemas del mundo real. La única razón por la que parece ser rápido para el Sudoku es que hay muy pocas células en el primer lugar. Un método razonable de adivinar debe permitir que usted para resolver cualquier (9 veces 9) Sudoku en una fracción de segundo. Aquí hay dos ejemplos que usted puede intentar:

Puzzle 1

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

Puzzle 2

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

Puzzle 1 no puede ser resuelto por la mayoría simple Sudoku técnicas. Puzzle 2 es el que mi solver necesita revisar el mayor número de estados, de los aproximadamente 100 generado aleatoriamente puzzles con este tipo de patrón. Pero como ya he dicho, cualquier pésimo algoritmo de retroceso debe resolver en un segundo. Para probar realmente si su solver es eficiente, hay que extender el solucionador de 16 veces en 16 Sudoku y tratar de resolver el siguiente (la cantidad de tiempo que mi solver toma en un único procesador i5 de Intel está en paréntesis):

Rompecabezas 3 [3] (de esta página web al azar)

7   -   -   -   -   5   1   -   3   11  -   -   -   -   -   -
12  8   -   -   -   15  14  -   4   -   9   -   11  -   16  2
-   15  10  2   13  -   -   -   -   7   -   5   8   -   3   -
1   -   -   -   -   -   -   -   -   -   -   -   -   -   -   -
-   -   1   -   -   2   -   -   15  -   -   -   5   -   -   11
15  -   -   3   -   -   -   -   -   -   7   14  6   -   1   -
14  -   16  -   -   -   -   -   -   5   6   -   10  2   -   -
-   -   12  -   -   -   -   8   9   1   10  13  16  -   -   3
-   -   -   -   -   -   -   -   -   15  -   -   9   8   -   -
-   6   4   -   -   10  -   -   7   -   14  -   -   -   11  -
-   16  -   12  -   3   9   -   10  -   -   8   -   -   5   -
3   -   -   -   15  -   -   -   -   13  -   4   -   14  -   16
-   -   -   -   -   14  15  13  -   10  8   -   -   4   -   9
9   -   7   -   6   -   -   -   -   -   -   1   -   -   -   -
5   13  8   -   3   -   10  -   -   -   11  6   -   -   15  -
10  1   15  -   -   -   5   16  14  -   4   -   -   6   -   -

Puzzle 4 [26] (desde otra página web al azar)

-   -   10  -   -   -   -   15  6   -   -   5   -   -   -   -
15  -   -   -   10  13  -   -   -   14  8   -   9   -   5   -
-   5   7   11  -   9   -   -   -   -   -   -   -   -   -   -
-   -   13  2   -   14  -   -   10  -   7   11  -   15  16  3
-   -   -   16  -   -   -   -   -   -   -   7   -   3   11  9
13  2   15  4   1   3   -   -   -   -   -   -   -   12  -   -
1   3   12  -   16  7   -   -   -   2   10  -   -   -   -   15
11  6   -   -   -   8   -   -   -   -   13  -   -   -   2   10
2   16  -   -   -   12  -   -   -   -   11  -   -   -   14  4
3   -   -   -   -   1   4   -   -   -   14  10  -   9   15  6
-   -   9   -   -   -   -   -   -   -   6   8   11  2   10  5
5   12  1   -   15  -   -   -   -   -   -   -   7   -   -   -
16  7   3   -   2   11  -   12  -   -   5   -   15  14  -   -
-   -   -   -   -   -   -   -   -   -   3   -   2   8   13  -
-   13  -   8   -   10  6   -   -   -   1   16  -   -   -   12
-   -   -   -   7   -   -   8   14  -   -   -   -   5   -   -

Mi solver utiliza ninguna de las estrategias de todos, pero sólo adivinando, y así el código es muy corto. Hay un montón más que se puede tratar desde el segundo enlace, pero vas a tener que copiar el rompecabezas de sí mismo.

Answer 2

En respuesta a la OP solicitud voy a postear esto como una respuesta - a pesar de todo lo que hice fue pasar a conocer de un lugar en donde se encontró un rompecabezas en el que derrotó a su algoritmo.

Peter Norvig precioso ensayo aquí - norvig.com/sudoku.html - se analiza el diseño y la (Python) implementación de su sudoku solver. Si es o no responde a su pregunta acerca de retroceso profundidad de la recursión su pena leer. – Ethan Bolker Jun 19 a las 19:03

@EthanBolker gracias por el enlace. Norvig, definitivamente, permite conjeturar en una "profundidad" (número de conjeturas realizarse simultáneamente) mayor que 1. Pero parece que solo utiliza 2 muy básico polinomio tiempo de deducción de reglas, mientras que yo uso 4. Hizo mención de algunas de sus más difícil rompecabezas, aunque algunos de ellos tienen soluciones múltiples y algunos de ellos no tienen ninguno. En mi paradigma (y la mayoría de Sudoku jugador de los entusiastas de paradigma), asumimos que un rompecabezas tiene exactamente 1 solución. Algunas de sus "más difícil" rompecabezas tenido esta propiedad. Voy a probar y ver qué pasa. Gracias de nuevo por la info. +1. – user2566092 Jun 19 a las 19:34

@EthanBolker Si este post como respuesta, voy a aceptar y el premio de la recompensa, porque el rompecabezas de Norvig del 95 "difícil" que publicó que tomó más tiempo para su solver para resolver no era capaz de resolver mis problemas. También se proporciona un enlace a "más difícil Sudoku" que llevó a un rompecabezas Inkala que mi solver también fracasó. – user2566092 hace 2 horas

Answer 3

Comenzar con un simple rompecabezas, y luego me hizo esto más difícil y más difícil por la extracción del conocido campo de los valores. El principal dureza de un rompecabezas de sudoku es en el principio.