{"id":583,"date":"2011-05-05T01:33:16","date_gmt":"2011-05-05T00:33:16","guid":{"rendered":"http:\/\/julia2.lucaamore.com\/?p=583"},"modified":"2025-11-29T20:23:47","modified_gmt":"2025-11-29T18:23:47","slug":"cammelli-labirinti-e-depth-first-search-realizzazione-di-un-generatore-e-risolutore-di-labirinti-in-perl","status":"publish","type":"post","link":"https:\/\/www.lucaamore.com\/?p=583","title":{"rendered":"Cammelli labirinti e depth-first search: realizzazione di un generatore e risolutore di labirinti in Perl"},"content":{"rendered":"\n
\n
\"\"<\/a><\/figure>\n<\/figure>\n\n\n\n

Se T\u00e9seo<\/a> (\u0398\u03b7\u03c3\u03b5\u03cd\u03c2), eroe spregiudicato nonch\u00e8 figlio del re ateniese \u00c8geo<\/a> (\u0391\u1f30\u03b3\u03b5\u03cd\u03c2), avesse conosciuto qualche rudimento di Perl, avrebbe potuto risolvere brillantemente il problema del Labirinto di Cnosso<\/a> adottando l’algoritmo deep-first search<\/a>, sconfiggere il Minotauro<\/a> (\u039c\u03b9\u03bd\u03ce\u03c4\u03b1\u03c5\u03c1\u03bf\u03c2) Asterione ma – soprattutto – non avrebbe spezzato il cuore della povera Arianna<\/a> (\u0391\u03c1\u03b9\u03ac\u03b4\u03bd\u03b7), figlia di Minosse e Pasifae (ed anche madre del Minotauro), seducendola per ottenere il risolutivo gomitolo di filo rosso (un surrogato di stack analogico ideato da Dedalo<\/a> ) per poi abbandonarla ancora dormiente nell’isola deserta di Nasso<\/a> (pare pure dopo una lunga notte di “festeggiamenti” nella sua nave).<\/p>\n\n\n

\n
\"\"<\/a>
labirinto 20 x 20 generato da maze.pl<\/figcaption><\/figure>\n<\/div>\n\n\n

A chi mi obietta – ingiustamente – che ai tempi non era disponibile un interprete Perl cos\u00ec come un notebook agevolmente trasportabile in un Labirinto, ma anche a tutti gli altri che gridano vendetta contro il comportamento di T\u00e9seo nei confronti della povera Arianna, consiglio vivamente la lettura dell’avvincente leggenda del Minotauro<\/a>; scoprirete che la storia di T\u00e9seo, per opera di Poseidone, si conclude in modo tragico a causa dell’inversione di un’informazione booleana (1 bit) ma vitale: il colore delle vele della sua imbarcazione.<\/p>\n\n\n\n

Dopo questa mitologica premessa, certo di esser perdonato per eventuali errori sulla mitologia greca, sperando di non deludere il forse unico temerario lettore che avr\u00e0 avuto l’ardore di proseguire nella lettura di questo articolo, vi presento un semplicissimo generatore e risolutore di labirinti scritto interamente in Perl<\/strong>.<\/p>\n\n\n\n

\"\"<\/a>
Labirinto 60 x 40 generato da maze.pl<\/figcaption><\/figure>\n\n\n\n

Questo progetto \u00e8 ispirato da un articolo<\/a> che ho letto nel blog di Eriol in cui il problema viene affrontato in Python.<\/p>\n\n\n\n

In rete esistono anche molti riferimenti sui labirinti (storia, classificazione, generazione, risoluzione, miti e leggende) dove \u00e8 piacevole perdersi:<\/p>\n\n\n\n