Rompicapi di Alice: Generatore di labirinti

Avevo già affrontato l'argomento dei labirinti in un lontano Rompicapo, e ho pensato bene di tornare sull'argomento però da un punto di vista leggermente diverso: gli algoritmi di generazione dei labirinti.
Per generare un labirinto si parte da una griglia di celle, generalmente rettangolare, ma se ne può realizzare una di qualsiasi forma. A questa griglia si associa un percorso in cui i nodi coincidono con il centro di ciascuna cella. Lo scopo del generatore di labirinti è quello di determinare un sottografo in cui sia difficile trovare l'unico percorso che collega due nodi particolari, denominati ingresso e uscita.
Poiché la mappa del labirinto è, di fatto, un albero, ovvero un percorso che unisce un insieme di punti connessi a due a due da una e una sola linea, gli algoritmi di generazione ricadono nel campo della teoria dei grafi. Di tutti i possibili algoritmi (ce ne sono diversi) vi propongo quello basato sull'algoritmo di Kruskal, proposto nel 1956 da Joseph Kruskal⁽²⁾, fratello di Martin David⁽¹⁾. L'algoritmo si compone di questi passi:

• creazione di una foresta F, ovvero un insieme di alberi, con ciascun albero separato
• creare un insieme S con tutti i bordi del grafico
• mentre S non è vuoto ed F non è ancora ricoperto
  • rimuovere da S un bordo con peso minimo
  • se il bordo rimosso collega due alberi diversi, allora va aggiunto alla foresta F, combinando i due alberi in un unico albero

L'algoritmo che possiamo implementare a partire da quello precedente per quel che riguarda i labirinti è piuttosto semplice.
Partiamo da un reticolo \(n \times m\). Prendiamo a caso un punto sul reticolo e decidiamo di scendere o salire o di spostarci a desta o a sinistra. A questo punto se nello spospamento incontriamo una parete, la rimuoviamo. A questo punto pesciamo un altro punto, scegliamo ancora, possibilmente a caso, la direzione del movimento, e come prima rimuoviamo l'eventuale parete incontrata. Procediamo in questo modo fino a che tutti i punti del reticolo non sono connessi tra loro. In questo processo alcune delle pareti saranno scomparse, mentre altre saranno sopravvissute, lasciandoci così con la mappa di un labirinto. E più è grande il reticolo di partenza, più sarà complesso e quindi difficile il labirinto generato.
Ovviamente, per concludere l'opera nel modo classico, bisogna scegliere un punto di partenza e un punto di arrivo (magari i due estremi opposti del labirinto).
Di generatori di labirinti ce ne sono diversi. Qui vi propongo un paio di labirinti, il primo generato da mazegenerator.net:

Il secondo, invece, da printablecreative.com:

Ovviamente, se vi va, potete provare a risolvere i due labirinti e poi inviarmi le risposte, che spero siano simili a quelle che ho scaricato dai due siti. Le soluzioni usciranno in un futuro Paralipomeno.
L'ultima cosa è segnalarvi un'applicazione per Android che trovate sullo store alternativo F-Droid: Minos, un gioco tutto sommato abbastanza semplice dove bisogna trascinare una pallina dalla posizione iniziale fino alla X indicata sulla mappa generata.
Per cui, non mi resta che chiudere con il classico... Buon divertimento!

---

1. Sembra che ultimamente questa rubrica sia diventata i Roimpicapi di Kruskal! ↩
2. Kruskal, J. B. (1956). On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society. 7 (1): 48–50. doi:10.1090%2FS0002-9939-1956-0078686-7 ↩