Algoritmo di risoluzione Tetravex

Question

Bene, stavo pensando di creare un programma di risoluzione Tetravex per esercitare le mie capacità di scrittura del codice (il linguaggio sarà propostamente Visual Basic) e ho bisogno di aiuto per trovare un algoritmo per risolverlo. Per coloro che non sanno cosa sia il tetravex, vedi questo http://en.wikipedia.org/wiki/TetraVex. L'unico algoritmo che posso inventare è il metodo della forza bruta, posizionare una tessera a caso in un angolo e provare ogni possibile piastrella accanto ad essa e continuare lo stesso processo, se raggiunge un vicolo cieco torna a uno stato precedente e posiziona un altro piastrella. Quindi qualcuno può trovare un algoritmo migliore? Grazie per il tuo tempo.

Answer 1

qui alcune idee.

Un algoritmo di forza bruta vaniglia tenta di riempire la griglia in modo ricorsivo enumerando le posizioni della griglia in un ordine fisso (ad esempio riga maggiore) e cercando sempre di adattare ogni possibile pezzo nella posizione corrente e quindi ricorsivamente. Questo è quello che hai citato ed è molto inefficiente.

Un miglioramento è contare sempre per ogni posizione libera il numero di pezzi che si adattano lì, e poi recurse sulla posizione che ha almeno adatta; se uno ha zero pezzi, torna subito indietro; se ce n'è uno in cui solo un pezzo si adatta al riempimento e continua (nessun ramo creato); altrimenti seleziona quello che ha meno pezzi (≥ 2) e continua da lì.

Una volta impostato questo algoritmo, la prossima domanda è come si può più sfoltire lo spazio di ricerca. Se hai, per esempio, un pezzo con "1" nella prima posizione e B pezzi con "1" nella posizione inferiore, e A> B, allora sai che almeno A - B della "1 in posizione alta" pezzi deve essere effettivamente posizionato nella riga superiore, quindi è possibile escluderli da qualsiasi altra posizione. Questo aiuta a ridurre il fattore di ramificazione e ad individuare i vicoli ciechi in precedenza.

Si dovrebbe anche verificare ad ogni passaggio di ricorsione che ogni pezzo ha almeno un punto in cui si adatta (eseguire questo controllo dopo aver verificato che non ci sia pezzo che si adatti solo a un punto per la velocità). Se c'è un pezzo che non si adatta a nessuna parte, è necessario tornare immediatamente indietro. È possibile estendere questo controllo per verificare che ogni coppia di pezzi si adatti a per una capacità di controllo dead-lock potenzialmente migliore.

Esiste anche una strategia chiamata "backtracking non cronologico" o "backjumping" che ha origine dalla ricerca nella risoluzione SAT. Questo ti aiuta a tornare indietro di più di un livello alla volta quando raggiungi un punto morto; se vuoi, puoi cercare su Google questi termini per trovare altro, ma devi fare del lavoro mentale per mappare il concetto nel tuo spazio problematico.

Answer 2

Un primo miglioramento consisterebbe nel contare quante coppie di numeri corrispondenti ci sono, e se, diciamo, ci sono 5 "1" in cima ai quadrati, ma solo 4 in basso, quindi ci deve essere un "1" che punta fuori dalla parte superiore della griglia.

Answer 3

In ogni scheda in parte risolto vorrei

• cercare un posto in cui nessuna delle tessere rimanenti potrebbe essere svolto. Se trovato, il tabellone deve essere svolto nell'ultimo posto in cui una tessera è stata giocata in modo casuale.

• Cerca un luogo in cui solo 1 delle tessere rimanenti può essere riprodotto legalmente. Se trovato, posiziona quella tessera.

• Posizionare una tessera in modo casuale nel punto del tabellone in cui è possibile legalmente riprodurre il numero di tessere rimanenti in numero minore di. Ricorda questo schema di bordo prima del Io poso la tessera, potrei voler tornare a questa tavola e giocare una tessera diversa.

In pseudocodice sarebbe

top: 
    evaluate # of tiles that match at each empty square 
    if any square has 0 matches, unwind to <prev> 
    if any square has 1 match, lay tile, goto top 
    save current board as <prev> 
    play randomly at square with minimum number of matches, goto top 

Come un'ottimizzazione, è possibile ignorare le piazze che valutano che non vengano a contatto piazze che hanno piastrelle, dal momento che permetterà sempre tutte le tessere rimanenti.

Answer 4

Sembra che Tetravex sia un Constraint Satisfaction Problem, quindi si desidera limitare le opzioni il più rapidamente possibile. Dovrebbe essere possibile fare meglio del posizionamento casuale. Che ne dici ?:

• Creare collegamenti tra tutte le facce delle tessere con le possibili corrispondenze.
• Qualsiasi tessera con una faccia scollegata deve essere una tessera bordo.
• Qualsiasi tessera con due facce scollegate adiacenti deve essere una tessera d'angolo.
• I riquadri centrali devono avere quattro collegamenti attivi.
• Ora, posiziona una tessera in un percorso valido e invalida i collegamenti utilizzati. Se una tessera non posizionata contiene tre facce non collegate o facce scollegate su lati opposti, la mossa non è valida e puoi tornare indietro.
• Dovresti essere in grado di utilizzare i collegamenti faccia a faccia per cercare la successiva piastrella possibile rispetto alla ricerca di tutte le tessere. Se non ce n'è uno, torna indietro.

Answer 5

Ho scritto un risolutore per Tetravex e ho utilizzato un approccio diverso e mi sembra molto efficiente. Ho creato possibili relazioni valide aumentando le dimensioni. Quindi ogni iterazione mi dà pezzi di puzzle più grandi con cui lavorare riducendo il numero di pezzi di puzzle, per così dire.

Inizio a creare un elenco di tutte le connessioni possibili tra le tessere dal basso verso l'alto e un elenco di tutte le possibili connessioni tra le tessere da destra a sinistra.

Da questi due elenchi, creo un elenco di tutte le possibili combinazioni 2x2 valide.

Utilizzando l'elenco 2x2, creo un elenco di tutte le possibili combinazioni 3x3 valide.

Da lì posso andare in 4x4 utilizzando le liste 2x2 e 3x3, oppure fare 5x5 semplicemente usando la lista 3x3.

In questo momento il mio codice esegue ciascuna iterazione separatamente, ma dovrebbe essere in grado di essere ripulito per gestire ogni iterazione con lo stesso codice che consentirebbe griglie di dimensioni maggiori.

---

Anche questa sembra una situazione fantastica per l'utilizzo di una rete neurale, e potrei provare una prossima volta.