javascript - resuelve - sudoku para principiantes

Grado de dificultad Sudoku nivel (6)

¿Quizás podrías calificar la "limitación" general de un rompecabezas? Tenga en cuenta que un nuevo rompecabezas (con solo sugerencias) puede tener un cierto número de celdas que se puede determinar simplemente eliminando los valores que no puede contener. Podríamos decir que estas celdas están "limitadas" a un número menor de valores posibles que las celdas típicas, y mientras más celdas limitadas existen, más progreso se puede hacer en el rompecabezas sin adivinar. (Aquí consideramos que el requisito de "adivinar" es lo que hace difícil un rompecabezas).

Sin embargo, en algún momento, el jugador debe comenzar a adivinar y, nuevamente, la restricción de una celda es importante porque, al elegir entre menos valores para una celda determinada, es más fácil encontrar el valor correcto (y aumentar la restricción de otras celdas). ).

Por supuesto, en realidad no juego al Sudoku (solo disfruto escribiendo juegos y solucionadores), así que no tengo idea de si esta es una métrica válida, solo estoy pensando en voz alta =)

Estoy construyendo un juego de Sudoku por diversión, escrito en Javascript.
Todo funciona bien, el tablero se genera completamente con una sola solución cada vez.

Mi único problema es, y esto es lo que me impide que mi proyecto se publique públicamente
es que no sé cómo calificar mis tablas para los niveles de dificultad. He mirado por todos lados
publicado en foros, etc. No quiero escribir los algoritmos yo mismo, ese no es el punto de este proyecto,
y al lado, son demasiado complejos para mí, ya que no soy matemático.

Lo único a lo que me acerqué fue a este sitio web que califica a través de JS
pero el problema es que el código está escrito de una manera tan poco documentada, muy ad hoc,
por lo tanto no puede ser prestado ...

Iré al punto -
¿Alguien me puede indicar un lugar que ofrezca un código fuente para la calificación / calificación de Sudoku?

Gracias

Actualización 22.6.11:
Este es mi juego de Sudoku , y he implementado mi propio sistema de calificación que se basa en
En técnicas básicas de resolución de lógica humana, así que échale un vistazo.

Donald Knuth estudió el problema y creó el algoritmo de Dancing Links para resolver el sudoku y luego evaluar la dificultad de los mismos.

Google alrededor, hay varias implementaciones del motor Dancing Links.

He hecho esto en el pasado.

La clave es que tienes que descubrir qué reglas usar desde la perspectiva de la lógica humana. El ejemplo que proporciona detalla una serie de diferentes patrones de lógica humana como una lista a la derecha.

Realmente necesitas resolver el rompecabezas usando estas reglas en lugar de las reglas de la computadora (que pueden resolverlo en milisegundos usando un reemplazo de patrón simple). Cada vez que cambias el tablero, puedes volver a comenzar desde el patrón "más fácil" (por ejemplo, abrir cajas en una celda o fila), y moverte hacia abajo en la cadena hasta que encuentres una de las siguientes "reglas" lógicas para usar.

Al puntuar el sodoku, a cada metodología se le asigna algún valor en puntos, que sumaría para cada campo que necesita completar. Mientras que ''una sola celda vacía'' puede obtener un 0, ''XY Chain'' puede obtener 100. Usted tabula todos los métodos necesarios (y la frecuencia) y termina con una ponderación final. Hay muchos lugares que enumeran los valores esperados para esas ponderaciones, pero todos son bastante empíricos. Está intentando modelar la lógica humana, así que siéntase libre de crear sus propias ponderaciones o mejorar el sistema (si realmente solo usa cadenas XY, el rompecabezas es probablemente más fácil que si requiere mecanismos más avanzados).

También puede encontrar que a pesar de tener un sodoku único, es imposible de resolver a través de la lógica humana.

Y también tenga en cuenta que todo esto es mucho más intensivo en CPU que resolverlo de una manera estándar y con patrón. Hace algunos años, cuando escribí mi código, tomaba varios (me olvido exactamente, pero tal vez incluso hasta 15) segundos para resolver algunos de los rompecabezas generados que había creado.

Suponiendo que la dificultad es directamente proporcional al tiempo que le lleva al usuario resolver el enigma, aquí hay una solución Artificialmente Inteligente que se acerca a los resultados del algoritmo ideal a lo largo del tiempo.

Genere aleatoriamente un número fijo de diseños de rompecabezas iniciales, por ejemplo, 100.
Inicialmente, ofrezca una sección de dificultad aleatoria que permita a un usuario jugar rompecabezas aleatorios de los diseños disponibles.
Mantenga un tiempo de solución aleatorio promedio para cada usuario. Probablemente haría una tabla de clasificación de top 10 / top X para que esto genere interés en jugar rompecabezas aleatorios.
Mantenga un multiplicador de tiempo de solución promedio para cada solución de rompecabezas (si el usuario normalmente resuelve el rompecabezas en 5 minutos y lo resuelve en 20 minutos, 4 debe figurar en el multiplicador de tiempo de solución promedio de los rompecabezas)
Una vez que se haya jugado un rompecabezas las veces suficientes para obtener una dificultad básica para el rompecabezas, digamos 5 veces, agregue ese rompecabezas a su lista de rompecabezas clasificados y agregue otro rompecabezas generado aleatoriamente a sus diseños de rompecabezas disponibles.
Nota: debe mantener el primer enigma en su lista de rompecabezas al azar para que pueda obtener mejores estadísticas.
Una vez que tenga suficientes rompecabezas con calificación básica, digamos 50, permita a los usuarios acceder a la parte de "Dificultad clasificada" de su aplicación. La dificultad para cada rompecabezas será el multiplicador de tiempo promedio para ese rompecabezas.
Nota: cuando los usuarios eligen jugar rompecabezas con dificultad clasificada, esto NO debe afectar el tiempo de solución aleatorio promedio o el multiplicador de tiempo de solución promedio, a menos que desee calcular los promedios ponderados (de lo contrario, si un usuario juega muchos rompecabezas más difíciles, su promedio los multiplicadores de tiempo y tiempo serán sesgados).

Usando el método anterior, una solución se calificaría de 0 (ya resuelto / sin tiempo para resolver) a 1 (los usuarios probablemente resolverán este rompecabezas en su tiempo promedio) a 2 (los usuarios probablemente tomarán el doble de tiempo para resolver este rompecabezas que su tiempo promedio) hasta el infinito (los usuarios tardarán una eternidad en encontrar una solución para este rompecabezas).

Tengo un solucionador simple que busca solo posibilidades únicas en filas, columnas y cuadrados. Cuando ha resuelto las pocas celdas que se pueden resolver con este método, selecciona un candidato restante que lo intenta y ve si el solucionador simple conduce a una solución o una celda sin posibilidades. En el primer caso, el enigma se resuelve, en el segundo, una posibilidad ha demostrado ser inviable y, por lo tanto, eliminada. En el tercer caso, que no conduce a una solución final ni a una inviabilidad, no se puede alcanzar una deducción.

El resultado principal del ciclo a través de este procedimiento es eliminar las posibilidades hasta que elegir una entrada de celda correcta lleve a una solución. Hasta ahora, este procedimiento ha resuelto incluso los rompecabezas más difíciles sin fallar. Resuelve puzzles sin dificultad con múltiples soluciones. Si los candidatos de prueba son elegidos al azar, generará todas las soluciones posibles.

Luego genero una dificultad para el rompecabezas basado en la cantidad de candidatos ilegales que deben eliminarse antes de que el solucionador simple pueda encontrar una solución.

Sé que esto es como adivinar, pero si la lógica simple puede eliminar un posible candidato, entonces uno está más cerca de la solución final.

Micro

Yo mismo he considerado este problema y lo mejor que puedo hacer es decidir qué tan difícil es resolver el enigma resolviéndolo y analizando el árbol del juego.

Inicialmente: implemente su solucionador usando "reglas humanas", no con algoritmos que probablemente no sean utilizados por jugadores humanos. (Un problema interesante en sí mismo). Anota cada regla lógica en tu solucionador de acuerdo con su dificultad para que los humanos la usen. Use valores de cientos o más para que tenga libertad para ajustar las puntuaciones entre sí.

Resolver el rompecabezas. En cada posición:

Enumere todas las celdas nuevas que se pueden deducir lógicamente en la posición actual del juego.
El puntaje de cada deducción (la resolución completa de una celda) es el puntaje de la regla más fácil que basta para hacer esa deducción.
EDITAR: Si se debe aplicar más de una regla a la vez, o una regla varias veces, para realizar una deducción, realice el seguimiento como una única aplicación de regla "compuesta". Para calificar un compuesto, tal vez use el número mínimo de aplicaciones de reglas individuales para resolver una celda por la suma de las puntuaciones de cada una. (Se requieren mucho más esfuerzo mental para tales deducciones). Calcular el número mínimo de aplicaciones podría ser un esfuerzo intensivo de CPU en función de su conjunto de reglas. Cualquier aplicación de regla que resuelva por completo una o más celdas debe revertirse antes de continuar explorando la posición.
Excluya todas las deducciones con una puntuación superior al mínimo entre todas las deducciones. (La lógica aquí es que el jugador no percibirá los más difíciles, ya que percibió uno más fácil y lo tomó, y además, esto promete eliminar muchos cálculos del proceso de decisión).
La puntuación mínima en la posición actual, dividida por el número de deducciones "más fáciles" (si existen muchas, encontrar una es más fácil) es la dificultad de esa posición. Entonces, si la regla A es la regla más fácil de aplicar con un puntaje de 20 y se puede aplicar en 4 celdas, la posición tiene un puntaje de 5.
Elige una de las deducciones "más fáciles" al azar como tu juego y avanza a la siguiente posición de juego. Sugiero retener solo celdas completamente resueltas para la siguiente posición, sin pasar por ningún otro estado. Esto es un desperdicio de CPU, por supuesto, repetir los cálculos ya realizados, pero el objetivo es simular el juego humano.

La dificultad general del rompecabezas es la suma de las puntuaciones de las posiciones en tu camino a través del árbol del juego.

EDITAR: Puntuación de posición alternativa: en lugar de excluir por completo las deducciones utilizando reglas más difíciles, calcule la dificultad general de cada regla (o aplicación compuesta) y elija el mínimo. (La lógica aquí es que si la regla A tiene un puntaje de 50 y la regla B tiene un puntaje de 400, y la regla A se puede aplicar en una celda, pero la regla B se puede aplicar en diez, entonces el puntaje de posición es 40 porque es más probable que el jugador Encuentra una de las diez jugadas más difíciles que la única más fácil. Pero esto requeriría que computes todas las posibilidades.

EDITAR: Alternativa sugerida por Briguy37: Incluir todas las deducciones en el puntaje de la posición. Califique cada posición como 1 / (1/d1 + 1/d2 + ...) donde d1 , d2 , etc. son las deducciones individuales. (Básicamente, esto calcula la "resistencia a realizar cualquier deducción" en una posición dada por las "resistencias de deducción" d1 , d2 , etc., pero esto requiere que usted calcule todas las posibilidades).

Con suerte, esta estrategia de puntuación producirá una métrica para los rompecabezas que aumenta a medida que aumenta su valoración subjetiva de la dificultad. Si no es así, el ajuste de las puntuaciones de sus reglas (o su elección de heurística de las opciones anteriores) puede lograr la correlación deseada. Una vez que haya logrado una correlación consistente entre el puntaje y la experiencia subjetiva, debería poder juzgar cuáles deberían ser los umbrales numéricos de "fácil", "difícil", etc. Y luego ya está!