Come posso risolvere il puzzle di legno di Log Pile con un programma per computer?

Question

Qualcuno può suggerire come risolvere il puzzle di legno di Log Pile utilizzando un programma per computer?

Vedi qui per visualizzare il puzzle: http://www.puzzlethis.co.uk/products/madcow/the_log_pile.htm

l'immagine mostra solo alcuni dei pezzi. Il set completo di 10 pezzi è configurato come segue con 1 che rappresenta un piolo, -1 che rappresenta un foro e 0 che non rappresenta né un piolo né un foro.
-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

I pezzi possono essere interbloccati in due strati di 5 pezzi ciascuno con lo strato superiore a 90 gradi rispetto allo strato inferiore come mostrato nel link sopra.

Ho già creato una soluzione a questo problema utilizzando Java ma ritengo che sia stata una soluzione maldestra e sono interessato a vedere alcune soluzioni più sofisticate. Sentiti libero di suggerire un approccio generale o di fornire un programma di lavoro nella lingua che preferisci.

Il mio approccio era usare la notazione numerica sopra per creare un array di "Log". Ho quindi utilizzato un generatore di combinazione/permutazione per provare tutte le possibili disposizioni dei registri fino a quando non è stata trovata una soluzione in cui tutte le intersezioni erano pari a zero (ad esempio da Peg a foro, da foro a peg o da vuoto a vuoto). Ho usato alcuni speed-up per rilevare la prima intersezione fallita per una data permutazione e passare alla permutazione successiva.

Spero che tu abbia trovato questo interessante come me.

Grazie, Craig.

Answer 1

Seguendo i consigli da Jay Elston, vorrei attuarlo utilizzando il seguente pseudocodice:

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 

Dove il "ruotato pezzi" sarebbe, per un determinato strato di base, i pezzi ideali si avrebbe bisogno di coprilo. Calcolando questi pezzi e abbinandoli ai pezzi del livello superiore, è possibile utilizzare un ordinamento O (N log N) per abbinare i pezzi ruotati al livello superiore reale invece di corrispondere a tutti N! possibili disposizioni dello strato superiore. Inoltre, al primo non-match, puoi uscire presto.

La chiave per scrivere algoritmi efficienti è di ridurre la ricerca il prima possibile e di sfruttare eventuali simmetrie. Ad esempio, puoi ridurre della metà il tempo di esecuzione se pensi che il puzzle sia simmetrico, e quindi assegni arbitrariamente un pezzo al livello inferiore: avrai quindi solo 9 strati su 4 di base da esplorare.

Answer 2

Prolog è popolare per problemi di questo tipo. Ho impostato alcuni simpler puzzle problems che hanno soluzioni relativamente buone in Prolog.

Esistono modi molto eleganti per risolvere questo tipo di problemi in Haskell, utilizzando le funzioni e il backtracking. Un mio amico ha risolto un enigmatico puzzle fisico — Puzzling Pets — in poco più di 200 righe, di Haskell, comprese le descrizioni di tutti i pezzi e di tutto. A   buon modo per apprendere le tecniche pertinenti sarebbe leggere il documento di John Hughes Why Functional Programming Matters, installare Haskell Platform e provare la tua mano.

Answer 3

Questo problema sembra essere un modulo di Boolean satisfiability problem. Se lo è, l'approccio più noto è la forza bruta.

Ma ci sono alcune simmetrie e alcune proprietà del problema che possono consentire di ridurre il numero di soluzioni da provare.Per esempio -

• Se si divide i registri in due 5 pezzi sottoinsiemi parte superiore e inferiore, il # pioli in TOP deve essere uguale a # fori sul fondo, ed i fori # in esigenze TOP per abbinare i # pioli in BOTTOM, e gli # appartamenti in TOP hanno bisogno di per corrispondere ai # appartamenti in BOTTOM. Se i # pioli e i # buchi coincidono, allora anche i # appartamenti corrispondono, quindi non è necessario controllare gli appartamenti # .
• Ci sono 10 * 9 * 8 * 7 * 6 modi in cui è possibile suddividere i registri in due sottoinsiemi da 5 pezzi . (Una volta che avete scelto i primi 5 registri per sottoinsieme TOP, i registri rimanenti sono in sottoinsieme INFERIORE.
• Quando si prova un 5 pezzi sottoinsieme, ci sono 5 * 8 * 6 * 4 * 2 modi per organizzare uno strato di registri, ovvero dopo aver selezionato il registro 1, ci sono 4 registri rimanenti. Per il secondo registro, è possibile scegliere tra quattro e ci sono in due modi che possono essere orientati con rispetto al primo registro
• Una volta che hai un livello base, puoi provare ad adattare ogni registro dall'altro livello uno alla volta, finché non ne trovi uno che non va bene. A quel punto, rinuncia alla disposizione attuale del registro di livello di base e prova il prossimo:

Answer 4

Ho una soluzione (disordinata!) In javascript, ma ho avuto difficoltà a pubblicarlo. L'algoritmo di base utilizzato è: Trova tutte le iterazioni di 5 registri dal totale di 10 registri e ogni set di 5 registri crea ogni iterazione possibile con i registri invertiti. Per ciascuno di questi stati, sapremo quale modello di log dovrà essere posizionato sopra. Quindi, determiniamo se i rimanenti 5 registri possono essere posizionati in cima.

che porta a questa rappresentazione di una soluzione:

(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