Newsgroup: it.hobby.enigmi
Titolo: Cavallo Pazzo

In attesa di partire per un meritato riposo ho rispolverato 
la mia vecchia scacchiera e preso da un attimo di follia mi
sono messo a giocare con un cavallo che definire pazzo e' poco.
Posto questo quesito, ma quasi sicuramente ci sono passati 
anche gli antichi romani...
;-)
"Cavallo Pazzo"
Prendiamo una scacchiera classica 8x8 in cui mettiamo un 
cavallo in uno dei 4 angoli.
Il cavallo muove a caso in tutte le sue possibili mosse e dovrebbe
passare, almeno una volta, per tutte le 63 caselle rimanenti.
In quante mosse, in media, ci riesce ?
Se la scacchiera 8x8 e' troppo impegnativa si potrebbe 
provare a partire dalla 4x4 che e' la piu' piccola in cui il
cavallo riesce a muoversi liberamente...
CiaO e Buona Pasqua,
Massimo
PS...Io non ho neppure provato, ma lo porto con me...

 cavallo riesce a muoversi liberamente...
Nessuna proposta, per cui non mi sono spiegato (molto prob.)
oppure e' impossibile qualsiasi approccio (non credo).
Fiducioso aspetto prima di dire cosa avevo pensato io...
CiaO,
Massimo


Mai.
Perchè, per quello che so io se un cavallo è in una casella bianca, rimarrà
sempre nelle caselle bianche e quindi ne toccherà al massimo trentadue.
Ciao
Sisifo.

sempre nelle caselle bianche e quindi ne toccherà al massimo trentadue.
Oddio, che mi tocca sentire :( ... Sisifo non giochi a scacchi, vero?
Cmq così, a naso, credo che esista un modo per fare toccare in sole 63
mosse tutte le altre 63 caselle. Adesso ci penso...
Ciao
Stark

 mosse tutte le altre 63 caselle. Adesso ci penso...
Scusate se intervengo, non portando la soluzione, perche'
e' un po' tardino e non ho voglia di ritrovare il giro di cavallo
a quest' ora,annotare le mosse ecc.
Comunque questa cosa (Il cavallo inizia da una casella e
le tocca tutte una ed una sola volta) e' possibilissima anzi,
se non ricordo male esistono decine (non vorrei esagerare,
ma forse centinaia) di modi differenti per farlo.
Cosi' a memoria, mi ricordo che e' una buona regola cominciare
a girare intorno alla scacchiera, avendo cura di lasciare agli
angoli il posto giusto per i passaggi successivi dell' animale,
e spostarsi progressivamente verso il centro.
Non saprei dove si possa trovare su internet, ma sicurissimamente
esiste, il problema e' stato analizzato in un sacco di libri,
mi pare pure su quelli di Gardner.
ciao
fulvio

 ma forse centinaia) di modi differenti per farlo.
Basta chiedere a Dario Uri.
Ha anche scritto un bellissimo articolo in merito pubblicato su
Contromossa dell'aprile-maggio 86.
Sempre su Contromossa (giugno 85) è apparso un mio articolo
sull'argomento.
L'ho scannerizzato e ve ne propongo uno stralcio.
Farò la stessa cosa domani per l'articolo di Dario.
TOPOLOGIA & ROMPICAPO di Giovanni Ravesi
Un problema che ha sempre attirato l'attenzione di matematici e
topologi, è sicuramente quello dei percorsi di cavallo su di una
scacchiera. In particolare quello dei cosiddetti percorsi
rientranti; di quei percorsi ciclici che, dopo aver toccato una
sola volta tutte le caselle, ritornino, cioè, al punto di
partenza.
[cut]
Fra i vari metodi di soluzione suggeriti, merita particolare
attenzione quello proposto, agl'inizi dell'800, da Eulero, valido
per quadrati e rettangoli di qualsiasi dimensione. Tale metodo
porta ad una soluzione rientrante (quando possibile) ma
normalmente asimmetrica.
Esso consiste nel muovere inizialmente a caso il cavallo sulla
scacchiera fino a che ciò sia possibile e nel successivo recupero
(in una o più volte) delle caselle non toccate, mediante
appropriate ed eventualmente ripetute permutazioni di tratti ad
una o ad entrambe le estremità della catena di caselle formata
fino a quel momento. Lo stesso sistema si presta anche alla
ciclizzazione del percorso; anzi, la preventiva ciclizzazione del
percorso ancora incompleto, favorisce il recupero delle caselle
non ancora raggiunte.
Supponendo che, su di una scacchiera si sia percorsa,
numerandola, una catena formata da 60 caselle, si potrebbe avere,
ad esempio, che la casella 60 possa essere raggiunta anche dalla
casella 53. In tal caso, invertendo la numerazione
delle caselle da 54 a 60, si otterrà un nuovo percorso in cui
l'ultima casella toccata sarà quella precedentemente
contrassegnata con il numero 54. Con l'ultima casella in questa
nuova posizione, si potrà ripetere più volte il procedimento,
spostando ogni volta la casella 60, fino a portarla in una
posizione
da cui sia possibile raggiuntgere una o più caselle non ancora
toccate, recuperandole, o da cui sia possibile raggiungere la
casella 1, ciclizzando il percorso. Lo stesso procedimento può
essere usato per spostare l'ubicazione della casella 1.
L'eventuale ciclizzazione consente, a sua volta di potere ruotare
a piacimento la numerazione delle caselle, consentendo, quindi,
di portare la casella 60 nella posizione idonea per aprire il
percorso ciclico e raggiungere una o più caselle non ancora
recuperate.
Una estensione del metodo di Eulero consente di arrivare alla
costruzione di percorsi che, oltre ad essere rientranti, siano
anche simmetrici. Vediamone la sua applicazione ad una scacchiera
8 x 8. Si divida in due parti la scacchiera e nella sua metà in
basso, si costruisca, con le modalità appena viste, un percorso
non rientrante di 32 caselle, che inizi e finisca, ad esempio,
nella 3° e nella 4° casella della 5° riga della scacchiera. Si
ruoti di 180° il percorso ottenuto, si
aggiunga 32 ai suoi numeri e lo si riporti nella parte alta della
scacchiera. In tal modo, l'inizio e la fine dei due percorsi
risulteranno connessi fra di loro, formando un unico percorso
ciclico e simmetrico.
Un altro interessante metodo di soluzione, è stato dato nel 1823
da Warnsdorff, il
quale proponeva la seguente regola. il cavallo dovrà essere
sempre mosso in una delle caselle dalle quali avrà la minor
libertà di movimento. Tale regola, anche se non se n'è dimostrata
l'assoluta veridicità, sembra funzionare sempre e su qualsiasi
tipo di scacchiera, dando, però, solo percorsi non rientranti.
Ciao
Gianni
--
Io voto Berlusconi perchè credo alla Befana

> Oddio, che mi tocca sentire :( ... Sisifo non giochi a scacchi, vero?
No, in effetti, no.
Ogni tanto sarebbe molto opportuno
rispettare qualche minuto di silenzio.
Ciao
Sisifo.

> Oddio, che mi tocca sentire :( ... Sisifo non giochi a scacchi, vero?
Ehi, sempre senza offesa... :)
Non te la sei presa, vero?
Con amicizia
Stark

 Basta chiedere a Dario Uri...
Effettivamente questo problema e' antichissimo e ha
coinvolto molti matematici del passato, esiste un'immensa
bibliografia.
Colgo l'occasione per 2 segnalazioni. Uno dei problemi piu'
spinosi e' quello di enumerare tali percorsi chiusi o
aperti, la sol. e' stata trovata di recente (febbraio 1994)
da Brendan D. McKay. I percorsi possibili sulla scacchiera
8x8 escludendo R&R sono 1.658.420.855.433.
Uno dei maggiori esperti e storici di questo problema e'
senz'altro G.P.Jelliss, editore di The Games amnd Puzzles
Journal, una fanzine che racchiude recenti risultati oltre
che storici. Jelliss si avvale spesso di materiale raccolto
dal famoso T.R.Dowson nella mitica Fairy Chess pubblicata
fra il 1930 ed il 1947. Vedere per credere la sua home page:
http://homepages.stayfree.co.uk/gpj/index.htm
una impressionante quantita' di ottimo materiale.
:) dario

 In media? Che cosa vuol dire?
 
Vediamo se riesco a spiegarmi in questo modo:
- Prendi una scacchiera classica 8x8 oppure una 4x4, 5x5...etc.
- Prendi un "pezzo pazzo"...(Cavallo che si muove random sulla
scacchiera)
- Lo lasci libero di muovere
- Annoti tutte le mosse che effettua
- quando riesce a passare per tutte le rimanenti 63 caselle ti fermi
- La risposta e' il numero medio di mosse che servono.
Il numero e' medio perche' il "cavallo pazzo" muove senza una logica
precisa per cui le 63 mosse minime necessarie saranno solo un caso
estremo.
CiaO,
Massimo

estremo.
non so se questo calcolo è praticabile... 
per avere un "numero medio" bisogna calcolare la media delle possibili
sequenze di mosse... quante saranno?
Chiedo lumi agli statistici del NG.
ciao
Stark

 In quante mosse, in media, ci riesce ?
Cio ho provato centomila volte, ed in media ci metto poco meno di 540 mosse,
con una varianza di quasi 200 mosse.
Silv:o)

"Silvio Sergio" ha scritto

Ciao Silvio, e bentornato!
devo dire che mi aspettavo un risultato inferiore (poco più della metà) del
tuo.
Con un ragionamento *a spanne* ho considerato che, dopo un certo numero, non
troppo grande, di mosse, possiamo ritenere con buona approssimazione, che la
prossima casella sia casuale.
Cioè, supponiamo che a un certo punto siano rimaste k caselle non ancora
toccate, la probabilità che la prossima mossa faccia decrementare questo
valore dovrebbe essere circa k/63, e mediamente dovrei impiegare 63/k di
mossa per portare le caselle libere a k-1.
Allora 63/63=1 mossa per ridurre le caselle libere da 63 a 62;
63/62=1.016 mosse (in media) per ridurle a 61
...
63/1=63 mosse per eliminare l'ultima casella libera.
sommando 63*(1/63 + 1/62 +... 1/1)= 298 mosse circa.
Per una valutazione *un po'* più accurata ho anche considerato che i
movimenti del cavallo passano sempre da una casella ad un'altra di diverso
colore. Allora valuto separatamente le mosse dispari, che portano su case
bianche, e le pari che portano su case nere.
Per le dispari, se k sono le case libere su 32 possibili, servono 32/k mosse
per ridurle a k-1. Quindi
32*(1/32+1/31+...1/1)=130 mosse dispari circa, per eliminare le 32 caselle
bianche. Altrettante *circa* mosse pari per le caselle nere.
Sicuramente in tutto il ragionamento c'è qualcosa che non va, ma non riesco
a capire dove sia l'errore.
ciao
paolo

 a capire dove sia l'errore.
Ciao, Paolo!
Ho verificato sperimentalmente il tuo ragionamento e il tuo calcolo e ti
dico che il tuo 298 coincide pienamente con quanto ottenuto dalla mia
simulazione. Però ad una condizione: che il pezzo che si muove a caso nella
scacchiera non sia un Cavallo ma un pezzo in grado di saltare a caso su una
casella qualunque della scacchiera (una specie di SuperRegina in grado di
muovere dove vuole).
Nel caso del Cavallo ottengo un risultato simile a quello ottenuto da
Silvio: 568 mosse in media.
Ritengo che la differenza tra il 298 della SuperRegina e il 568 del Cavallo
sia da imputare alla modalità di spostamento del Cavallo stesso. Per quanto
questo pezzo salti, i suoi salti sono sempre limitati nello spazio e il
rischio di tornare vicino a dove era e quindi su caselle già toccate è
abbastanza alto. Non solo, tra le 8 possibili mosse che il Cavallo può fare
(quando non sono meno, in prossimità dei bordi della scacchiera), una lo
riporta sempre nella cella da cui proveniva. Bisognerebbe aggiungere al tuo
ragionamento una stima accurata di ciò, ma non mi sembra molto facile!
Ho simulato il movimento di un Re e il tempo medio è di 597 (e in fondo,
come capacità di spostamento, il Cavallo è  una via di mezzo tra un Re e una
SuperRegina (molto spannometricamente parlando! :-) ).
Ciao
Giorgio


Ho fatto altre simulazioni con pezzi varianti del Cavallo. Definendo
Cavallo2x1 il normale Cavallo degli scacchi (che muove di 2 in una direzione
e 1 trasversalmente), ho provato anche i Cavalli 4x1, 3x2, 4x3. Questi sono
gli unici cavalli in grado di percorrere tutta la scacchiera. I cavalli axb
dove a+b è pari vanno sempre su caselle dello stesso colore (potremmo
definirli "Cavalli di Sisifo" :-)))) ), mentre i cavalli dove a o b è > 4
non sono in grado di raggiungere le caselle centrali.
Questi i risultati della simulazione:
Pezzo      Numero medio di mosse
Cavallo2x1 538 (erroneamente riportato come 568 nel post precedente)
Cavallo4x1 533
Cavallo3x2 553
Cavallo4x3 792
Sembra proprio che il numero medio delle mosse sia in funzione della
capacità di andare lontano (più salta lontano e meno mosse impiega), ma
soprattutto delle limitazioni che un movimento ampio dà quando si è vicino
ai bordi (più salta e più il numero di mosse possibili si riduce
avvicinandosi ai bordi della scacchiera).
Ciao
Giorgio