Il gioco del quindici
Il gioco del quindici è una cornice con quindici tessere numerate e una casella vuota. Fai scorrere le tessere fino a rimetterle in ordine ed è risolto. Sembra semplice, ma nel 1880 scatenò una mania, e dietro c’è una delle dimostrazioni più eleganti della matematica ricreativa: metà delle posizioni non si potrà mai risolvere.
La mania del 1880
Il gioco viene dallo Stato di New York, negli anni 1870; di solito come inventore si indica Noyes Chapman, direttore dell’ufficio postale di Canastota. All’inizio del 1880 diventò una mania, prima in tutti gli Stati Uniti e poi in Europa.
Il 14-15 di Sam Loyd
L’autore americano di rompicapi Sam Loyd sostenne in seguito di aver inventato il gioco, e parlò di un premio di 1.000 dollari per chiunque riuscisse a risolverlo con soltanto il 14 e il 15 scambiati. Nessuno vinse il premio, e nessuno poteva vincerlo: quella posizione non si può risolvere. Nemmeno la sua pretesa di averlo inventato era vera.
Perché metà delle posizioni è impossibile
Considera la casella vuota come una sedicesima tessera. Ogni scorrimento scambia la casella vuota con una tessera. Per tornare nel suo angolo, la casella vuota deve spostarsi tante volte a sinistra quante a destra e tante volte in alto quante in basso, quindi una posizione con la casella vuota nel suo angolo dista sempre un numero pari di scambi dall’ordine risolto. Scambiare il 14 e il 15 è un solo scambio, cioè dispari, quindi nessuna sequenza di scorrimenti può raggiungerla. Nel 1879 William Johnson e William Story dimostrarono che si può raggiungere esattamente metà di tutte le disposizioni.
Un test per qualsiasi posizione
Conta le coppie di tessere che stanno nell’ordine sbagliato quando leggi la cornice riga per riga. Su una griglia 3×3 o 5×5 una posizione si può risolvere quando quel numero è pari. Su una griglia 4×4 aggiungi la riga della casella vuota contata dal basso: la posizione si può risolvere quando la somma è dispari.
Risolverlo al computer
Un computer può cercare una via di ritorno con A*, che esamina sempre per prima la posizione più promettente. Stima le mosse ancora necessarie in base a quanto ogni tessera dista dalla sua casella di destinazione, più due mosse per ogni coppia di tessere che si bloccano a vicenda nella propria riga o colonna. Trovare la soluzione più breve diventa molto difficile sulle griglie grandi. Le posizioni più difficili del gioco del 15 richiedono 80 mosse, e il gioco dell’8 non ne richiede mai più di 31.
Prova in PictorX
Apri il Gioco del quindici e fai clic su una tessera per farla scorrere. Mescola mette le tessere in una nuova posizione che si può risolvere, Risolvi riproduce una soluzione mossa dopo mossa, e «Mostra tessere al posto giusto» colora i numeri delle tessere che sono già al loro posto. Scegli «14-15 di Loyd» per vedere la posizione impossibile, e usa Dimensione per passare tra 3×3, 4×4 e 5×5.
Domande frequenti
Chi ha inventato il gioco del quindici?
Di solito come inventore si indica Noyes Chapman, direttore dell’ufficio postale di Canastota, New York, negli anni 1870. La successiva pretesa di Sam Loyd di averlo inventato era falsa.
Il rompicapo 14-15 si può risolvere?
No. Dista un solo scambio dall’ordine risolto, e ogni posizione che gli scorrimenti possono raggiungere ne dista un numero pari.
Quante posizioni ha il gioco del quindici?
Le 16 caselle si possono riempire in 20.922.789.888.000 modi. Esattamente la metà, 10.461.394.944.000, si può raggiungere facendo scorrere le tessere.
PictorX carica qualcosa?
No. Il gioco è disegnato su una tela nel browser. Salva scarica un PNG, e Modifica apre quell’immagine nell’editor di PictorX.
Strumenti correlati
Gioco del quindici
Gioca nel browser al classico gioco del quindici, il rompicapo a tessere scorrevoli di legno, su 3×3, 4×4 o 5×5. Mescola, fai scorrere intere righe in una volta, prova l’impossibile 14-15 di Sam Loyd, oppure guarda Risolvi completarlo.
Torre di Hanoi
Sposta una torre di dischi su tre pioli nel browser. Un disco alla volta, mai uno più grande su uno più piccolo. La soluzione più breve è di 2ⁿ − 1 mosse.
Torre di Hanoi
La Torre di Hanoi: tre pioli, un disco alla volta e mai uno più grande su uno più piccolo. La soluzione più breve è di 2ⁿ−1 mosse. Édouard Lucas presentò il rompicapo nel 1883.
Giro del cavallo
Fai saltare un cavallo degli scacchi su ogni casella della scacchiera esattamente una volta. Gioca da solo con i suggerimenti di Warnsdorff, oppure guarda Risolvi completare un giro aperto o chiuso. Salva il percorso come PNG.
Otto regine
Posiziona otto regine su una scacchiera in modo che nessuna ne attacchi un’altra. Prova tu stesso, guarda la ricerca con backtracking trovare una soluzione passo dopo passo e scorri tutte le 92 soluzioni.
Formica di Langton
Avvia la formica di Langton nel browser. Osserva simmetria, caos e l’autostrada di 104 passi, poi prova regole multicolore, più formiche, una griglia esagonale e i turmiti.
Pronto a provarlo?
Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.
Prova il gioco del quindici