Newsgroup: it.hobby.enigmi
Titolo: Curiosita' su Torre di Hanoi

Visto che qui tutti conoscono il rompicapo in oggetto, avrei una 
curiosita'. Sto scrivendo un programmino che risolve da solo una torre a n 
pioli (dire banale e' dire poco), ma vorrei insegnargli (quindi prima devo 
sapere io come si fa) a riconoscere se da una combinazione arbitraria 
(chiamando 'combinazione' una disposizione dei dischi sui pioli) e' 
possibile risolvere il gioco.
Ad esempio, con 3 dischi, ho le seguenti combinazioni (corrispondenti alle 
mosse):
<123,,> Partenza
<23,,1> Mossa 1
<3,2,1> Mossa 2
<3,12,> Mossa 3
<,12,3> Mossa 4
<1,2,3> Mossa 5
<1,,23> Mossa 6
<,,123> Mossa 7 (successo)
L'idea e' che il programma capisca se da una combinazione data si puo' 
raggiungere la soluzione. In questo caso, la combinazione <3,1,2> non porta 
a niente, mentre <,12,3> porta alla soluzione in 3 mosse. La soluzione piu' 
banale sarebbe far scorrere al programma tutta la sequenza delle mosse, 
fino a trovare la combinazione data, ma vorrei fare una cosa un po' meno 
becera. Qualcuno ha idee/suggerimenti in proposito?
Bye by SixaM 8-]

 porta a niente, mentre <,12,3> porta alla soluzione in 3 mosse. 
Qui è il tuo sbaglio: nel problema i tre pioli sono equivalenti quindi 
la tripla <3,1,2> è esattamente uguale a <1,2,3>, <2,1,3>, e così via.
E quindi puoi tranquillamente farla rientrare tra le 'possibili' della 
tua lista.
bye!
-- 
Fabrizio "Hermooz" Ermini


Pero' davanti ad una tripla non so ancora come muovermi 8-(
Se uso un approccio 'a forza bruta', devo definire qual'e' il piolo di 
partenza, quello di transito e quello di arrivo, per generare le varie 
mosse (e relative combinazioni) ed in questo modo alcune triple non 
c'entrano...nell'esempio che hai fatto, se la posizione 1 identifica il 
piolo di partenza, la posizione 2 quello di transito e la posizione 3 
quello di arrivo, in un gioco 'ottimale' la prima mossa mi portera' da 
<123,,> a <23,,1>. Se mi trovo davanti a <23,1,>, potrei fare l'ipotesi che 
il piolo di transito e quello di arrivo non sono nelle posizioni che avevo 
pensato. Sono d'accordo che le tre combinazioni che hai riportato portano 
ad una soluzione in due mosse, ma i pioli di arrivo/partenza/transito sono 
diversi.
Bye by Massimo 8-]

 c'entrano...
Non rimanere bloccato dalle assunzioni e soprattutto dalle notazioni: 
OGNUNO dei tre pioli può fare da partenza, da transito e da arrivo, a 
seconda della combinazione di partenza.
Il programma deve essere in grado di identificare qual'e' il piolo da 
assegnare ad ognuno dei tre 'ruoli'.
-- 
Fabrizio "Hermooz" Ermini

 Qualcuno ha idee/suggerimenti in  proposito?
Come gia' detto da Hermooz, da una posizione legale (ciascun disco ha sopra 
di se' un disco di diametro inferiore) e' sempre possibile raggiungere la 
soluzione.
Ecco qualche altra condiderazione.
Da una posizione intermedia l'unico errore possibile e' quello di muovere 
sul piolo sbagliato. Per evitare questo errore, basta immaginare i dischi 
colorati alternativamente bianco e nero, allora 2 dischi dello stesso 
colore non devono mai entrare in contatto.
C'e' anche un modo per sapere come saranno distribuiti gli n dischi sui 3 
pioli alla k-esima mossa.
Eticchettiamo i pioli da sinistra  in ternario: 0, 1, 2.
Zero e' il piolo dove sono impilati i dischi all'inizio del gioco.
Faccio un esempio pratico, si inizia con 7 dischi (numerati da 1 a 7 
partendo dal piu' piccolo) si vuol conoscere la loro posizione alla 13 
esima mossa.
Si espande k come somma binaria, nel nostro caso 13= 1+4+8.
Se n e' pari:
si sostituisce  l'1 col numero ternario      1
si sostituisce il 2 col numero ternario     21
si sostituisce il 4 col numero ternario    122
si sostituisce  l'8 col numero ternario   2111
               il 16                      12222
               1l 32                     211111
...... e via di seguito.
Se n e' dispari:
si sostituisce  l'1 col numero ternario      2
si sostituisce il 2 col numero ternario     12
si sostituisce il 4 col numero ternario    211
si sostituisce  l'8 col numero ternario   1222
               il 16                      21111
               1l 32                     122222
...... e via di seguito.
Nel nostro caso n=7 e' dispari, abbiamo 2+211+1222 questa deve essere una 
somma ternaria Nim, cioe' senza riporto il risultato sara' = 0001102
Leggendo da destra:
Il disco 1 sara' sul piolo 2
Il disco 2 sara' sul piolo 0
Il disco 3 sara' sul piolo 1
Il disco 4 sara' sul piolo 1
Il disco 5 sara' sul piolo 0
Il disco 6 sara' sul piolo 0
Il disco 7 sara' sul piolo 0
Verificando e' proprio cosi', questa e' una delle magie di J.H.Conway.
ciao

Pero' davanti ad una tripla non so ancora come muovermi 8-(
emh.. se cerchi online da qualche3 parte ci sono dispense di vari
corsi di informatica (io a ing. inf. lo diedi a "Fondamenti di
Informatica 1") dove viene fornito l'algoritmo esatto
(che ovviamente adesso non mi viene in mente :)

La soluzione "classica" che l'informatica da' al problema della torre di
Hanoi e' quella ricorsiva.
Provo a fartela capire intuitivamente (per l'algoritmo basta Google).
Supponi di aver una torre con 2 dischi in posizione 1, e di volerli spostare
in posizione (ad esempio) 3.
Sol. 1->2, 1->3, 2->3
Come vedi ora sai spostare a tuo piacere una mini-torre di 2 dischi.
---
Ora invece hai 3 dischi in 1, e li vuoi spostare in posizione 2.
Sol. sposti i 2 dischi piu' piccoli in posizione 3, 1->2, e poi sposti i 2
dischi in posizione 3 in 2.
Ora sai spostare una mini-torre di 3 dischi.
---
Con 4 dischi sposti la mini-torre da 3, sposti 4, e quindi gli sposti sopra
la torre da 3.
E cosi' via.
Ciao
Tom Cat


La soluzione ricorsiva la conoscevo gia', solo che non vorrei dover 
generare tutta la sequenza di mosse per capire come muovermi da una 
combinazione corretta.
Bye by SixaM 8-]


Credo che la soluzione generata dall'algoritmo di ricorsione sia la piu'
breve possibile.
Ma forse non ho capito bene la tua risposta ...
Ciao
Tom Cat

 breve possibile.
Credi male... la soluzione iterativa è ancora più breve. :-)
