modo più efficace per calcolare una serie di mosse in Peg Solitaire

Question

Dato un peg solitaire configurazione della scheda arbitraria, qual è il modo più efficiente per calcolare qualsiasi serie di mosse che si traduce in posizione di "fine del gioco".

Per esempio, la posizione di partenza standard è:

..***..
..***..
*******
***O***
*******
..***..
..***..

E la posizione "fine del gioco" è:

..OOO..
..OOO..
OOOOOOO
OOO*OOO
OOOOOOO
..OOO..
..OOO..

Peg solitare è descritto in dettaglio qui: Wikipedia , stiamo considerando la "inglese bordo" variante.

Sono abbastanza sicuro che sia possibile risolvere qualsiasi pensione a partire in pochi secconds su un computer ragionevole, diciamo un P4 3GHz.

Al momento questo è il mio migliore strategia:

def solve:
    for every possible move:
        make the move.
        if we haven't seen a rotation or flip of this board before:
            solve()
            if solved: return
        undo the move.

Answer 1

L'articolo di Wikipedia si collega a già menziona il fatto che là solo 3.626.632 posizioni possibili da tavolo, quindi è facile per qualsiasi computer moderno di fare una ricerca esaustiva dello spazio.

Il vostro algoritmo di cui sopra è giusto, il trucco sta attuando il "non hanno visto una rotazione o medaglia di questa scheda prima di", che si può fare utilizzando una tabella di hash. Probabilmente non c'è bisogno della linea "annullare lo spostamento" come una reale attuazione sarebbe passata allo stato di bordo come argomento per la chiamata ricorsiva in modo si può usare lo stack per la memorizzazione dello stato.

Inoltre, non è chiaro quello che si potrebbe dire con "efficiente".

Se si desidera trovare tutte le sequenze di mosse che portano ad una fase vincente allora avete bisogno di fare la ricerca esaustiva.

Se si vuole trovare la sequenza più breve allora si potrebbe utilizzare un algoritmo branch-and-bound di tagliare alcuni alberi di ricerca nella fase iniziale. Se si riesce a trovare una buona euristica statica allora si potrebbe provare A * o una delle sue varianti.

Answer 2

Avvia dallo stato completato, e indietro a piedi nel tempo. Ogni mossa è un salto che le foglie di un piolo aggiuntiva sulla scheda.

In ogni momento, ci possono essere più unmoves si può fare, così potrete essere generando un albero di mosse. Attraversare l'albero (o DF o breadth-) arrestare qualsiasi ramo quando si raggiunge lo stato di partenza o non ha più mosse possibili. Uscita l'elenco dei percorsi che hanno portato allo stato di partenza originale.