Newsgroup: it.scienza.informatica
Titolo: Problema su alberi di ricerca nel gioco del solitario

Ciao a tutti,
ho già scritto sul forum di matematica. Spero che se non mi rispondano
lì
lo facciate voi.
Sto cercando una stima al limite massimo di figli che un nodo può
avere nel gioco del solitario.
Tale gioco è semplicissimo. Si gioca su di una scacchiera n x n. Si
posizionano
a caso un certo numero di pedine. Lo scopo del gioco è rimanere con
una
sola pedina. Le mosse sono: salto orizzontale o verticale. In pratica,
si "mangia" una pedina con un altra pedina, finendo quindi per
eliminare
una pedina dalla scacchiera. Se per esempio ho la seguente
configurazione:
. . . .
. o . .
. o . .
. . . .
si effettua una mossa verticale e si ottiene
. . . .
. . . .
. . . .
. o . .
oppure equivalentemente
. o . .
. . . .
. . . .
. . . .
e il gioco è risolto, perchè la configurazione di arrivo ha una sola
pedina.
Ovviamente, un buco può contenere una sola pedina, così come una
pedina
può saltare soltanto una casella in orizzontale o verticale (come già
detto).
Allora, ciò che mi serve è arrivare a conoscere un limite superiore
realistico
per il max numero di mosse che posso effettuare data una
configurazione su
di una scacchiera n x n. Per esempio, data la configurazione:
. . . .
. o . .
. o o .
. . . .
si calcola facilmente che, inizialmente, posso effettuare al più 4
mosse.
Sono arrivato al limite 4n^2 (infatti, se gioco su di una scacchiera n
x n,
ho n^2 pedine;se ipotizzo che ogni pedina può mangiare altre 4 pedine,
cioè
il massimo consentito, ho 4n^2 possibili mosse). 
Ma questo limite è mostruosamente per eccesso.
Per esempio, se ho 4 pedine posso al più fare 8 mosse, se ne ho 5 sono
ancora 8, se ne ho 6 dovrebbero essere al più 10, con 7 pedine le
mosse possibili dovrebbero essere al massimo 12 e così via.
Questo è evidentemente roba per matematici, ma anche gli informatici
dovrebbero essere in grado di farcela (io non ce l'ho ancora fatta :(,
quindi mi appiglio alla vostra clemenza: aiut!!!!
Grazie e ciao.
PS:
x chi ha letto il post sul dubbio sulla funzione di minimizzazione, è
tutto
collegato...miiii quanto sono misterioso...se qualcuno è interessato,
quella
funzione mi serviva per ricercare una soluzione in modo efficiente
(quando
c'è)...posso essere più chiaro se volete...ciao
PSS:
il mex che ho scritto sul forum di mat contiene una cafonata: pensavo,
mentre
scrivevo, che il numero max di figli doveva essere legato in modo
lineare
al numero di pedine, ma ora mi sembra chiaro che non è così, visto che
se
riempio la scacchiera n x n con n^2 pedine non posso effettuare
nessuna
mossa...miiii è meglio che vado a dormire.... ;)
PSSS:
ora che ci penso, mi sembra quasi di vedere una funzione di tipo
gaussiana
da qualche parte...uhm...anzi, a pensarci bene, il fattore di
branching
dovrebbe essere più alto quando si è intorno a n^2 mezzi
pedine...forse
si dovrebbe ragionare su una scacchiera di dimensioni infinite con n^2
pedine
posizionate su di essa...così si evita di considerare il fatto che le
pedine sui bordi non possono muoversi oltre i confini della
scacchiera..magari
facilita le cose...mah

 di una scacchiera n x n.
Secondo me ti stai complicando la vita:
Considera questa cosa: ad ogni mossa, il numero di pedine diminuisce di 
1, quindi se sulla scacchiera hai 10 pedine, non capisco come fai a 
poter fare piů di 10 mosse...
nel tuo primo esempio infatti hai 3 pedine ed esegui 3 mosse prima di 
risolvere il gioco.
O forse non ho capito io cosa cerchi e devi spiegarti meglio
ciao
Peppe