Cómo generar tablas de Sudoku con soluciones únicas

Aquí está la forma en que mi propio programa de SuDoKu lo hace:

1. Comience con un tablero completo y válido (lleno con 81 números).

2. Haga una lista de las 81 posiciones de la celda y barajarla aleatoriamente.

3. Mientras la lista no esté vacía, tome la siguiente posición de la lista y elimine el número de la celda relacionada.

4. Pruebe la unicidad usando un solucionador de retroceso rápido. Mi solucionador es - en teoría-capaz de contar todas las soluciones, pero para al probar la singularidad, se detendrá inmediatamente cuando encuentre más de una solución.

5. Si la placa actual todavía tiene una sola solución, vaya al paso 3) y repita.

6. Si el tablero actual tiene más de una solución, deshaga la última eliminación (paso 3) y continúe el paso 3 con la siguiente posición de la lista

7. Deténgase cuando haya probado las 81 posiciones.

Esto te da no solo tableros únicos, sino tableros donde no puedes elimine más números sin destruir la singularidad de la solución.

Por supuesto, esta es solo la segunda mitad del algoritmo. La primera mitad es encontrar un tablero válido completo primero (¡llenado aleatoriamente!) Funciona muy similar, pero"en la otra dirección":

1. Empieza con un tablero vacío.

2. Agregue un número aleatorio en una de las celdas libres (la celda se elige aleatoriamente, y el número se elige aleatoriamente de la lista de números válidos para esto de acuerdo con las reglas del SuDoKu).

3. Utilice el solucionador de backtracking para comprobar si la placa actual tiene al menos una solución válida. Si no, deshaga el paso 2 y repita con otro número y celda. Tenga en cuenta que este paso puede producir tableros válidos completos por sí solo, pero estos no son de ninguna manera aleatorios.

4. Repita hasta que el tablero esté completamente lleno de números.

Puedes hacer trampa. Comience con un tablero de Sudoku existente que se puede resolver y luego juguetee con él.

Puede intercambiar cualquier fila de tres bloques de 3x3 con cualquier otra fila. Puede intercambiar cualquier columna de tres bloques de 3x3 con otra columna. Dentro de cada fila de bloque o columna de bloque puede intercambiar filas individuales y columnas individuales. Finalmente, puede permutar los números para que haya diferentes números en las posiciones llenas, siempre y cuando la permutación sea consistente en todo el tablero.

Ninguno de estos cambios harán que una placa resoluble sea irresoluble.

A menos que P = NP, no hay un algoritmo de tiempo polinómico para generar problemas generales de Sudoku con exactamente una solución.

En su tesis de maestría, Takayuki Yato definió El Problema de Otra Solución (ASP), donde el objetivo es, dado un problema y alguna solución, encontrar una solución diferente a ese problema o demostrar que no existe. Yato luego definió ASP-completitud, problemas para los cuales es difícil encontrar otra solución, y demostró que Sudoku es ASP-completo. Dado que también demuestra que ASP-completity implica NP-hardness, esto significa que si permites tableros de Sudoku de tamaño arbitrario, no hay un algoritmo de tiempo polinómico para verificar si el rompecabezas que has generado tiene una solución única (a menos que P = NP).

Lamento arruinar sus esperanzas de un algoritmo rápido!

No Es fácil dar una solución genérica. Necesitas saber algunas cosas para generar un tipo específico de Sudoku... por ejemplo, no se puede construir un Sudoku con más de nueve grupos vacíos de 9 números (filas, bloques 3x3 o columnas). Se cree que los números mínimos dados (es decir, "pistas") en un Sudoku de solución única son 17, pero las posiciones numéricas para este Sudoku son muy específicas si no me equivoco. El número promedio de pistas para un Sudoku es de aproximadamente 26, y no estoy seguro, pero si dejas números de un completada la cuadrícula hasta tener 26 y dejarlas de forma simétrica, es posible que tengas un Sudoku válido. Por otro lado, puede simplemente dejar de lado aleatoriamente los números de las cuadrículas completadas y probarlos con CHECKER u otras herramientas hasta que aparezca un OK.

También creo que tendrás que comprobar explícitamente la unicidad. Si usted tiene menos de 17 givens, una solución única es muy poco probable, sin embargo: Ninguno se ha encontrado todavía, aunque no está claro todavía si podría existir.)

Pero también puede usar un solucionador de SAT, en lugar de escribir un algoritmo de backtracking propio. De esa manera, puede regular hasta cierto punto lo difícil que será encontrar una solución: Si restringe las reglas de inferencia que usa el solucionador SAT, puede verificar si usted puede resolver el rompecabezas fácilmente. Solo busca en Google "sudoku de resolución de SAT".

Aquí hay una manera de hacer un rompecabezas de sudoku clásico (rompecabezas de sudoku con una única solución; los cuadrados precargados son simétricos alrededor del cuadrado central R5C5).

1) comience con una cuadrícula completa (usando relleno de grupo más desplazamiento circular para obtenerla fácilmente)

2) eliminar número(s) de dos cuadrados simétricos si los cuadrados despejados se pueden inferir utilizando las pistas restantes.

3) repita (2) hasta que todos los números estén marcados.

Usando este método puede crear un rompecabezas sudoku muy fácil con o sin programación. También puedes usar este método para crear rompecabezas Sudoku más difíciles. Es posible que desee buscar "crear sudoku clásico" en YouTube para tener un ejemplo paso a paso.