Esiste un solo metodo per risolvere i puzzle scorrevoli a mano. Non dipende dalla dimensione della griglia. Una volta che lo hai per il 3×3, lo hai per il 4×4, 5×5, 6×6 e qualsiasi dimensione più grande che trovi. Questo è il metodo.
Il piano
Per un puzzle N×N:
- Risolvi la riga 1 — piazza le tessere 1, 2, …, N nella riga in alto.
- Risolvi la colonna 1 — piazza le tessere N+1, 2N+1, … nella prima colonna sotto la riga 1.
- Hai ora un puzzle (N−1)×(N−1). Ricorri.
- Caso base — quando raggiungi un 2×2, le tessere rimanenti o sono in posizione o devi consultare un controllo di parità.
Quello è l’intero algoritmo. Tre frasi. Il resto è meccanica.
La meccanica: angoli
Piazzare le prime tessere di una riga o colonna è facile. Il trucco è piazzare l’ultima tessera — la tessera d’angolo.
Per l’angolo in alto a destra della riga 1 (tessera N su un puzzle N×N):
- Non cercare di far scorrere la tessera N direttamente nell’angolo. Non resterà lì.
- Piazza prima la precedente tessera (tessera N−1) nell’angolo.
- Piazza la tessera N direttamente sotto N−1.
- Ora ruota la coppia: porta il vuoto nell’angolo (spostando N−1), fai scorrere N−1 giù-e-a-sinistra fuori dai piedi, fai scorrere N in alto nell’angolo, fai scorrere N−1 a destra.
L’effetto è che N−1 e N finiscono correttamente piazzate senza disturbare nulla alla loro sinistra.
Questa è la manovra a L dell’angolo. Lo stesso trucco, specchiato, funziona sull’angolo in basso a sinistra della colonna 1.
Se ricordi solo un pezzo di tecnica per puzzle scorrevoli, ricorda questo. Tutto il resto ne discende.
La meccanica: gli interni
Per l’interno di una riga (tessere da 1 a N−2 nella riga in alto), il piazzamento è diretto:
- Trova la tessera che vuoi.
- Spostala in una posizione adiacente alla sua destinazione.
- Usa la casella vuota per farla scorrere in posizione.
Potresti dover spingere da parte altre tessere non piazzate. Va bene — non sono piazzate. Finché non disturbi le tessere già piazzate alla sinistra, la riga si costruisce in modo pulito.
La regola che ti tiene al sicuro: non lasciare mai che la casella vuota attraversi una tessera piazzata. Se il vuoto deve viaggiare dalla destra della griglia alla sinistra di una tessera piazzata, devi instradarlo attorno alla tessera piazzata passando per le celle non piazzate.
Perché "riga, poi colonna"
Due ragioni:
- Simmetria speculare. La manovra dell’angolo di riga e quella dell’angolo di colonna sono esattamente lo stesso trucco, specchiato. Imparare uno ti insegna l’altro.
- Il vuoto ha spazio per lavorare. Dopo aver risolto la riga 1, il vuoto ha le (N−1) righe in basso in cui manovrare. Dopo aver risolto la colonna 1, ha un’area (N−1)×(N−1). L’area di lavoro si restringe con grazia.
Potresti alternare (riga 1, colonna 1, riga 2, colonna 2, …) ma il ritmo naturale è farle in coppia all’esterno, e ricorrere.
La ricorsione
Quando riga 1 e colonna 1 sono fatte, il puzzle (N−1)×(N−1) rimanente contiene tessere che devono andare in una configurazione obiettivo diversa — la stessa sequenza numerica, ma in posizioni diverse. La buona notizia: al metodo non importa. Risolvi la nuova riga in alto, la nuova colonna a sinistra, ricorri. Alla fine arrivi a un caso base 2×2 o 3×3.
Per il caso base 3×3, le ultime tre tessere possono essere ciclate in posizione con singole mosse ripetute. Per un caso base 2×2 (che può presentarsi proprio alla fine di puzzle grandi), vale lo stesso.
Perché funziona a ogni dimensione
La famiglia dei puzzle scorrevoli ha una utile proprietà ricorsiva: risolvere una riga-e-colonna riduce il puzzle a un puzzle più piccolo dello stesso tipo. La matematica è diretta. Dopo aver piazzato N tessere sulla riga 1 (e non averle più toccate), il gioco rimanente vive su una griglia larga (N−1) a cui manca una riga. Dopo aver piazzato la colonna più a sinistra, vive su una griglia (N−1)×(N−1).
Puoi applicare questa riduzione a ogni passo. Il 6×6 si riduce a un 5×5, che si riduce a un 4×4, che si riduce a un endgame 3×3. L’endgame 3×3 è l’unico con una tecnica caso-speciale; tutto ciò che è più grande si riduce ad esso.
Quella struttura ricorsiva è il motivo per cui i puzzle scorrevoli sono spesso usati per insegnare il divide-and-conquer nei corsi di programmazione. La dimostrazione di correttezza è un paragrafo; l’implementazione è il corpo dell’algoritmo.
Quanto diventi veloce
Un risolutore alle prime armi, applicando questo metodo alla lettera, impiega:
In poche partite per dimensione, questi tempi si dimezzano. Il metodo è lo stesso; è solo memoria motoria della manovra dell’angolo.
Per cosa questo metodo non è adatto
Soluzioni ottimali. Un computer con un vero risolutore troverà sequenze del 30–50% più brevi di quelle prodotte dal metodo riga-e-colonna. Gli umani non possono eseguire quegli algoritmi nella testa.
Competizioni di velocità. I migliori velocisti umani usano il metodo riga-e-colonna come base ma tagliano gli angoli in modo aggressivo, facendo piazzamenti parziali che annullano in seguito. È più veloce ma più difficile da imparare.
Per tutti gli altri — il metodo riga-e-colonna è il metodo.