L’Enigma degli Esagoni: Svelando i Segreti dei Puzzle Scorrevoli e la Loro Magica Parità!

Introduzione: Un Salto Oltre il Solito Quadrato!

Amici appassionati di rompicapi, chi di noi non si è mai scervellato davanti a un puzzle scorrevole? Il più famoso è sicuramente il Gioco del 15, quel quadrato magico con 15 tessere numerate e uno spazio vuoto che ci ha fatto dannare (e divertire) per generazioni. Ricordo ancora la frustrazione nel tentare di rimettere in ordine i numeri, scoprendo poi che a volte, semplicemente, non si può! Ebbene, oggi voglio portarvi in un mondo simile ma con una geometria tutta nuova e, se possibile, ancora più intrigante: quello dei puzzle scorrevoli esagonali.

Sì, avete capito bene! Dimenticate per un attimo le classiche tessere quadrate e immaginatevi tavole composte da eleganti esagoni. Come per i cugini quadrati, se la tavola è piena, non c’è gioco. Ma basta togliere qualche tessera, creando dei “buchi”, e la magia ha inizio. La domanda che ci poniamo, proprio come per il Gioco del 15, è: quali configurazioni sono risolvibili? E qui, amici miei, la cosa si fa interessante.

La Parola Chiave: Parità! Ma Esagonale è Diverso

Nel Gioco del 15, la risolvibilità è legata a una proprietà matematica chiamata parità. In soldoni, ogni mossa (scorrimento di una tessera) equivale a uno scambio di posizioni. Se per passare dalla configurazione iniziale a quella finale serve un numero dispari di scambi (una “permutazione dispari”) partendo da una configurazione che per sua natura ne richiede una pari, beh, siete di fronte a un puzzle impossibile. Il grafo del puzzle, cioè l’insieme di tutte le configurazioni raggiungibili, si divide in due “universi” separati: quello delle permutazioni pari e quello delle dispari.

Ora, penserete: “Ok, stessa storia per gli esagoni?”. E invece no, o meglio, non del tutto! Con i puzzle esagonali, le proprietà di parità diventano più complesse e dipendono in modo cruciale dalla forma della tavola e dal numero di buchi. È un po’ come passare da una partita a dama a una a scacchi tridimensionali: le regole di base ci sono, ma le possibilità esplodono!

Una delle scoperte più affascinanti che abbiamo fatto è che per tavole esagonali sufficientemente grandi, che abbiano forma di esagono, triangolo o parallelogramma, se ci sono tre o più buchi, allora tutti i puzzle sono risolvibili! Immaginate, è come se il Gioco del 15 diventasse sempre risolvibile togliendo non una, ma due tessere in più. Questa proprietà si chiama connessione massimale del grafo del puzzle: da qualsiasi configurazione (non isolata, cioè dove almeno una mossa è possibile) si può raggiungere qualsiasi altra.

Due Buchi: La Sfida degli “Angoli Stretti”

Ma cosa succede se abbiamo solo due buchi? Qui la situazione si complica e ricorda più da vicino il classico Gioco del 15, ma con delle peculiarità tutte esagonali. La risolvibilità dipende sì dalla parità, ma anche da un altro fattore: la posizione delle tessere negli “angoli stretti” della tavola. Un “angolo stretto” è una tessera che ha esattamente due vicini. Pensate a un parallelogramma: ha due angoli così. Un triangolo ne ha tre. I puzzle a forma di “fiore” (un esagono fatto di esagoni) invece, non ne hanno!

Il problema è che una tessera in un angolo stretto può rimanere “incastrata”. Per muoverla, i due buchi devono essere proprio lì accanto. Ma una volta mossa, o torna al suo posto, o lascia il buco nell’angolo, e solo lei può muoversi per riempire quel buco o l’altro. Questo comportamento non si vede nei puzzle quadrati e aggiunge un livello di complessità notevole.

Per studiare meglio questo fenomeno, abbiamo introdotto il concetto di “tavole rifilate”: in pratica, togliamo questi angoli stretti. E cosa scopriamo? Che queste tavole rifilate, con due buchi, si comportano in modo molto simile al Gioco del 15, mostrando una “proprietà di parità forte”. Ciò significa che il loro grafo del puzzle si divide nettamente in due componenti, determinate appunto dalla parità delle permutazioni delle tessere.

Per le tavole a parallelogramma e triangolari non rifilate, con due buchi, il numero di componenti connesse del grafo del puzzle (cioè, quanti “universi” di puzzle irraggiungibili tra loro esistono) diventa molto più grande, proprio a causa di queste tessere che possono rimanere bloccate negli angoli.

Capire la Complessità: il “Numero di Dio”

Un altro aspetto che ci affascina è la complessità di un puzzle. Come la misuriamo? Con il numero minimo di mosse per passare da una configurazione all’altra. Il massimo di queste distanze, tra tutte le coppie di configurazioni possibili su una data tavola, è chiamato il “Numero di Dio”. Per il Gioco del 15, è 80. Trovare questo numero per tavole più grandi o di forme diverse è un problema difficilissimo, addirittura NP-Hard per le tavole quadrate!

Anche per i nostri amici esagonali, abbiamo iniziato a calcolare dei limiti per il Numero di Dio su tavole piccole, usando algoritmi come il Breadth-First Search (BFS). È come esplorare un labirinto partendo da un punto e segnando tutte le strade possibili, strato dopo strato, fino a trovare il punto più lontano.

Come Sveliamo Questi Misteri? Teoremi e Computer

Vi chiederete come facciamo a dimostrare queste cose. Usiamo un mix di matematica tosta e potenza di calcolo. Ad esempio, c’è un risultato che chiamo il “Lemma di Coniugazione”: se voglio dimostrare che posso passare da una configurazione C a una C’ (che è C con due tessere scambiate), mi basta trovare una qualsiasi configurazione C1 raggiungibile da C, tale che anche C1 con le stesse due tessere scambiate sia raggiungibile da C1. Sembra un giro di parole, ma è potentissimo!

Poi c’è il “Teorema di Incollaggio” (Patching Theorem). Immaginate di avere due tavole più piccole di cui conoscete le proprietà (ad esempio, sapete che con 3 buchi sono massimamente connesse). Se potete “incollare” queste due tavole in modo che si sovrappongano abbastanza, allora anche la tavola più grande risultante manterrà quelle belle proprietà! È così che dimostriamo la connessione massimale per tavole a forma di fiore o triangolari grandi: le costruiamo incollando parallelogrammi più piccoli, di cui conosciamo già il comportamento.

Per le tavole piccole, invece, ci affidiamo a simulazioni al computer. Scriviamo codice (Python, nel nostro caso) che esplora sistematicamente tutte le mosse possibili a partire da una configurazione, per capire quante altre configurazioni sono raggiungibili, quante componenti ha il grafo del puzzle, e per stimare il Numero di Dio. È un lavoro certosino, ma i risultati sono incredibilmente illuminanti.

Ad esempio, abbiamo scoperto che una tavola a parallelogramma 2xM2 (due colonne di M2 esagoni) si comporta in modo molto simile a una striscia 1xM2 di quadrati: le tessere possono solo scorrere avanti e indietro senza cambiare il loro ordine relativo, creando (M1M2-h)! componenti connesse (dove h è il numero di buchi). Sorprendente, vero?

Parità Debole e Forte: Una Sottile Differenza

Abbiamo parlato di “proprietà di parità debole” e “forte”. Cosa significano?

• Proprietà di parità debole: Se due configurazioni sono nella stessa componente connessa (cioè, puoi passare da una all’altra), allora la permutazione delle tessere per trasformare una nell’altra deve essere pari. Ma non garantisce che tutte le permutazioni pari siano raggiungibili.
• Proprietà di parità forte: Non solo vale la debole, ma il grafo del puzzle ha esattamente DUE componenti connesse. Una contiene tutte le configurazioni raggiungibili con permutazioni pari, l’altra quelle con permutazioni dispari (sebbene quest’ultima sia spesso irraggiungibile se si parte da una configurazione “standard”). È il caso del Gioco del 15.

Abbiamo dimostrato che le tavole a parallelogramma con due buchi hanno la proprietà di parità debole. E, cosa ancora più interessante, le tavole a fiore, i parallelogrammi rifilati e i triangoli rifilati (con due buchi) hanno la proprietà di parità forte! Sono una nuova famiglia di puzzle che si comportano in modo molto simile al classico Gioco del 15.

Oltre il Gioco: Topologia e Spazi di Configurazione

Tutto questo studio non è fine a se stesso. Il grafo del puzzle è un modello discreto per qualcosa di più grande e continuo: lo spazio delle configurazioni. Immaginate che le tessere possano muoversi liberamente sulla tavola, senza sovrapporsi. L’insieme di tutte queste posizioni possibili forma uno spazio topologico. Per i puzzle quadrati, si è visto che a volte questo spazio “si ritrae” sul grafo del puzzle, come se il grafo ne fosse lo scheletro.

Capire la combinatoria del grafo del puzzle dei nostri amici esagonali potrebbe quindi aprirci le porte a una comprensione più profonda della topologia di questi spazi di configurazione più complessi. È un campo di ricerca attivo e pieno di sorprese, dove la matematica pura incontra il piacere del gioco.

Spero che questo viaggio nel mondo dei puzzle scorrevoli esagonali vi abbia incuriosito almeno quanto affascina me. È la dimostrazione che anche dietro a un semplice gioco possono nascondersi strutture matematiche profonde e bellissime. E chissà, magari la prossima volta che vedrete un esagono, penserete a tutte le permutazioni possibili!

Fonte: Springer