Cuando alguien crea un rompecabezas de Sudoku, ¿cómo saben lo difícil que será resolverlo (fácil, difícil o diabólico)?

En Puzzazz, tenemos un evaluador de software que imita la resolución humana de la mejor manera posible. No le importa cómo se ve el rompecabezas (ya sea en estética o cantidad de detalles). Puede haber rompecabezas fáciles de 24 dados y rompecabezas difíciles de 30 dados. Las técnicas requeridas, la complejidad de la resolución y el tiempo dedicado a resolverlo influyen en la dificultad resultante. Luego mapeamos la dificultad de nuestros acertijos contra los niveles de dificultad establecidos de una variedad de los libros más populares, que alimentamos al software con fines de calibración.

Algunas cosas interesantes que hemos aprendido:

* Las personas cuya única experiencia es en juegos de rompecabezas aleatorios de Sudoku tienen una idea muy diferente de la dificultad que las personas que resuelven Sudoku en el periódico o en los libros. Casi todos los juegos solo son capaces de producir acertijos fáciles (los que se pueden resolver solo conociendo las tres reglas básicas y no más), por lo que clasifican sus acertijos entre fácil, súper difícil, diabólico o loco (un nombre sorprendentemente popular para un nivel de dificultad en esos juegos aleatorios) únicamente en el número de obsequios. De hecho, todos son fáciles según la definición estándar.

* Algunos de los mejores solucionadores, como los que compiten en torneos de Sudoku, tienen diferentes niveles de dificultad. Estas personas conocen todas las técnicas de resolución posibles, incluidas las que el resto de nosotros ni siquiera podemos entender. Esas técnicas de resolución súper complejas son mucho más rápidas una vez que las entiendes. Por lo tanto, estas personas consideran que un rompecabezas es más fácil si se pueden aplicar más de esas técnicas, y consideran que un rompecabezas es más difícil si requiere una búsqueda “simple” o algo así que lleva mucho tiempo.

Creo que es justo dejar que los amantes del Sudoku califiquen el nivel de dificultad de un rompecabezas de Sudoku creado. Sin embargo, antes de resolver cualquiera, un fanático del Sudoku preferiría que el nivel de dificultad de un Sudoku ya se le haya dado.

En “Crear Sudoku”, medimos el nivel de dificultad de un Sudoku creado en función de los métodos que deben usarse para resolverlo, suponiendo que un solucionador de Sudoku siempre use las técnicas de resolución de la más fácil a la más difícil. Ella / Él solo usa un método de resolución avanzado cuando los métodos de resolución más fáciles no pueden resolverlo.

Create Classic Sudoku enumera muchas técnicas populares para resolver acertijos de Sudoku, desde las más fáciles hasta las más difíciles, como OneChoice, Elimination, interacción, subconjunto, X-wing, XY-wing, XYZ-wing y adivinanzas. Calificamos OneChoice y Elimination como técnicas de resolución fácil; Subconjunto, X-wing, XY-wing, XYZ-wing como técnica de resolución media; Adivinar como una técnica de resolución difícil; y Buscar como las técnicas de resolución más desafiantes.

Los métodos de resolución más fáciles son OneChoice y Elimination. La técnica de resolución de OneChoice es sencilla: si un cuadrado en blanco solo se puede llenar con un número porque todos los demás números se toman en su fila / columna / cuadro, llenamos este cuadrado vacío con este único número. La eliminación es eliminar las posibilidades de que un número vaya a otros cuadrados vacíos en una fila / columna / cuadro. Para un cuadrado vacío en una fila / columna / cuadro, si un número no tomado en esta fila / columna / cuadro no puede ir a otros cuadrados vacíos, llenamos este cuadrado en blanco con el número.

Crear Sudoku califica el nivel de dificultad de Sudoku de la siguiente manera:

Un Sudoku fácil es uno que puede resolverse mediante múltiples rondas de OneChoice y / o Elimination. Un Sudoku fácil es uno que se puede resolver sin enumerar los dígitos candidatos de los cuadrados vacíos.

Un Sudoku mediano es uno que debe resolverse mediante múltiples rondas de métodos avanzados que incluyen Subconjunto, SubsetPosition, Interacción, serie X-wing, XY-Wing y / o XYZ-Wing además de técnicas de resolución fácil. Para resolver un Sudoku de nivel medio, deberás enumerar los dígitos candidatos de los cuadrados vacíos.

Un Sudoku difícil es uno que debe resolverse adivinando además de técnicas de resolución fácil y / o media. Para resolver un Sudoku de nivel difícil, deberás enumerar los dígitos candidatos de cuadrados vacíos y adivinar.

Un Sudoku malvado / diabólico es uno que tiene que resolverse mediante una búsqueda exhaustiva, además de técnicas de resolución fácil, media y / o difícil. Para resolver un Sudoku de nivel maligno / diabólico, deberás enumerar los dígitos candidatos de cuadrados vacíos, adivinar y buscar.

Lo más importante al calificar un rompecabezas de Sudoku es qué técnicas están involucradas para resolverlo. Un buen comienzo es dar un puntaje a cada técnica (por ejemplo, soltero desnudo, soltero oculto, etc.) y luego sumar estos puntajes para un solucionador.

La única forma de hacer esto es tener un solucionador informático que se base en técnicas lógicas en lugar de la fuerza bruta, pero ahora hay cargas y cargas de tales solucionadores, y al menos para las técnicas no muy complejas, no son tan difíciles codificar.

Por supuesto, en un rompecabezas simple que se puede resolver solo con solteros desnudos y ocultos, la cantidad de solteros desnudos / ocultos disponibles en cada paso es importante y generalmente afectará la velocidad de resolución de la mayoría de los solucionadores.

Además, los diferentes solucionadores pueden tener diferentes técnicas que encuentran más fáciles o más difíciles de usar; para un solucionador humano también hay algo de suerte / variación, ya que no hay forma de ver posibilidades en todo el tablero al mismo tiempo.

El número de donaciones no es tan importante para determinar la dificultad de un Sudoku.

Una buena referencia es http://diuf.unifr.ch/people/juil… .

Este es un problema general en los rompecabezas lógicos (a lápiz) hechos por computadoras para ser resueltos por humanos. Si se utiliza un solucionador de fuerza bruta, puede crear fácilmente un rompecabezas que es casi imposible de resolver para un humano, pero no notablemente más difícil que un simple rompecabezas para la computadora.

Un solucionador que usa reglas lógicas a menudo puede ser igual de rápido, pero es más difícil de implementar y puede quedar atascado en ciertos acertijos especialmente difíciles. Esos acertijos son los que requieren prueba y error, y generalmente también son los más difíciles para los solucionadores humanos.

En Krazydad, uso un programa de computadora que intenta imitar las estrategias que un humano usaría para resolver el rompecabezas. Este solucionador también se utiliza para determinar la cuadrícula de sugerencias, que indica el orden de resolución.

http://krazydad.com/sudoku/

La dificultad del rompecabezas está determinada por

a) El número de pases que toma el solucionador de software para resolver el rompecabezas.

b) Los tipos particulares de estrategias que se requieren para resolver el rompecabezas.

c) Cuando, en el proceso de resolución, se requieren las estrategias más difíciles: en los rompecabezas más difíciles, tienden a surgir antes, mientras que en los rompecabezas más fáciles, solo puede encontrar dificultades en los últimos cuadrados, que se pueden determinar fácilmente a través de la prueba y error.