Sudoku garantizados para ser solucionable?

Question

Quiero generar al azar sudokus.

Mi enfoque es llenar la de tres 3x3 grupos en la diagonal de la red, cada uno con los números 1-9 ordenan aleatoriamente. Que se ve como la cuadrícula de abajo:

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

Entonces dejé que mi sudoku solver proceso hasta que se encuentre una solución para llenar todos los huecos que queden. El ejemplo anterior se tradujo en el llenado de la cuadrícula de abajo:

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

Mi pregunta es si este enfoque es matemáticamente segura, es decir, se puede demostrar a mí que cuando me llene mi grid mediante el método descrito (de forma aleatoria la asignación de los 27 primeros números de los campos en los grupos en una línea diagonal), siempre habrá al menos un camino posible para completar la cuadrícula a partir de ahí?

O hay posibilidades de que el puesto al azar los números pueden interferir unos con otros y el resultado en un imposible cuadrícula?

Answer 1

WLOG el bloque superior es en el orden canónico, porque podemos etiquetar de nuevo, como en 5 -> 1, 6 -> 2, … en su ejemplo. No voy a hacer que la sustitución por el resto de la cuadrícula, pero sólo pretendo que comenzó como eso.

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

Haciendo pequeños fila swaps dentro de uno de los tres grandes filas, o haciendo pequeños de la columna de swaps dentro de una de las tres grandes columnas, no cambia solveability del sudoku. Por lo tanto, podemos WLOG que la parte superior-izquierda de la entrada de cada una de las tres rejillas es de 1, por la rotación:

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

Del mismo modo podemos WLOG que a las 5 de la media del bloque aparece en uno de dos lugares:

+-------+
| 1 *   |
| ! *   |
|       |
+-------+

porque si en cualquiera de los otros, podemos fila/columna de intercambio en una de aquellas. La excepción es que si es en el ! posición, que en realidad es equivalente a la cima *. Esto es debido a que podemos transponer toda la cuadrícula, y re-etiquetar la parte superior izquierda del bloque de nuevo, sin afectar el medio del bloque de 1 o 5, excepto en las mueve a la posición correcta.

Lo mismo (pero sin la opción de reflejar este tiempo, ya que podría estropear el medio bloque) podemos WLOG que la parte inferior derecha del bloque 5 se encuentra en una de las tres posiciones:

+-------+
| 1 *   |
| * *   |
|       |
+-------+

Ahora hay $2 \times 7! \times 3 \times 7! = 152409600$ restante de los casos, que se deja como ejercicio para el lector.

Answer 2

He trabajado este, sobre el papel, dibujando una cuadrícula de sudoku y poner todos los números para cada dígito lugar, la columna y la fila que podía y no podía ser. Mientras el programa se está utilizando es 100% fiable, hay al menos una solución adecuada a cada uno de los 27 números en la diagonal. Lo siento no te puedo dar una fórmula para prueba, este tipo de cosas en las que estoy mejor en la visualización de la misma.