Vi siete persi in un labirinto? Ecco i geniali modi per uscirne sempre

I labirinti, elaborati intrecci di sentieri, tipicamente fiancheggiati da alte mura di pietra o siepi per impedire all'avventore di individuare una via di uscita, hanno affascinato l'uomo da migliaia di anni, e ancora oggi non smettono di farlo. Molti sono i labirinti costruiti dall'uomo le cui tracce sono arrivate sino ai giorni nostri: basti pensare che Erodoto narrava di un labirinto a Faiyum, in Egitto, ritrovato solo due secoli fa attraverso spedizioni archeologiche che ne hanno datato la costruzione attorno al 1800 avanti Cristo.

I labirinti sono stati fonte inesauribile di opere di finzione, dal mito di Cnosso al film Maze Runner, passando per il racconto Il giardino dei sentieri che si biforcano di Borges. Questo d'altronde si spiega facilmente poiché, oltre l'elegante struttura estetica, la funzione primaria di un labirinto di rendere complicato trovarne l'uscita si presta molto bene come incipit di una storia.
Ciò che non molti sanno è che la scienza può venire incontro a un povero personaggio perdutosi al suo interno: ci sono infatti molti algoritmi di risoluzione dei labirinti, che portano, prima o poi, ad uscirne. Vediamone dunque alcuni esempi che, chissà, magari potrebbero tornarvi utili (a proposito, visto che ci siamo, riuscite a risolvere questo labirinto?).

Seguire il muro

La regola del wall-following è il più semplice metodo per uscire da un labirinto, ed è anche quello più noto. Pur funzionando solo con i labirinti meno complessi, è un interessante esempio di come si possa affrontare la risoluzione di un tale problema.

Assumiamo che il labirinto sia semplicemente connesso, ovvero che ogni parete sia collegata al confine esterno del labirinto. Dunque, se guardiamo la mappa del labirinto dall'alto, non possono esserci pezzi di parete isolati e scollegati dalle altre pareti. In questo caso la regola suggerisce ad un avventore appena entrato nel labirinto di poggiare semplicemente la propria mano, destra o sinistra, su di una parete e continuare a camminare senza mai staccare la mano dal muro. Se il labirinto presenta un'uscita allora la regola garantisce di arrivarci, altrimenti la persona percorrerà ogni corridoio almeno una volta per poi tornare all'entrata.

La domanda, a questo punto, sorge spontanea: perché questa regola funziona e permette di uscire dai labirinti semplicemente connessi? La ragione è matematica o, più precisamente, topologica. La topologia è una branca della matematica che richiederebbe forse troppo tempo per essere introdotta, ma si può averne una buona intuizione pensando che il topologo, a differenza del geometra, studia oggetti con la libertà di deformarli, come se fossero fatti di gomma elastica. Per un topologo, quindi, un cubo e una sfera sono equivalenti.

Gli spazi semplicemente connessi sono particolarmente semplici da trattare in topologia. Per esempio, tramite opportune deformazioni, un labirinto semplicemente connesso può essere deformato in un cerchio. Come mostrato nel video appena sopra, percorrere un labirinto è topologicamente equivalente a spostarsi da un punto di una circonferenza a un altro e quindi si può completare semplicemente muovendosi lungo la circonferenza che, dopo le deformazioni, è diventata l'unica parete.

L'algoritmo di Trémaux

Purtroppo, o per fortuna, non tutti i labirinti sono semplicemente connessi e quindi la regola del wall-following risulta inutilizzabile con strutture un po' più complesse.

Per questo motivo, si rende necessario un metodo che prescinda dalla semplicità del labirinto e che possa funzionare sempre, o quasi. Per nostra fortuna, viene in nostro aiuto l'algoritmo inventato da Charles Pierre Tremaux nel diciannovesimo secolo, che consiste nel lasciare delle tracce, come nella fiaba di Pollicino.
Anche questo algoritmo richiede delle piccole condizioni strutturali sul labirinto, ma lo vedremo in seguito. Le regole da seguire sono poche e semplici. Occorre lasciare una traccia su di ogni corridoio attraversato, per esempio una linea con una penna da quando lo si imbocca a quando lo si lascia. Non bisogna mai percorrere un corridoio che è stato segnato due volte e, se si arriva a un incrocio dove si trovano due o più corridoi non segnati, se ne può scelgiere uno a caso. Altrimenti, se il percorso da cui si arriva ha un solo segno, bisogna girarsi, tracciare un nuovo segno e tornare indietro. Se invece il percorso da cui veniamo ha già due segni dobbiamo scegliere e segnare in maniera arbitraria uno degli altri sentieri. Perfino queste semplici cellule riescono a completare i labirinti più difficili al mondo.

Il video in alto offre un chiaro esempio di come l'algoritmo funzioni, ed è chiaro che non sempre seguendo le regole di Tremaux si riesca a seguire la strada più breve per giungere all'uscita, anzi. Risulta però intuitivo capire come l'algoritmo possa effettivamente portare a una soluzione, visto che l'avventore del labirinto non camminerà mai più di due volte su di uno stesso corridoio e quindi eviterà di incorrere in pericolosi loop, come invece potrebbe accadere seguendo la regola del wall-following in labirinti non semplicemente connessi.
L'unica cosa a cui stare attenti quando si applica l'algoritmo di Tremaux è che le curve all'interno del labirinto siano sempre di 90 gradi, e che non ci siano larghi spazi vuoti, altrimenti l'algoritmo potrebbe non funzionare.

Questi sono solamente due modi per uscire da un labirinto, ma ce ne sono anche altri più raffinati, come il Pledge algorithm, che richiede un'attenzione particolare nel contare gli angoli che si ruotano ad ogni svolta oppure l'utilizzo di una bussola. Altre soluzioni sfruttano metodi molto più grezzi, come il Random mouse algorithm, che suggerisce solamente di scegliere a caso la direzione giusta a ogni svolta e può ovviamente richiedere tempi molto lunghi per uscire da un labirinto anche relativamente semplice. La realtà però è che non ci sono algoritmi che funzionano per ogni labirinto: ci sono sempre dei requisiti di partenza che devono essere soddisfatti. Forse, però, è proprio l'irresolubilità dei labirinti che ci affascina e che ha contribuito a renderli le attrazioni che sono oggi.