Calcolare tutte le possibili mosse in una partita a scacchi

[domx]

Ah, ho capito, roba che io non conosco (ancora)
va beh, qualcosa per annoiarmi meno quest'estate, grazie
per ora ovviamente non credo sia necessario studiare le serie geometriche, basta scrivere il risultato sulla tesina...

[Gottinger95]

E' abbastanza banale come problema, però è carino per i risvolti matematici che ha. Prendi una scacchiera 3x3 e numera le caselle, con 1,2,3 nella prima riga. Poi posiziona due cavalli bianchi nei vertici in alto (caselle 1 e 3) e due cavalli neri nei vertici in basso (caselle 7 e 9). L'obiettivo è quello di mettere i cavalli bianchi al posto di quelli neri e viceversa, secondo le mosse del cavallo degli scacchi. Ovviamente due cavalli non possono occupare una stessa casella, e le mosse non possono essere contemporanee. Per risolverlo in maniera elegante imposti un grafo con 9 vertici numerati secondo le caselle e colleghi i vertici che sono raggiungibili in una mossa. In questo modo la soluzione è banale: basta far circolare i cavalli sul grafo, facendo solo attenzione che non si sovrappongano. E' un grafo semplice di due componenti connesse: una è un ciclo, l'altra è una casella isolata (quella centrale, che non può essere raggiunta).
Poi da là attacchi a parlare dei grafi, e secondo me fai un figurone da paura!
Scusa ma non sono in grado di inserire un disegnino: lascio alla tua immaginazione questo compito gravoso.

[domx]

E' abbastanza banale come problema, però è carino per i risvolti matematici che ha. Prendi una scacchiera 3x3 e numera le caselle, con 1,2,3 nella prima riga. Poi posiziona due cavalli bianchi nei vertici in alto (caselle 1 e 3) e due cavalli neri nei vertici in basso (caselle 7 e 9). L'obiettivo è quello di mettere i cavalli bianchi al posto di quelli neri e viceversa, secondo le mosse del cavallo degli scacchi. Ovviamente due cavalli non possono occupare una stessa casella, e le mosse non possono essere contemporanee. Per risolverlo in maniera elegante imposti un grafo con 9 vertici numerati secondo le caselle e colleghi i vertici che sono raggiungibili in una mossa. In questo modo la soluzione è banale: basta far circolare i cavalli sul grafo, facendo solo attenzione che non si sovrappongano. E' un grafo semplice di due componenti connesse: una è un ciclo, l'altra è una casella isolata (quella centrale, che non può essere raggiunta).
Poi da là attacchi a parlare dei grafi, e secondo me fai un figurone da paura!
Scusa ma non sono in grado di inserire un disegnino: lascio alla tua immaginazione questo compito gravoso.

ho già fatto l'esame, comunque grazie lo stesso, sembra una cosa interessante

[Sonner]

Vi riporto un problema carino che non mi ricordo più dove ho trovato:

"è possibile che un cavallo partendo dalla casa A1 possa arrivare in H8 passando una e una sola volta da ogni casa?"

[Valenash]

Vi riporto un problema carino che non mi ricordo più dove ho trovato:

"è possibile che un cavallo partendo dalla casa A1 possa arrivare in H8 passando una e una sola volta da ogni casa?"

HINT:

Testo nascosto:

colori

SOLUZIONE:

Testo nascosto:

no, infatti ad ogni mossa il cavallo va su una casa di colore diverso da quella precedente.
Quindi per toccare 64 caselle, deve partire da una di un colore e arrivare in una di colore contrario.
A1 e H8 hanno entrambe lo stesso colore (stanno sulla diagonale), indi per cui non è possibile.