Resolver rompecabezas de Kakuro

Aquí es una buena para reflexionar sobre: Resolver rompecabezas de Kakuro

http://en.wikipedia.org/wiki/Kakuro

Estoy intentando hacer un programa de solución para este juego. El papeleo está hecho (leyendo un archivo inicial con un número variable de columnas y filas. Se supone que el archivo de entrada sigue las reglas del juego para que el juego siempre se pueda resolver. Tómate tu tiempo para leer las reglas del juego.

I 've cuidado de la estructura de datos que creo que se adapte mejor:

struct aSquare { int verticalSum; int horizontalSum; int value; }

e hizo una 'matriz' de éstos de forma dinámica para trabajar en lo hice para que los cuadrados negros tienen un valor de -1 y. los cuadrados blancos (los cuadrados de la solución real) se inicializan a 0. También puede obtener la posición de cada estructura aSquare desde el conjunto fácilmente, sin necesidad de crear campos de estructura adicionales para él.

Ahora el algoritmo ... Cómo en el mundo voy a conciliar todas estas sumas y encontrar una manera general que resolverá todos los tipos de grillas. He estado luchando con esto toda la tarde en vano.

Se aprecia la ayuda, ¡diviértase!

* EDIT: Me acabo de dar cuenta de que el enlace real que publiqué tiene algunos consejos con respecto a las técnicas de resolución. Todavía voy a mantener esto para ver qué se le ocurre a la gente.

Fuente

2010-10-29 Qosmo

Un simple solucionador de fuerza bruta para Sudoku toma milisegundos para funcionar, por lo que no tiene que preocuparse de implementar cualquier tácticas especiales. Creo que en el caso de Kakuro esto será lo mismo. Un algoritmo simple:

def solve(kakuro): 
    if kakuro has no empty fields: 
     print kakuro 
     stop. 
    else: 
     position = pick a position 
     values = [calculate possible legal values for that field] 
     for value in values: 
      kakuro[position] = value 
      solve(kakuro) 
     kakuro[position] = None # unset after trying all possibilities

Este algoritmo podría funcionar mejor si encuentra el mejor orden de campos para llenar. Intente elegir los campos que serán los más restringidos (como en: no hay muchos valores que sean legales).

De todos modos, este será probablemente el más simple de implementar, así que pruébalo y busca solucionadores más sofisticados solo si este no funciona. (En realidad, este es uno de los solucionadores de programación de restricciones más simples, los solucionadores de CP reales son mucho más complicados, por supuesto).

Fuente

2010-10-29 20:28:12 liori

Tenga en cuenta que hay mucho espacio para la astucia en el paso "[calcular posibles valores legales para ese campo]". – Brian

@Brian: más para elegir una posición, como en muchos algoritmos esto podría significar pasar de un tiempo polinomial a uno exponencial. Kakoru es NP-completo, pero aún elegir el orden sabiamente podría hacer las constantes mucho más pequeñas. Y calcular los posibles valores legales debe ser un tiempo constante con estructuras de datos adecuadas, de todos modos. – liori

Bastante justo.En un solucionador que diseñé (para un rompecabezas diferente), un truco que utilicé fue escoger ** cada ** posición y probarlo para una iteración, usando pruebas por contradicción para reducir la cantidad de posibles valores legales. También completé todos los espacios que tenían solo un posible valor legal. Por lo tanto, mi rompecabezas tenía una función de facto '[calcular posibles valores legales para cada campo]'. Mi selector de posición para hacer conjeturas no tenía inteligencia en absoluto, y realmente no la necesitaba. Para ser justos, Nurikabe es un rompecabezas binario, por lo que todas las posiciones están igualmente restringidas. – Brian

Este es un álgebra lineal directa, utilice técnicas de manipulación de vector/matriz para resolver.

[editar - respondiendo a los comentarios]

a + b + 0 + d + 0 = n1 
0 + b + c + 0 + e = n2 
a + 0 + c + 0 + 0 = n3 
a + b + c + 0 + e = n4 
a + 0 + c + d + 0 = n5

Por encima se convierte en una matriz, y sumando y restando múltiplos de las filas, que terminan con:

a 0 0 0 0 na 
0 b 0 0 0 nb 
0 0 c 0 0 nc 
0 0 0 d 0 nd 
0 0 0 0 e ne

No combinatoria, todos permanecen enteros.

Fuente

2010-10-29 20:27:28 slashmais

Al usar álgebra lineal, normalmente no terminará con una solución entera. Combinatorics necesita entrar de alguna manera. –

El álgebra lineal no puede representar la regla de la duplicación sin dígitos. – liori

En su ejemplo, hay un orden de eliminación donde la solución es entera, pero encontrar ese orden para una matriz general 0-1 no es fácil. Intenta llevar a cabo la eliminación gaussiana en el orden que presentas, encontrarás que 1/2 se arrastra. En este caso, es fácil encontrar un buen orden (un ejemplo es a, b, d, c, e), pero en En general, necesitaría poder retroceder en la GE en caso de que un elemento de matriz posterior resulte ser fraccionario debido a una decisión anterior. –

Si su interés está en última instancia en hacer una solución de software para estos juegos, pero no entrar en los detalles algorítmicos, le recomiendo usar un motor de Programación de Restricciones (CP). CP es un paradigma de programación declarativa que se adapta muy bien a este tipo de problemas. Varios motores comerciales y de código abierto CP están disponibles.

http://en.wikipedia.org/wiki/Constraint_programming

Fuente

2010-10-29 20:27:33

En realidad es solo este juego en este momento. En realidad, estaba tratando de hacer algo más complejo para mí. Gracias por la sugerencia, aunque – Qosmo

yo supongo que Linear Programming se puede utilizar fácilmente para resolver este tipo de juego .. entonces este es un problema de número entero para el que las soluciones exactas sí existe .. (sucursal y obligado? de corte plano?)

En cualquier caso, el uso de una tabla con las más ciertas combinaciones serán de utilidad para asegurarse (por ejemplo http://www.enigmoteka.com/Kakuro%20Cheatsheet.pdf)

Fuente

2010-10-29 20:34:07 Jack

+1 para la tabla de prueba/tabla. – LarsH

he encontrado algunos buenos trucos de manipulación de bits que aceleran la resolución de Kakuro. Puede recoger la fuente here.

Fuente

2010-10-29 20:45:57 zvrba

En cuanto a la Programación de Restricción: Aquí hay algunas implementaciones diferentes de cómo resolver un acertijo Kakuro con Programación de Restricciones (todas usan el mismo principio básico). La instancia del problema está arreglada en el programa.

Google o-herramientas/Python: http://www.hakank.org/google_or_tools/kakuro.py
Comet: http://www.hakank.org/comet/kakuro.co
MiniZinc: http://www.hakank.org/minizinc/kakuro.mzn
SICStus: http://www.hakank.org/sicstus/kakuro.pl
Eclipse: http://www.hakank.org/eclipse/kakuro.ecl
Gecode: http://www.hakank.org/gecode/kakuro.cpp
Google or- herramientas/C#: http://hakank.org/google_or_tools/kakuro.cs
respuesta Programación Set: http://hakank.org/asp/kakuro.lp

Editar: Agregado de Google o-herramientas/C# y respuesta fije la programación.

Fuente

2010-10-30 08:37:58 hakank

Enlaces útiles, gracias! – Qosmo

Respuesta

Cuestiones relacionadas