gioco del 15
Alberto Calderone
un algoritmo, una regola per risolvere sempre il gioco del 15, un
procedimento da poter programmare! Grazie gia da ora.
se tu non lo conoscessi:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15
č quello fatto cosě con i tasselli che scorrono!
GRAZIE!
--
Posted from ammi01.mailbridge.pronet.it [194.183.5.12]
via Mailgate.ORG Server - http://www.mailgate.org
Roscio
>un algoritmo, una regola per risolvere sempre il gioco del 15, un
>procedimento da poter programmare! Grazie gia da ora.
>
>se tu non lo conoscessi:
>1 2 3 4
>5 6 7 8
>9 10 11 12
>13 14 15
Cominciamo col dire che non tutte le configurazioni dei tasselli portano ad una soluzione.
(una famosa versione del solitario, proposta da Sam Lloyd, riportava il 14 ed il 15
invertiti di posto - questa configurazione è impossibile da risolvere - io stesso mi sono
divertito un sacco invertendo i due numeri in una scacchiera e proponendo agli amici di
risolvere il gioco...).
Il motivo credo dipenda dal fatto che una mossa "valida" scambia due tasselli (di cui uno è
il tassello vuoto) che stanno o in verticale o in orizzontale fra loro, ma non in diagonale.
Ciò comporta che ci sono esattamente la metà delle configurazioni di sedici tasselli
(compreso il vuoto) che sono risolvibili.
Anche una vecchia versione del gioco, con alcune lettere anziché i numeri,
il cui scopo era di comporre la frase:
R A T E
Y O U R
M I N D
P A L
(prova la tua intelligenza, ragazzo)
giocava sul fatto che le due "R" si trovano su due posizioni non intercambiabili,
per cui se si comincia mettendo la seconda "R" all'inizio della configurazione,
non si potrà arrivare alla soluzione.
Un metodo per sapere se la configurazione porta ad una soluzione è quello
di controllare (dopo aver posizionato il vuoto in basso a destra) se i numeri dispari
stanno tutti su caselle dispari e quelli pari su caselle pari, o che ci sia un numero
PARI di inversioni. Per esempio, se avessimo la configurazione col 14 e 15 scambiati,
per farla diventare valida dovremmo o scambiare il 14 col 15 (ovviamente), oppure
scambiare un'altra coppia di numeri di cui uno dispari ed uno pari.
Partendo da una configurazione valida, l'algoritmo di soluzione è piuttosto banale:
basta impostare i tasselli cominciando da quello che deve andare in alto a sinistra,
continuando verso destra e proseguendo alla riga sottostante, ricordandosi che
per inserire un numero tra due altri numeri, basta mettere i primi due numeri sulla
stessa riga e quello da inserire sulla riga successiva, poi far andare il vuoto tra
i due numeri ed inserirvi il numero. Manipolando il gioco si trovano facilmente
"gruppi" di mosse che permettono di spostare agevolmente un tassello da una parte
all'altra della scacchiera.
--
Er Roscio.
Mauro Fiorentini
Alberto Calderone wrote:
> ...
> se tu non lo conoscessi:
> 1 2 3 4
> 5 6 7 8
> 9 10 11 12
> 13 14 15
> č quello fatto cosě con i tasselli che scorrono!
>
Io proverei a scrivere sequenze prefissate di mosse che, per esempio,
portano
due caselle in posizione fissa all'interno di un rettangolo 2 x 3 o 2 x 4,
lasciando
invariate le caselle all'esterno.
Dopodiche' : porto 1 e 2 nelle prime colonne;
porto 1 e 2 in alto
porto 3 e 4 a posto etc.
alla fine resta un quadrato 2 x 2.
Una paio di tabelle e poca "intelligenza".
Naturalmente un controllo di parita' iniziale serve a stabilire se il
problema
e' risolubile o meno.
Se ti interessa, e' stato stabilito che 80 mosse bastano da qualsiasi
posizione
iniziale e ci sono posizioni iniziali che le richiedono; se scrivi un
algoritmo
euristico, questo dato ti puo' servire per stabilirne la bonta'.
Ciao
Mauro Fiorentini
Dario Uri
> Naturalmente un controllo di parita' iniziale serve a stabilire se il
> problema
> e' risolubile o meno.
>
> Se ti interessa, e' stato stabilito che 80 mosse bastano da qualsiasi
> posizione
> iniziale e ci sono posizioni iniziali che le richiedono; se scrivi un
> algoritmo
> euristico, questo dato ti puo' servire per stabilirne la bonta'.
Ciao Mauro,
per approfondire gli argomenti distanze, parita'.....ecc:
http://johnrausch.com/PuzzleWorld/art01.htm
http://www.cut-the-knot.com/
da qui si clicca "3 Games and Puzzle" poi "27 Sam Loyd fifteen"
(in realta' il gioco non e' di Sam L.)
ciao dario
Mauro Fiorentini
Dario Uri wrote:
> ......
> Ciao Mauro,
> per approfondire gli argomenti distanze, parita'.....ecc:
>
> http://johnrausch.com/PuzzleWorld/art01.htm
>
> http://www.cut-the-knot.com/
> da qui si clicca "3 Games and Puzzle" poi "27 Sam Loyd fifteen"
Grazie
>
> (in realta' il gioco non e' di Sam L.)
> ciao dario
COOOME? Sei sicuro? (domanda stupida) E di chi e' allora?
Tutti i libri (che ho letto io) lo citano come uno dei grandi successi di
Loyd.
Ciao
Mauro Fiorentini
Dario Uri
> COOOME? Sei sicuro? (domanda stupida) E di chi e' allora?
> Tutti i libri (che ho letto io) lo citano come uno dei grandi successi di
> Loyd.
Difatti e' stata fatta un po' di confusione.
Il gioco apparve nel 1879.
I primi scritti riguardanti il gioco del 15:
-W.W.Johonson (1879) American Journal of Mathematics,n.2 pp 397/399:
" A ruled square of 16 compartements is numbered....fifteen counters
numbered in like manner are placed at random upon squares so that one
square is vacant..."
-Rev.T.P.Kirkman (1880) Mathematical questions and solutions.
Educational Times Reprints n.34 pp.113/114:
-G.A.Sala (1880) Echoes of the Week in Illustrated London New n.76 p.491
"You take out the number 16; you mix up the counters in the box so that
will run irregurarly..."
-J.W.Snowdon (1880) The fifteen puzzle in Leisure Hour n.29 pp.493/495.
"Sixteen small wooden cubes, numbered from one to sixteen, are placed in
random order in a shallow box.."
-Edward Lucas (1881) Revue Scientifique de la France et de Entranger n.3
pp.783/788.
Riferisce che Sylvester il matematico inglese corrispondente
dell'Accademia delle scienze di Parigi e professore alla Hopkins di
Baltimora, gli avrebbe riferito che il gioco fu inventato da un
sordomuto 18 mesi prima.
Ce ne sono altri, e nessuno di questi riporta la questione delle
parita'.
Quello che scopri' Loyd fu che solo meta' delle sistemazioni casuali
delle pedine danno luogo ad una soluzione, cosi' propose quello che
passo' alla storia come gioco del 14-15. Iniziando con le ultime due
pedine invertite, ed offri' i famosi 1000 dollari, che nessuno
naturalmente incasso, ma gli favorirono molta pubblicita'.
Un'altra prova, e' che Loyd brevettava tutte le sue invenzioni che
riteneva buone, e non c'e' traccia del 15 nell'archivio americano. (Ho
la fortuna di avere le copie di tutti i brevetti americani su giochi
meccanici dal 1803 ad oggi. 20 volumi. Un lavoro di ricerca complesso
fatto da un collezionista del Lussemburgo)
Il nome di quel sordomuto, vero inventore del 15, resta sconosciuto,
l'unica cosa certa e' l'origine americana.
ciao :)dario