Se hai mai passato trenta minuti su un 15-puzzle che semplicemente non finisce — ogni mossa che fai porta a due tessere scambiate alla fine — c’è una possibilità che il puzzle sia matematicamente irrisolvibile. Esattamente metà di tutte le disposizioni del 15-puzzle lo sono. Un’app scritta male può generarne una per errore.
Questo articolo è il controllo pratico. La giustificazione matematica completa vive in il teorema di parità; questo mantiene le cose semplici.
Il controllo in 30 secondi
Guarda le tessere in ordine di lettura — da sinistra a destra su ogni riga, dall’alto in basso — ignorando il vuoto.
Per ogni coppia di tessere, conta quante volte un numero più grande appare prima di uno più piccolo. Quel conteggio è il numero di inversioni.
Poi nota in quale riga si trova la casella vuota, contando dal basso (la riga in basso è 1, la riga sopra è 2, poi 3, poi 4 in alto).
Somma il numero di inversioni e la riga del vuoto dal basso. Se il risultato è dispari, il puzzle è risolvibile. Se pari, non lo è.
Ecco fatto. Quello è l’intero controllo.
Un esempio guidato
Supponi che la tua griglia abbia questo aspetto:
1 2 3 4
5 6 7 8
9 10 11 12
13 15 14 _
Ordine di lettura: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 14.
Conta le inversioni. Dobbiamo trovare ogni coppia in cui un numero più grande appare prima di uno più piccolo. Scorrendo: 15 appare prima di 14, e quella è l’unica inversione. Quindi conteggio inversioni = 1.
Il vuoto è nella riga in basso → riga 1 dal basso.
Somma: 1 + 1 = 2. Pari. Questa griglia è irrisolvibile.
Questo è, di fatto, il puzzle premio di Sam Loyd del 1880. L’uomo offrì 1000 dollari a chiunque potesse risolverlo. Il puzzle era irrisolvibile; tenne i suoi soldi.
Un altro esempio
Supponi che la tua griglia abbia questo aspetto:
5 1 3 4
2 6 7 8
9 10 11 12
13 14 15 _
Ordine di lettura: 5, 1, 3, 4, 2, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15.
Conta le inversioni:
- 5 prima di 1 → 1 inversione (5 > 1, e 5 viene prima)
- 5 prima di 3 → 1 inversione
- 5 prima di 4 → 1 inversione
- 5 prima di 2 → 1 inversione
- 3 prima di 2 → 1 inversione
- 4 prima di 2 → 1 inversione
Totale inversioni: 6.
Il vuoto è nella riga in basso → riga 1.
Somma: 6 + 1 = 7. Dispari. Questa griglia è risolvibile.
Nota che 6 + 1 = 7 è dispari perché 6 è pari e aggiungiamo un numero dispari — no, aspetta. 6 + 1 = 7, che è dispari. Risolvibile.
Perché funziona (in breve)
Uno scorrimento legale o muove una tessera orizzontalmente (nessun cambiamento nelle inversioni, nessun cambiamento nella riga del vuoto) o verticalmente (cambia le inversioni di un numero dispari, cambia la riga del vuoto di 1).
In entrambi i casi, la somma di inversioni + riga del vuoto rimane pari-o-dispari nello stesso modo in cui è iniziata. Quindi questa somma è un invariante — una proprietà del puzzle che le mosse legali non possono cambiare.
Lo stato obiettivo (1‑2‑3‑...‑15 con il vuoto in basso a destra) ha 0 inversioni e il vuoto nella riga 1 dal basso. Somma: 1, dispari. Quindi qualsiasi puzzle risolvibile ha somma dispari. Qualsiasi puzzle con somma pari non può raggiungere l’obiettivo.
Per la dimostrazione completa con tutti i casi sviluppati, vedi la pagina sul teorema di parità.
E gli 8-puzzle (3×3)?
Il controllo è più semplice per il 3×3:
- Conta le inversioni in ordine di lettura.
- Se pari, risolvibile.
- Se dispari, irrisolvibile.
Non devi tracciare la riga del vuoto per il 3×3, perché la simmetria del puzzle rende ridondante la dipendenza dalla riga.
(Per 5×5 — stessa regola del 3×3. Per 6×6 — stessa regola del 4×4. La regola è "la riga del vuoto conta quando N è pari".)
Cosa fare se la tua app genera puzzle irrisolvibili
Questo non dovrebbe mai succedere. Un’app ben scritta usa uno di due metodi per evitarlo:
Generare camminando all’indietro dall’obiettivo. Parti dallo stato obiettivo, applica mosse valide casuali e usa lo stato risultante come posizione di partenza. Ogni posizione generata in questo modo è risolvibile per costruzione.
Generare casualmente, poi testare con la parità. Rimescola le tessere uniformemente a caso; calcola il controllo di parità; se pari, scambia due tessere qualsiasi per sistemarlo. La posizione risultante è garantita risolvibile.
Se incontri un puzzle irrisolvibile in un’app, quell’app è rotta. Segnala il bug, cambia app. Slide Puzzle usa il metodo del cammino all’indietro dall’obiettivo e non può produrre posizioni di partenza irrisolvibili.
Cosa fare se sospetti che il tuo puzzle fisico sia irrisolvibile
Due cose:
- Esegui il controllo. Inversioni più riga del vuoto. Se pari, i pezzi fisici sono stati assemblati in modo errato. Estrai una tessera, scambiala con una adiacente, e il puzzle è risolvibile.
- Se anche dopo uno scambio il puzzle ti resiste — la resistenza è la tua strategia, non il puzzle.
Il controllo di parità richiede circa trenta secondi. Farlo prima di affondare un’altra ora in una griglia bloccata è un uso ragionevole di quei secondi.