¿Cómo puedo resolver el rompecabezas de madera Log Pile con un programa de computadora?

Question

¿Alguien puede sugerir cómo resolver el rompecabezas de madera Log Pile usando un programa de computadora?

Ver aquí para visualizar el rompecabezas: http://www.puzzlethis.co.uk/products/madcow/the_log_pile.htm

La imagen sólo muestra algunas de las piezas. El conjunto completo de 10 piezas está configurado de la siguiente manera: 1 representa una clavija, -1 representa un agujero y 0 representa ni una clavija ni un agujero.
-1,1,0, -1,0
1,0,1,0,0
1, -1,1,0,0
-1, -1,0,0, -1
-1,1,0,1,0
0,1,0,0,1
1,0, -1,0, -1
0, -1,0,1,0
0,0, -1,1, -1
1,0, -1,0,0

Las piezas se pueden enclavar en dos capas de 5 piezas cada una con la capa superior a 90 grados en la capa inferior como se muestra en el enlace de arriba.

Ya he creado una solución a este problema utilizando Java, pero creo que fue una solución torpe y estoy interesado en ver algunas soluciones más sofisticadas. Siéntase libre de sugerir un enfoque general o de proporcionar un programa de trabajo en el idioma de su elección.

Mi enfoque era utilizar la notación numérica anterior para crear una matriz de "Registros". Luego utilicé un generador de combinación/permutación para probar todas las disposiciones posibles de los registros hasta que se encontró una solución donde todas las intersecciones equivalían a cero (es decir, Peg a Hoyo, Hoyo a Peg o Blanco a Blanco). Usé algunas aceleraciones para detectar la primera intersección fallida para una permutación dada y pasar a la siguiente permutación.

Espero que esto te parezca tan interesante como yo.

Gracias, Craig.

Answer 1

Siguiendo el consejo de Jay Elston, me gustaría ponerlo en práctica utilizando el siguiente pseudocódigo:

Read in the pieces 
Annotate each piece with its number of pegs and holes 
Generate all possible base layers (10 over 5 = 252, selecting 5 from the set), 
    so that sum(above, pegs) == sum(below, holes) and sum(below, pegs) == sum(above, holes) 
    For each base layer, (5! = 120 of them, permuting the 'below' pieces) 
     compute 'rotated pieces' for the base layer 
     if one-to-one match between top layer and rotated base-layer pieces, 
      report successful solution 

Cuando el "girar piezas" sería, por una capa de base dada, las piezas ideales que necesitarían cubrelo. Al calcular estas piezas y unirlas con las capas superiores, puede usar una clasificación O (N log N) para unir las piezas giradas contra la capa superior real en lugar de hacer coincidir todas las N! posibles arreglos de capa superior. Además, en la primera no coincidencia, puedes rescatar temprano.

La clave para escribir algoritmos eficientes es podar su búsqueda lo antes posible y explotar cualquier simetría. Por ejemplo, puede reducir el tiempo de ejecución a la mitad si considera que el rompecabezas es simétrico y, por lo tanto, asigna arbitrariamente una pieza a la capa inferior: entonces tendrá solo 9 sobre 4 capas base para explorar.

Answer 2

Prolog es popular para problemas de este tipo. Configuré algunos simpler puzzle problems que tienen soluciones relativamente buenas en Prolog.

Hay formas muy elegantes de resolver este tipo de problemas en Haskell, utilizando funciones y retroceso. Un amigo mío resolvió un rompecabezas físico muy molesto — Puzzling Pets — en poco más de 200 líneas, de Haskell, incluyendo descripciones de todas las piezas y todo. Una buena forma de aprender las técnicas relevantes sería leer el documento de John Hughes Why Functional Programming Matters, instalar el Haskell Platform, y probar su mano.

Answer 3

Parece que este problema es una forma del Boolean satisfiability problem. Si lo es, el enfoque más conocido es la fuerza bruta.

Pero hay algunas simetrías y algunas propiedades del problema que pueden permitirle reducir el número de soluciones que debe probar.Por ejemplo -

• Si divide los troncos en dos 5 pieza subconjuntos superior e inferior, el # clavijas en TOP debe coincidir con el # agujeros en el fondo, y el # agujeros en necesidades TOP para que coincida con las # clavijas en ABAJO, y las # llanuras en la parte superior necesita para que coincida con los # pisos en la PARTE INFERIOR. Si coinciden las # clavijas y los agujeros #, entonces los pisos planos también coincidirán, por lo que debe no necesitar verificar los pisos #.
• Hay 10 * 9 * 8 * 7 * 6 formas en que pueden dividir los registros en dos subconjuntos de 5 piezas . (Una vez que tenga recogido los primeros 5 registros de subconjunto TOP, los registros restantes están en subconjunto BOTTOM.
• Cuando se prueba una 5 pieza subconjunto, hay 5 * 8 * 6 * 4 * 2 maneras en que puede arregle una capa de registros. Es decir, después de seleccionar el registro 1, hay 4 registros restantes. Para el segundo registro, puede elegir entre cuatro, y hay dos maneras en que puede orientarse con respecto del primer registro
• Una vez que tenga una capa base, puede intentar ajustar cada registro de la otra capa de a uno por vez, hasta que encuentre uno que no encaje. En ese punto, abandona la disposición de registro de la capa base actual y prueba el siguiente.

Answer 4

Tengo una solución (desordenada) en javascript, pero he tenido problemas para publicarla. El algoritmo básico utilizado es: Encuentra todas las iteraciones de 5 registros del total de 10 registros, y con cada conjunto de 5 registros crea cada iteración posible con registros que se invierten. Para cada uno de estos estados, sabremos qué patrón de registros deberá colocarse en la parte superior. Entonces, determinamos si los 5 registros restantes pueden colocarse en la parte superior.

que nos lleva a esta representación de una solución:

(Bottom, right-> left) 
[0,0,1,-1,1],[-1,-1,0,0,-1],[0,0,1,0,1],[-1,1,0,-1,0],[1,0,-1,0,0] 
(Top, up->down) 
[0,1,0,1,-1],[0,1,0,-1,0],[-1,0,-1,0,1],[1,0,0,1,0],[-1,1,-1,0,0] 


0 - flat 
1 - dowel 
-1 - hole