Algoritmo per creare un puzzle di dilavamento esagonale

Question

Sto creando un puzzle game che, pur giocabile a mano per livelli facili, è pensato per essere risolto dai programmi per computer per quelli più difficili. Il puzzle è un riempimento di piena su una tavola esagonale. Puoi provare un prototipo here.

alt text http://www.hacker.org/flood/screen.png

Ecco come funziona il puzzle: scegliendo un colore dalla parte superiore, si esegue un riempimento a partire dalla piastrella in alto a sinistra. Questo progressivamente converte la tavola in un colore solido. La sfida è fare questo in un certo numero di mosse.

Ho creato diversi puzzle simili a questo, e la chiave è usare un algoritmo che genera schede difficili da risolvere senza sapere come sono state create. Per esempio, qui potremmo produrre una tavola invertendo il riempimento di piena: lavorando all'indietro da una tavola piena fino a quando non è stato rilasciato. Sappiamo quanti passaggi ha richiesto e possiamo impostarlo come limite inferiore per una soluzione.

Il problema che sto affrontando è che quando provo questo approccio, il mio limite superiore è troppo alto. Diventa banale risolvere il puzzle all'interno di questo numero di mosse, anche spostandosi casualmente.

Un approccio che non è una soluzione sta generando una scheda casuale e quindi risolvendolo in modo ottimale e impostandolo come obiettivo. Il punto è creare un puzzle dove risolverlo in modo ottimale è NP time o almeno un hard P.

Quindi quello che sto cercando è un algoritmo in grado di generare schede estremamente difficili dove risolverli, man mano che diventano più grandi, diventa una seria sfida.

Answer 1

Quando si esegue la crittografia RSA, non troviamo i numeri primi, selezioniamo numeri casuali e quindi applichiamo test che ci danno probabilità sempre maggiori di numero primo, senza mai provarlo.

Suggerisco lo stesso. Cerca di trovare le condizioni che danno una buona probabilità che il puzzle abbia le proprietà desiderate e che provino per quelle. Oppure potresti usare algoritmi genetici/reti neurali e addestrarli a riconoscere i puzzle "buoni", che equivale alla stessa cosa.

Answer 2

Proverei a dimostrare che è NP-completo o in P, per avere un'idea delle configurazioni che sono difficili.

Estrarre anche gli esagoni e utilizzare una rappresentazione come grafico.

Answer 3

Ho giocato molto al puzzle di alluvione rettangolare (http://labpixies.com/gadget_page.php?id=10). Eccitato per vedere una versione Hex! Penso che trovare un gioco duro sia facile come: evitare che blocchi grandi dello stesso colore compaiano nel puzzle. Almeno nei casi rettangolari che ho visto, quasi tutti i puzzle che possono essere risolti in un piccolo numero di passaggi hanno grandi blocchi di colore.

P.S. Penso che il tuo "limite inferiore" non sia valido. Quando si lavora in avanti, se viene utilizzata una buona strategia, è possibile terminare in pochi passaggi. Il "limite inferiore" è in realtà un limite superiore per la soluzione ottimale.