Generando un sudoku de una dificultad deseada?

Question

Así que he leído bastante sobre la generación de un rompecabezas de Sudoku. Por lo que puedo decir, la manera estándar de tener un acertijo de Sudoku de una dificultad deseada es generar un acertijo, y luego calificarlo luego, y repetirlo hasta que tengas uno de una calificación aceptable. Esto se puede refinar generando a través de retroceso utilizando algunos de los patrones de resolución más complejos (ala XY, pez espada, etc.), pero eso no es todo lo que quiero hacer aquí.

Lo que quiero hacer, pero no he podido encontrar ningún recurso real, es generar un acertijo desde un "valor de dificultad" (valor 0-1.0, 0 es el más fácil y 1.0 es el más difícil).

Por ejemplo, quiero crear un rompecabezas moderadamente difícil, por lo que se selecciona el valor .675. Ahora, usando ese valor, quiero poder generar un acertijo moderadamente difícil.

¿Alguien sabe algo como esto? ¿O tal vez algo con una metodología similar?

Answer 1

No es tan elegante como lo que pides, pero se puede simular este comportamiento con el almacenamiento en caché:

1. decidir el número de "cubos" que desea para los rompecabezas. Por ejemplo, digamos que eliges 20. Por lo tanto, tus cubos contendrán rompecabezas de diferentes rangos de dificultad: 0-.05, .05-.1, .1-.15, .., .9-.95, .95- 1
2. generar un rompecabezas
3. Grado rompecabezas
4. lo puso en el cubo correspondiente (o tirar a la basura cuando la cubeta está llena)
5. Repita hasta que sus cubos son "llenos". El tamaño de los depósitos y dónde se almacenan se basará en las necesidades de su aplicación.

Luego, cuando un usuario solicita un cierto rompecabezas de dificultad, proporciónele uno en la memoria caché del cubo que elija. También puede considerar intercambiar números y cambiar la orientación de rompecabezas con dificultades conocidas para generar acertijos similares con el mismo nivel de dificultad. Luego repite lo anterior según sea necesario cuando necesites rellenar tus cubos con nuevos rompecabezas.

Answer 2

Bueno, no se puede saber lo complicado que es, antes de saber cómo resolverlo. Y la resolución de Sudoku (y, por lo tanto, también la calificación de dificultad) pertenece al NP-C complexity class, lo que significa que (lógicamente) es lógicamente imposible encontrar un algoritmo que sea (asintóticamente) más rápido que la propuesta aleatoria de adivinar y verificar.

Sin embargo, si usted puede encontrar uno, que haya resuelto el P versus NP problem y debe borrar un armario para el Fields Medal ... :)

Answer 3

La dificultad del sudoku está relacionado de una manera interesante de la (mínima) cantidad de información necesaria para especificar una solución única para una grilla determinada.

Suena a teoría de la información, sí, tiene aplicaciones aquí también.

Sudoku debe tener una solución única. Además, los rompecabezas de sudoku tienen ciertas simetrías, es decir, por fila, por columna y por sub-cuadrado.

Estas simetrías especifican el número mínimo de pistas (y su posición más o menos) necesarias para que la solución sea única (es decir, utilizando un compilador de sudoku o un algoritmo como la búsqueda de retroceso).

Este sería el nivel de sudoku más difícil/difícil (es decir, el número mínimo necesario de pistas). Luego, todos los demás niveles de dificultad, desde los menos difíciles a los más fáciles, se generan al permitir más pistas que la cantidad mínima necesaria.

Cabe señalar que los niveles de dificultad sudoku son no estándar, como se explicó anteriormente, uno puede tener tantos o tan pocos niveles de dificultad como uno quiera. Lo que es estándar es el número mínimo (y posición) de pistas (que es el nivel más difícil y que está relacionado con las simetrías de sudoku), entonces uno puede generar tantos niveles de dificultad como uno quiera simplemente permitiendo que las pistas extra/redundantes sean visibles también.

Answer 4

Agregando otra respuesta para generar un sudoku de la dificultad deseada sobre la marcha.

Esto significa que a diferencia de otros enfoques el algoritmo se ejecuta sólo una vez y devuelve una configuración sudoku búsqueda de la dificultad deseada (con alta probabilidad dentro de un rango o con probabilidad = 1)

diversas soluciones para la generación de (y clasificación) una dificultad sudoku tiene que ver con human-based techniques and approaches, que puede ser fácilmente nominal.

Entonces uno (después de haber generado una configuración sudoku) re-resuelve el sudoku con el solucionador similar a la humana y dependiendo de las técnicas de la solucionador utilizada (por ejemplo pares, Ala-X, pez espada etc.) también se asigna una tasa de dificultad.

problemas con este enfoque (y los requisitos para el caso de uso que tenía)

1. Con el fin de generar un sudoku con dificultad dado, con el método anterior se necesita para resolver un sudoku dos veces (una vez con el algoritmo básico y una vez con el solucionador humano).

2. Uno tiene que (pre) generar muchos sudokus que solo pueden ser calificados como de dificultad después de ser resueltos por el solucionador humano. Entonces uno no puede generar un sudoku deseado sobre la marcha una vez.

3. El solucionador similar al humano puede ser complicado y en la mayoría de los casos (si no todos) está estrechamente vinculado a las cuadrículas de sudoku de 9x9. Por lo tanto, no es fácil generalizar a otros sudokus (por ejemplo, 4x4, 16x16, 6x6, etc.)

4. La calificación de dificultad de las técnicas similares a las humanas es muy subjetiva. Por ejemplo, ¿por qué se toma x-wing como más difícil que singles ocultos? (Personaly han resuelto muchos difíciles publicados Sudokus utilizados manualy y nunca tales técnicas)

fue utilizado Otro enfoque que tiene los siguientes beneficios:

1. generaliza bien a sudokus arbitraria (9x9, 4x4, 6x6 , 16x16 etc.)
2. La configuración de sudoku, con la dificultad deseada, se genera una vez y sobre la marcha
3. La calificación de dificultad es baja.

Cómo funciona?

En primer lugar, el simple hecho de que cuanto más difícil es el rompecabezas, más tiempo tiene que resolverse.

Pero el tiempo que debe resolverse está íntimamente correlacionado con el número de pistas (datos) y con las alternativas promedio que deben investigarse por celda vacía.

La extensión de mi previous answer, se mencionó que para cualquier sudoku el número mínimo de pistas es una propiedad objetiva del puzzle (por ejemplo for 9x9 grids the minimum number of clues for having a valid sudoku is 17)

Uno puede comenzar a partir de ahí y calcular el número mínimo de pistas por la dificultad nivel (correlación lineal).

Además en cada paso del proceso de generación sudoku, uno puede asegurarse de que (a ser investigadas) las alternativas promedio por celda vacía está dentro de límites dados (como una función de la dificultad deseada)

Dependiendo de si el algoritmo utiliza la función de retroceso o no (para el caso de uso analizado, el algoritmo no realiza retrocesos) se puede alcanzar la dificultad deseada, ya sea con probabilidad = 1 o con alta probabilidad dentro de límites (respectivamente).

Las pruebas del sudokus generado con este algoritmo y calificación de dificultad en base a los enfoques anteriores (humano-como solucionador), muestran una correlación de tasas de dificultad deseadas y estimadas, más una mayor capacidad de generalización a configuraciones de sudoku arbitrarias.

(han utilizado esta línea sudoku solver (y también this one) para correlacionar las tasas de dificultad de la prueba de sudokus)

El código está disponible de on github sudoku.js (along with sample demo application), una versión a escala reducida de un crucigrama CrossWord.js constructor profesional en JavaScript, por el mismo autor