¿Cómo puedo generar rompecabezas de Sudoku?

Estoy tratando de hacer un generador de rompecabezas Sudoku. ¡Es mucho más difícil de lo que esperaba y cuanto más me meto en él, más difícil se vuelve!

Mi enfoque actual es dividir el problema en 2 pasos:

1. Genera un rompecabezas de Sudoku completo (resuelto).
2. Elimine los números hasta que sea solucionable y tenga solo 1 solución.

En el paso 1, dado que estoy usando métodos de fuerza bruta, me enfrento a algunos problemas de tiempo de ejecución. ¿Hay una manera óptima de completar un rompecabezas de Sudoku completo?

En el paso 2, ¿qué tipo de algoritmo debo usar para "descifrar" un sudoku resuelto?

Tengo un juego de Sudoku más vendido en la tienda de aplicaciones de iOS. Así es como generé rompecabezas.

Primero tengo una aplicación de generador de rompecabezas. Pero no es parte del código del juego. Es una aplicación independiente que uso para hacer rompecabezas. Está muy modificado, por lo que puedo configurarlo para crear diferentes tipos de patrones, clasificaciones de dificultad, número de dados, etc. Generar rompecabezas y obtener un nivel de dificultad constante es difícil de hacer sobre la marcha y lleva más tiempo del que un jugador querría esperar. Entonces, genero lo que llamo "rompecabezas de semillas" y eso es lo que usa el código del juego para generar los rompecabezas que la gente juega.

No estoy respondiendo cómo codificar un generador aquí. Puede buscar en Google y encontrar toneladas de código generador de rompecabezas en línea. Comience por ahí. Pero para hacer un buen juego necesitas hacer un buen juego. Mi juego no genera rompecabezas sobre la marcha.

La forma en que funciona mi aplicación de generador de rompecabezas es que genera miles de rompecabezas por minuto, pero no todos son buenos y no todos coinciden con un índice de dificultad específico. El generador crea un rompecabezas, luego lo resuelve y calcula un índice de dificultad, y califica el rompecabezas en función de las técnicas necesarias para resolver el rompecabezas, y determina si es necesario adivinar para resolverlo (lo que generalmente es malo). Lanza cualquier rompecabezas que no coincida con un criterio. Para rompecabezas difíciles pero no imposibles, en una máquina rápida, puede tomar una hora generar 100 rompecabezas que coincidan con mis especificaciones exactas. Es por eso que no hago esto en la aplicación. Generar rompecabezas sobre la marcha con esas especificaciones difíciles no funcionaría para la calidad de los rompecabezas que tengo en mi aplicación.

Los rompecabezas son cadenas, 162 caracteres de largo, 81 caracteres con números y guiones o puntos donde van a estar los espacios en blanco, luego otros 81 con la solución. Luego columnas para cada una de las estadísticas, como cuántos singles, dobles, etc.

Mi salida de todas las sesiones de generación son líneas delimitadas por comas con las estadísticas como columnas. Tomaré unos 10,000 rompecabezas, los traeré para sobresalir y los ordenaré por dificultad. Luego, tráelos a una aplicación para verlos en el tablero de juego. También los miro por atractivo visual y los patrones visibles del rompecabezas. Luego selecciono a mano de esos.

Los llamo rompecabezas de semillas y esto es lo que quiero decir. Los números en un juego de sudoku son realmente solo fichas. En lugar de ser los números 1-9, podrían ser colores, símbolos o letras. Entonces mis rompecabezas de semillas no son números, son las letras ai. Cada rompecabezas de semillas se cambia sobre la marcha para hacer un rompecabezas jugable:

1. Aleatorizar los números / tokens. Cuando convierto las letras ai nuevamente en los números 1-9, la tabla de búsqueda es aleatoria. Lo que significa que a no siempre es 1. Eso solo crea alrededor de 300,000 variaciones en cada rompecabezas.
2. Gire el rompecabezas 90, 180 o 270 grados. Eso agrega 4 variaciones más.
3. Deja caer el rompecabezas horizontalmente, verticalmente o ambos. Eso agrega 4 variaciones más.

Por lo tanto, cada rompecabezas de semillas puede crear 5,806,080 variaciones. He probado esto en el campo con jugadores reales. La gente no sabe que esencialmente está jugando el mismo rompecabezas. Es imposible en realidad. Solo si se dieran cuenta de que el patrón en el que se encuentran los datos es el mismo cada vez. Pero con incluso 100 semillas diferentes, nadie se dará cuenta. Un millón de usuarios de mi juego no lo han hecho. También lo probé con aplicaciones de solución. Una aplicación de solución no resolverá un rompecabezas de la misma manera cuando se gira o se deja caer. Incluso a veces lo analizará como una calificación de dificultad diferente a pesar de que técnicamente es el mismo rompecabezas.

Sin embargo, Big Bad Sudoku Book tiene 10 de miles de rompecabezas de semillas en 5 niveles de dificultad y múltiples tipos de patrones de rompecabezas. Esto significa que hay miles de millones de rompecabezas en mi juego. Con cada 10,000 rompecabezas de semillas hay 58.060.800.000 rompecabezas diferentes.

En Sudoku Book versión 4 (disponible en 2016) descubrí una forma de poder especificar un rompecabezas exacto de esos 58 mil millones y obtener el mismo rompecabezas en el dispositivo de cada jugador.

En el paso (1) Genere un rompecabezas de Sudoku completo (resuelto), ya que estoy usando un método de fuerza bruta, me enfrento a algunos problemas de tiempo de ejecución. ¿Hay una manera óptima de completar un rompecabezas de Sudoku completo?

Hay una manera fácil de completar un rompecabezas de Sudoku completo: relleno de grupo y cambio circular.

1. Llena la primera fila con nueve números diferentes.
2. Rellene la segunda fila, que es un desplazamiento de la primera línea por tres espacios.
3. Rellene la tercera fila, que es un desplazamiento de la segunda línea por tres espacios.
4. Rellene la cuarta fila, que es un desplazamiento de la tercera por una ranura.

line 1: 8 9 3  2 7 6  4 5 1
line 2: 2 7 6  4 5 1  8 9 3 (shift 3)
line 3: 4 5 1  8 9 3  2 7 6 (shift 3)

line 4: 5 1 8  9 3 2  7 6 4 (shift 1)
line 5: 9 3 2  7 6 4  5 1 8 (shift 3)
line 6: 7 6 4  5 1 8  9 3 2 (shift 3)

line 7: 6 4 5  1 8 9  3 2 7 (shift 1)
line 8: 1 8 9  3 2 7  6 4 5 (shift 3)
line 9: 3 2 7  6 4 5  1 8 9 (shift 3)

Para evitar que el usuario note el patrón obvio, puede ser una buena idea aleatorizar el orden de las filas y las columnas para que ya no haya ningún patrón. Mientras los 9 números en cada fila / columna se muevan juntos como una unidad atómica, el tablero de Sudoku siempre será válido.

Obtienes un completo rompecabezas de Sudoku lleno. Para más detalles, puede buscar "hacer Sudoku".

No es demasiado difícil, siempre que tenga un solucionador de sudoku.

Hacer solucionadores de sudoku es un problema difícil / interesante, por lo que es mejor guardarlo para una pregunta diferente. O simplemente puedes leer esto y ver cómo te va.

1. Para generar un rompecabezas resuelto, simplemente ejecute el solucionador en un tablero vacío. La única advertencia es que debe aleatorizar las "conjeturas" que utiliza el solucionador, de lo contrario podría terminar con el mismo rompecabezas cada vez. Es decir, en algún momento el solucionador intentará un número para una celda; podría intentarlo en este orden: 1, 2, 3, 4, ...y elegir el primero que funcione. Es necesario para mezclar ese orden para que se trata, por ejemplo, 4, 7, 2, 9, .... Este proceso debe ser tan rápido como su solucionador.
2. Para eliminar números, use este algoritmo:
   • Elija un número aleatorio que no haya intentado eliminar antes
   • Elimine el número, ejecute su solucionador con la condición agregada de que no puede usar el número eliminado aquí
   • Si el solucionador encuentra una solución, no puede eliminar el número
   • Repita, hasta que haya eliminado suficientes números (o no pueda eliminar más)

Este es un método muy simple (e ingenuo), por lo que no hay garantía de que obtenga acertijos de cierta dificultad, aparte de la cantidad de números que faltan, o si incluso puede eliminar la cantidad de números que desea. Espero que esto ayude de todos modos.

Simplemente creo que es interesante señalar esta página web , ya que me ayudó mucho para el desarrollo de nuestro proyecto. Hacer un sudoku con una solución única está lejos de ser una tarea simple. En el enlace puede encontrar cómo el autor (¡realmente hizo un gran trabajo, no me eh!), Encontró varias estrategias diferentes. Puede tener una idea para generar su propio solucionador de Sudoku.

Ahora, siguiendo con el tema, también hay una manera de generar sudokus similares, solo con

1. La permutación de las filas.
2. Otra solución simple es comenzar con un sudoku de relleno de un mínimo de 17 dígitos (es el mínimo comprobado para encontrar una solución única) y completar las siguientes estrategias diferentes (por ejemplo, en el enlace anterior las estrategias se dividen en dificultades, usted puede hacer algo similar), hasta llegar a la solución única.
3. Había una lista de un matemático que intentaba encontrar un sudoku de solución única de 16 dígitos iniciales, con una lista HUGEEEEEE de sudokus de 17 dígitos. No puedo recordar si tiene algún tipo de copia escrita, pero estoy bastante seguro, si puede ofrecerle otras 17 soluciones únicas, sudoku estará más que feliz de permitirle usar sus datos.

Saludos y buena suerte con el algoritmo: D

Mi solucionador está utilizando la fuerza bruta y puede encontrar la solución en 20 milisegundos. Al usar el método de eliminación, descrito anteriormente, mi generador produce un rompecabezas en 200 milisegundos.

Por lo general, genera un rompecabezas con alrededor de 24-34 dígitos restantes, y todavía no sé cómo en el mundo logran producir rompecabezas de 17 dígitos.