Nel 1880, l’enigmista americano Sam Loyd annunciò un premio di 1000 dollari per chiunque potesse risolvere uno specifico 15-puzzle: la disposizione standard da 1 a 15 con 14 e 15 scambiati. La mania del puzzle stava già travolgendo America ed Europa; lo stunt di Loyd aggiunse benzina al fuoco. Migliaia provarono. Nessuno vinse.
C’era una ragione per cui nessuno vinse. La griglia di Loyd era dimostrabilmente irrisolvibile, e la dimostrazione è abbastanza semplice da stare in una pagina. Questo articolo è quella pagina.
L’affermazione
Esattamente metà di tutti i 16!/2 ≈ 10.461.394.944.000 modi di disporre quindici tessere e un vuoto su una griglia 4×4 può essere risolta nell’obiettivo standard. L’altra metà non può essere risolta. Il "14 e 15 scambiati" di Loyd sta nella metà irrisolvibile.
Questo si generalizza. Su ogni puzzle scorrevole N×N, metà di tutte le disposizioni è irrisolvibile. L’8-puzzle 3×3 ha 9!/2 = 181.440 griglie risolvibili su 362.880 totali; il 24-puzzle, il 35-puzzle e così via seguono la stessa regola.
Inversioni
La dimostrazione richiede una sola definizione. Leggi le tessere in ordine di lettura — da sinistra a destra sulla riga 1, poi sulla riga 2, poi sulla riga 3, poi sulla riga 4 — e ignora il vuoto. Ottieni una sequenza di quindici numeri.
Un’inversione è una coppia (a, b) in cui a appare prima di b nella sequenza, ma a > b. Conta ogni coppia di questo tipo nell’intera sequenza. Quel conteggio è il numero di inversioni della griglia.
Esempio: lo stato obiettivo 1,2,3,…,15 ha zero inversioni. Il "14 e 15 scambiati" di Loyd ha la sequenza 1,2,3,…,13,15,14, che ha esattamente una inversione (la coppia 15,14).
Il lemma chiave: uno scorrimento cambia la parità in modo controllato
Cosa succede al conteggio delle inversioni quando fai una mossa legale?
-
Scorrimenti orizzontali (una tessera si sposta di una casella a sinistra o a destra): la tessera spostata cambia posizione nella sequenza in ordine di lettura di uno slot. Il suo ordine relativo con ogni altra tessera nella sequenza rimane esattamente lo stesso — perché il movimento orizzontale non cambia la riga della tessera né quali tessere la precedono o seguono nell’ordine di riga. Il conteggio delle inversioni rimane invariato.
-
Scorrimenti verticali (una tessera si sposta in alto o in basso di una casella): la tessera spostata salta sopra altre tre tessere nella sequenza in ordine di lettura — le tre tessere della riga che attraversa. Ognuna di queste tre passa o da "dopo" a "prima" o viceversa, il che significa che ciascuna contribuisce con +1 o -1 al conteggio delle inversioni. La somma di tre ±1 è sempre dispari. Quindi il conteggio delle inversioni cambia di un numero dispari.
In sintesi: uno scorrimento orizzontale preserva la parità del conteggio delle inversioni (pari o dispari). Uno scorrimento verticale la inverte.
Anche la riga del vuoto si inverte negli scorrimenti verticali
Traccia la riga del vuoto, contando le righe dall’alto. Uno scorrimento orizzontale lascia il vuoto nella stessa riga. Uno scorrimento verticale lo sposta in alto o in basso di una riga, quindi la riga del vuoto cambia parità (riga pari ↔ riga dispari).
Abbiamo ora due cose che cambiano insieme:
- La parità del conteggio delle inversioni si inverte ⇔ scorrimento verticale.
- La parità della riga del vuoto si inverte ⇔ scorrimento verticale.
La loro somma è quindi invariante sotto ogni scorrimento legale. Abbiamo trovato una quantità conservata.
Il teorema di parità
Definisci l’invariante:
P = (conteggio delle inversioni) + (numero di riga del vuoto, contato dal basso, partendo da 1)
Questa è la quantità conservata. A ogni scorrimento legale, P cambia di un numero pari, quindi la sua parità (pari o dispari) non cambia mai.
Lo stato obiettivo ha zero inversioni e il vuoto nella riga 1 dal basso — quindi P = 1 (dispari). Qualsiasi griglia con P pari è irraggiungibile dall’obiettivo, e viceversa l’obiettivo è irraggiungibile da qualsiasi griglia di quel tipo.
Questo fornisce un test di risolvibilità pulito per il 15-puzzle:
- Leggi le tessere in ordine di riga, ignorando il vuoto.
- Conta le inversioni.
- Conta la riga del vuoto dal basso (1, 2, 3 o 4).
- Somma. Se la somma è dispari, la griglia è risolvibile. Se è pari, non lo è.
Il "14 e 15 scambiati" di Loyd ha 1 inversione e il vuoto nella riga 1 dal basso — somma 2, pari, irrisolvibile.
Come si presenta per altre dimensioni
La regola di parità N×N dipende dal fatto che N sia pari o dispari. L’enunciato generale:
- N dispari (3×3, 5×5, …): una griglia è risolvibile sse il conteggio delle inversioni è pari. La riga del vuoto non conta, perché la parità della riga del vuoto è determinata dalla parità del conteggio delle inversioni per ragioni di simmetria.
- N pari (4×4, 6×6, …): una griglia è risolvibile sse (conteggio delle inversioni) + (riga del vuoto dal basso) è dispari.
Per un 3×3, il test è semplicemente "il numero di inversioni è pari?". È più semplice della versione 4×4, e si memorizza in un minuto.
Una bella conseguenza
Poiché esattamente metà delle disposizioni è risolvibile, un rimescolamento casuale seguito dal controllo della parità è più veloce di un rimescolamento casuale seguito dal tentativo di risolvere. Le app che devono garantire posizioni di partenza risolvibili fanno una delle due:
- Pre-screening con il test di parità e rimescolano se fallisce.
- Generano camminando all’indietro dall’obiettivo, applicando scorrimenti casuali validi. Questo garantisce la risolvibilità per costruzione ed è ciò che fa la maggior parte delle app, la nostra inclusa.
Se mai giochi a un puzzle scorrevole e lo trovi impossibile qualunque cosa tu provi, l’app l’ha generato male — non è colpa tua, e non è un puzzle dall’universo.
La nota a piè di pagina su Sam Loyd
Il premio di 1000 dollari di Loyd è uno degli scherzi pratici meglio documentati nella storia degli enigmi. Il matematico che dimostrò l’irrisolvibilità — in modo indipendente — fu o William Johnson e William Story (1879, American Journal of Mathematics) o lo stesso Loyd, a seconda di quale resoconto credi. Loyd era una figura famosamente autopromozionale che si attribuì diverse invenzioni che non aveva inventato; il 15-puzzle stesso fu inventato da Noyes Chapman nel 1874, sei anni prima dello stunt del premio di Loyd.
Ciò che Loyd effettivamente contribuì furono il premio, la pubblicità e la variante irrisolvibile — un contributo utile, anche se non quello che pubblicizzava.