¿Qué estructura de datos sería mejor almacenar y resolver un rompecabezas ken-ken?

Answer 1

Después de pasar menos de 15 segundos mirando el rompecabezas, parece que retroceder optimizado para explorar opciones más probables de ser victoriosas lo haría primero.

Para que el algoritmo elija primero la dirección de búsqueda más prometedora, usaría una variación de un algoritmo X: mantener un montón de listas de qué dígito (¿es un dígito o un número? No importa) se ajusta a qué celdas, y primero iterando sobre las celdas donde el número de opciones es el más pequeño; idealmente uno.

En otras palabras:

• una estructura de datos por celda, para contener la lista de las opciones que aún se ajustan a esta celda,
• una estructura de datos para todas las celdas, para permitir dibujar rápidamente la siguiente celda a considerar, que tiene la menor cantidad posible de opciones,
• y un algoritmo para mantener incrementalmente sincronizados los dos anteriores, a medida que la búsqueda sube y baja (considerando y sin considerar cierta opción).

También estoy seguro de que una solución DP puede funcionar. Sin embargo, probablemente sería la mejor opción para tableros “largos” (ej. 8 * N, donde N es grande); para tableros pequeños, el DFS con las estructuras de datos descritas anteriormente debería estar bien.

Answer 2

Almacenaría un rompecabezas simplemente como una secuencia de restricciones, donde cada restricción es una secuencia de coordenadas de celda, la operación y el resultado.

Resolvería un rompecabezas convirtiéndolo en una fórmula SAT y luego ejecutando un solucionador SAT existente en él. La vida es demasiado corta para escribir y optimizar nuestras propias pistas back