COOKIES: Se continui a visitare questo sito, acconsenti al loro utilizzo. OK o Dettagli

Quadrati massimali di polimini

Qui consideriamo il problema, data una classe di polimini, ad esempio i pentamini, di tassellare il quadrato piu' grande possibile.

Il problema e' banale per il monomino e impossibile per domino e trimini. Per quanto riguarda i tetramini, l'unica soluzione (piuttosto insoddisfacente) e' quella costituita dal tetramino quadrato. Infatti non c'e' modo di combinare 4 tetramini per formare un quadrato 4 4.

Le cose cominciano a farsi interessanti, anche se ancora abbastanza semplici, quando entrano in gioco i pentamini, gli esamini e gli eptamini. I quadrati massimali hanno lati rispettivamente 5, 12 e 21.

Con gli ottomini le cose cominciano a farsi piu' complicate (almeno per i miei poveri mezzi...). Con qualche sforzo sono riuscito ad ottenere due quadrati massimali, uno 52 52 che utilizza 338 ottomini e uno 53 53 che, ai limiti del regolamento, sfrutta 350 ottomini "pieni" piu' uno dei sei ottomini "bucati" posto al centro:

Coi gli enneomini (i 9-polimini) dovrebbe essere possibile usarne 1225 senza buchi per formare un quadrato 105 105, che al momento pero' rimane ancora sconosciuto. Conclude questa galleria di risultati il capolavoro di Livio Zucca, un quadrato 210210 formato da ben 4410 decamini! Ho ridotto e 4-colorato la figura qui sotto, ma potete anche vedere la figura originale di Livio Zucca in bianco e nero e lievemente piu' grande.

Per ottenere questo risultato impressionante, Livio ha adottato una strategia mista: un programma da lui scritto appositamente ha costruito una soluzione parziale contenente quasi tutti i pezzi. Il programma era costruito in modo da richiedere l'intervento umano (o sovrumano!) di Livio tutte le volte che si imbatteva in un vicolo cieco. Dopo decine e decine di pazienti iterazioni uomo-macchina, l'ultima (piccola) parte dello schema e' stata completata per mezzo di un normale solutore.