Contiamo le soluzioni dei Sexomini

Puzzle dei Sexomini

Quante soluzioni ha il puzzle di 6x4 Sexomini non rovesciabili?

147.928
rotazioni e riflessioni escluse
Pierpaolo Bernardi - 2 Luglio 2001


Non mi sembravano tante la prima volta.
Il problema e' probabilmente risolvibile in vari modi, nessuno dei quali facilmente. Se pensate di eseguire tutte le 24! permutazioni ruotando ogni sexomino nelle posizioni possibili, otterrete 3x10^36 combinazioni. Se avete un super PC che le esamini al ritmo di 1/nanosec, impiegherete 10^17 secoli. Qualcuno ci sta provando, potando molti molti rami secchi. Se volete provare a fare un programma ad hoc, tenete conto che:
1) soltanto 7 pezzi possono occupare gli angoli;
2) i pezzi full-sexed possono occupare solo i posti centrali;
3) i pezzi tri-sex non possono entrare nei posti centrali.


Giugno 2001 - Pierpaolo Bernardi sta tentando di risolvere il problema globale con un programma scritto in Common Lisp. Pare che sia vicino ad ottenere una soluzione al secondo. Se la mia stima di 250.000 probabili soluzioni e' attendibile, dovrebbe trovarle tutte in meno di tre giorni di calcoli continui!


2 Luglio 2001 - Pierpaolo ha concluso i suoi calcoli. Ecco le sue conclusioni:
...il numero di soluzioni, senza riflessioni di 147.928, quindi 295.586 soluzioni totali. [Poiche' i pezzi sono per definizione non-rovesciabili, ogni riflessione e' in realta' un'altra soluzione. Noi, in seguito, per brevita' considereremo solo le soluzioni escluse le rotazioni e le riflessioni.]
Sono bastate circa 12 ore di calcolo.
Classificandole in base alla posizione del pezzo neutro si possono ripartire come segue:

71.992 hanno il pezzo neutro in (1,1)
8.688 in (1,2)
5.928 in (3,1)
61.320 in (2,1)


In questo file potete trovare il programma in Common Lisp di Pierpaolo.

Qualcuno vuol confermare questi dati?


6 Agosto 2001 - Tocca al sottoscritto la verifica:

Con il solito Gerard's Polyomino Solution Engine, bloccando il pezzo neutro in posizione (1,2) e poi in posizione (3,1) verifico facilmente i blocchi di 8.688 e 5.928 soluzioni.
Con il neutro in (2,1) riesco anche a confermare le 61.320 soluzioni, grazie ad alcuni artifici, ad un Pentium con clock di 1 GHz e ad un weekend di tempo macchina.
Ma l'analogo tentativo con il neutro in (1,1) provoca inevitabilmente l'inchiodamento della macchina dopo due giorni e una notte di lavoro. (Credo di aver individuato l'inconveniente in una protezione eccessiva di Microsoft in Internet Explorer: quando le soluzioni superano un certo numero, il sistema fa ricorso alla memoria virtuale, ma poiche' Java non deve scrivere sul disco, scatta la protezione).
La soluzione arriva con le... ferie:

L'importanza dell'ermafrodita

Sostituiti i lati sessuati con lati ermafrodita, cerco le soluzioni con neutro(1,1). Esse sono solo 10 (40 per il pezzo neutro in posizione qualunque):

Sexomini ermafroditi


Queste vengono utilizzate come matrici dove i pezzi omologhi sono permutati solo tra loro, ottenendo un'accelerazione iperbolica. Sotto potete vedere come l'utilizzo di chiavi possa forzare un solver a permutare i pezzi solo dove servono:

Matrice 1
Matrice 1


Matrice Nr. Sol.
19312
27424
38688
46500
56044
67120
76796
86244
96760
107104
Totale: 71992

Le 71.992 soluzioni con il pezzo neutro in (1,1) sono quindi confermate. Il tempo macchina e' stato inferiore alla mezz'ora in tutto, con il solito solver in Java, chissa' cosa potrebbe diventare con un prg. ad hoc. Il metodo e' generalizzabile per tutte le altre sex-forms, anche per quelle che aspettano soluzioni... :o)


La transessualita' dei Sexomini

Un'ultima osservazione di Pierpaolo: invertendo contemporaneamente tutti i sessi ad una soluzione, se ne ottiene un'altra che non e' una rotazione o una riflessione della precedente. Si dovrebbe quindi poter dimezzare ulteriormente il tempo di ricerca:

Inversione dei sessi
Cambiamento di sesso


L'osservazione di Pierpaolo ha numerose implicazioni. In primis, e' da molto tempo che mi chiedo (e chiedo ai NG :) una spiegazione del fatto che il numero delle soluzioni di tutti i sottoinsiemi osservati finora sia pari: la nota di Pierpaolo e' la risposta.
Mi e' poi capitato questo busillis: nel cercare le 61.320 soluzioni col neutro in (2,1) ho notato che in (1,1) poteva starci solo uno dei due monosessuati. Ho spezzato quindi il problema in due, imponendo in (1,1) prima la femmina e poi il maschio. Ho ottenuto due gruppi di 30.660 soluzioni cadauno e mi sono stupito di tanta simmetria: ora so il perche'!
Notiamo infine che questa transessualita' e' applicabile a tutte le Polysexes e in particolare ai SexeHexeS di cui possiamo ottenere altre soluzioni partendo dalle pochissime note.


Strategia ottimale

[IMHO] Ad oggi la strategia migliore per calcolare il numero delle soluzioni credo che sia la seguente: precalcolate le 40 matrici di ermafrodita, usarle per trovare 40 gruppi di soluzioni dove si potranno scambiare i pezzi soltanto tra quelli omologhi: 4 angolari, 3 bisex, 8 trisex e 6 full-sexed. L'ideale e' usare un buon linguaggio di programmazione compilabile. I due monosex potranno essere fissati in modo arbitrario: il numero delle soluzioni potra' essere moltiplicato per due, grazie alla simmetria transessuale. Se tanto mi da tanto, scommetto che si puo' abbattere il tempo di elaborazione a qualche minuto!

_________________


Classificazione di Dario Uri

Prospetto sexomini



Alla luce della soluzione di Pierpaolo, questa strada puo' apparire laboriosa. Resta cmq. una strada percorribile che richiederebbe solo qualche volontario per essere completata. Dario Uri propose sul NG it.hobby.enigmi di spezzare il problema in 510 sottocasi, bloccando di volta in volta i pezzi d'angolo. Nacque la tabella qua sotto. Chissa' se un giorno riusciremo a vederla completata?


Indice ABCD N.Sol. Autore N.Sol. Autore N.Sol. Autore
11o2o340LZ----
21o2o430LZ----
31o32o40LZ----
.....................----
1271v2o419566Dario Uri----
1281v2o194258Dario Uri----
1291v42o190Dario Uri----
1301v4192o410Dario Uri----
1311v192o40Dario Uri----
1321v1942o414Dario Uri----
1331o2v419184LZ184Dario Uri--
1341o2v194460LZ460Dario Uri--
1351o42v19256Dario Uri----
1361o4192v310Dario Uri----
1371o192v4184Dario Uri----
1381o1942v506Dario Uri----
1391v2v419378Dario Uri----
1401v2v194744Dario Uri----
1411v42v190LZ0Dario Uri--
1421v4192v936Dario Uri----
1431v192v40LZ0Dario Uri--
1441v1942v1288Dario Uri----
.....................----
1751v2o619324Dario Uri----
1761v2o196390Dario Uri----
1771v62o19232Dario Uri----
1781v6192o176Dario Uri----
1791v192o6236Dario Uri----
1801v1962o268Dario Uri----
1811o2v619390Dario Uri----
1821o2v196324Dario Uri----
1831o62v19236Dario Uri----
1841o6192v176Dario Uri----
1851o192v6232Dario Uri----
1861o1962v268Dario Uri----
1871v2v619498Dario Uri----
1881v2v196498Dario Uri----
1891v62v190LZ0Dario Uri--
1901v6192v748Dario Uri----
1911v192v60LZ0Dario Uri--
1921v1962v700Dario Uri----
.....................----
5074196240LZ----
5084192460LZ----
5094246190LZ----
5104241960LZ----

(Download della tabella completa... da completare.)

Saro' felice di ricevere soluzioni parziali, totali, stime statistiche, osservazioni, verifiche, etc....


Chi non sapesse da che parte cominciare, puo' fare il download di un mio programmino che aiuta:

http://members.theglobe.com/liviozucca/download/gerard1.zip

E' gratis (freeware) [1.5MB, ci vogliono 5..10 min di pazienza]. Lo potete unzippare con Winzip o equivalente e poi lanciate Setup.exe per installarlo. E' la versione 1.0 con un failetto di help in italiano.


Dario Uri ha anche trovato il numero di soluzioni, escludendo rotazioni e riflessioni, di ciasun sotto-rettangolo:

Indice RettangoloN.soluzioni
1 2x23
2 2x372
3 2x4562
4 3x31.337
5 2x53.610
6 3x479.126
7 2x615.302
8 3x5821.274


Qua sotto il solver di Gerard Putter tenta di trovare le soluzioni approssimando i sexomini con normali polimini:

Gerard's Solver




_________________

First edition: Jun 28th, 2001 - Last revision: Aug 13th, 2001

Separator

Home liviozucca@tiscalinet.it

| HOME |
| e-mail | Download | Links | Chronicle |

| PENTOMINOES |
| More about pentominoes | The cube | 3D pentominoes | Maximizing |

| POLYSEXES |
| Sexominoes | Xominoes | Zucca's Puzzle | Domino Puzzle | SexCubes | Dodecaculeus | Tubominoes |

| SEXEHEXES |
| SexeHexeS For Sale | More about SexeHexeS | How we did it | Other Sexehex Puzzle | My Solution | Reproduction |

| POLYMULTIFORMS |
| Aug 2000 edition | May 2000 edition | PolyEdges | To cover a solid | Fourier Series of a Square | Order 13 Perfect Square | Fibonacci Machine |

Separator

Qui sotto c'e' una copia del sito di Livio Zucca. Clicca qui per tornare alle mia home