Tetravex binario

[Snark]

Buona giornata a tutti! Potete aiutarmi?

Io e un mio amico ci siamo posti un problemino, ma non siamo riusciti a risolverlo. E' basato sul gioco del tetravex (se non ci avete mai giocato, le istruzioni sono qui: http://en.wikipedia.org/wiki/Tetravex" onclick="window.open(this.href);return false; ). In pratica ci sono un certo numero di tessere quadrate, divise in quattro settori dalle diagonali, e in ogni settore è presente un numero. Lo scopo del gioco è sistemare le tessere in una griglia nxn facendo in modo che i numeri presenti su due settori confinanti siano uguali.

Bene, c'è una griglia 4x4 che deve essere riempita con tutte le possibili tessere che si possono creare con i numeri 0 e 1. Ad esempio, se consideriamo una tessera così:
____
|\ b /|
|cXa|
|/ d \|

avremo tutte le possibili tessere abcd, ovvero 0000, 0001, 0010, ecc...

E' possibile riempire una griglia in questo modo? Se sì, potete farmi un esempio (e magari dirmi anche quante possibili combinazioni esisteranno)? E se no, perchè?

Vi ringrazio anticipatamente per l'aiuto.

[giobimbo]

Ecco una soluzione:

0...1...0...0...0...0...0...1...0...0...0...0
1...0...1...1...0...1...1...0...0...0...0...1
0...1...0...0...1...0...0...0...0...0...1...0
0...1...0...0...1...0...0...0...0...0...1...0
0...0...0...0...0...0...0...0...1...1...0...0
0...1...0...0...0...0...0...0...0...0...1...0
0...1...0...0...0...0...0...0...0...0...1...0
1...0...1...1...0...0...0...0...0...0...0...1
0...0...0...0...0...0...0...1...0...0...0...0
0...0...0...0...0...0...0...1...0...0...0...0
1...0...0...0...0...0...0...0...1...1...0...1
0...1...0...0...0...0...0...1...0...0...0...0

[giobimbo]

E, per concludere in bellezza, una soluzione simmetrica rispetto alla diagonale principale (no, non ho idea di quante siano le combinazioni possibili, non chiedetemelo):

0...1...0...0...0...0...0...0...0...0...1...0
1...0...1...1...0...1...1...0...1...1...0...1
0...1...0...0...0...0...0...1...0...0...0...0
0...1...0...0...1...0...0...1...0...0...0...0
0...0...0...1...0...0...0...0...1...0...0...0
0...1...0...0...0...0...0...0...0...0...1...0
0...1...0...0...0...0...0...0...0...0...0...0
0...0...1...1...0...0...0...0...1...1...0...0
0...1...0...0...1...0...0...1...0...0...0...0
0...1...0...0...0...0...0...1...0...0...0...0
1...0...0...0...0...1...0...0...0...0...0...0
0...1...0...0...0...0...0...0...0...0...0...0

[Snark]

Grazie mille per l'aiuto, Giobimbo...

La seconda soluzione non va: ci sono diversi settori 0 e settori 1 che confinano con settori 1... Insomma, non funziona. La prima soluzione invece e' perfetta!

In effetti mi ero fatta l'idea che il problema fosse impossibile; invece mi hai dimostrato che si puo' fare. Grazie!

Adesso bisognerebbe capire quante sono le soluzioni, ma forse questo problema e' piu' facile da risolvere con un programmino al computer che con metodi strettamente matematici...

[giobimbo]

Se si parla di programmazione devo passare la mano. Le due soluzioni le avevo trovato manualmente, usando una tabella di soli 40 triangoli invece di 64, come si vede dalla figura sotto, dove le 16 linee a ferro di cavallo corrispondono ai 16 pezzi del Tetravex, mentre i 4 circoletti su ogni linea corrispondono ai triangoli numerati, con bianco=zero e rosa=uno.
Nella seconda soluzione ho convertito i colori in numeri usando la tua convenzione, cioè a=Est, b=Nord, c=Ovest e d=Sud, convinto che non cambiasse niente e invece ne è uscito il pasticcio che mi hai fatto notare. Ecco la conversione corretta:

0...1...0...0...0...0...0...1...0...0...0...0
1...0...1...1...0...1...1...0...1...1...0...1
0...1...0...0...0...0...0...0...0...0...1...0
0...1...0...0...0...0...0...0...0...0...1...0
0...0...0...0...0...1...1...0...0...0...0...0
0...1...0...0...1...0...0...1...0...0...0...0
0...1...0...0...1...0...0...1...0...0...0...0
1...0...0...0...0...1...1...0...0...0...0...1
0...1...0...0...0...0...0...0...0...0...0...0
0...1...0...0...0...0...0...0...0...0...0...0
0...0...1...1...0...0...0...0...0...0...0...0
0...1...0...0...0...0...0...1...0...0...0...0

[Snark]

Davvero interessante il tuo metodo, complimenti!

[Gianfranco]

Ciao a tutti.

Grazie Snark per questo interessante problema.
Complimenti, come al solito, a Giobimbo per la sua potenza e velocità nel risolvere problemi combinatori.

Ho scritto un programmino in Decimal BASIC (brute force) per trovare tutte le soluzioni del problema, ma dopo 50 milioni di casi esaminati senza successo ho spento il computer.

In effetti, se non sbaglio, le possibili disposizioni di 16 elementi in un quadrato 4X4 sono:
16! = 20 922 789 888 000
quasi 21 000 miliardi.

Se riuscissimo a fare un programma che ne esamina un milione al secondo, avremmo bisogno di circa 242 giorni di elaborazione.
Il mio programma ne esamina circa un milione al minuto, perciò terminerebbe il suo compito in 40 anni, consumando un'energia di 63 miliardi di joule.

Poi ho riacceso il computer e ho chiesto al programma di esaminare la situazione partendo dalla prima delle soluzioni di Giobimbo.
In effetti, esaminando pochi milioni di combinazioni, mi ha sparato fuori un centinaio di soluzioni.
Ne riporto qui sotto alcune.

Codice: Seleziona tutto

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> OK
..1..|..0..|..1..|..0..|
1...1|1...1|1...0|0...1|
..1..|..1..|..0..|..1..|
..1..|..1..|..0..|..1..|
0...0|0...0|0...1|1...0|
..1..|..0..|..0..|..1..|
..1..|..0..|..0..|..1..|
1...1|1...0|0...0|0...1|
..0..|..0..|..1..|..0..|
..0..|..0..|..1..|..0..|
1...0|0...0|0...1|1...1|
..1..|..0..|..1..|..0..|
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> OK
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> OK
..1..|..0..|..1..|..0..|
1...1|1...1|1...0|0...1|
..1..|..1..|..0..|..1..|
..1..|..1..|..0..|..1..|
0...0|0...0|0...1|1...0|
..1..|..0..|..0..|..1..|
..1..|..0..|..0..|..1..|
1...1|1...0|0...0|0...1|
..0..|..0..|..0..|..1..|
..0..|..0..|..0..|..1..|
1...1|1...0|0...0|0...1|
..0..|..1..|..1..|..0..|
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> OK
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> OK
..1..|..0..|..1..|..0..|
1...1|1...1|1...0|0...1|
..1..|..1..|..0..|..1..|
..1..|..1..|..0..|..1..|
0...0|0...0|0...1|1...0|
..1..|..0..|..0..|..1..|
..1..|..0..|..0..|..1..|
1...1|1...0|0...0|0...1|
..0..|..1..|..0..|..0..|
..0..|..1..|..0..|..0..|
0...0|0...1|1...1|1...0|
..1..|..1..|..0..|..0..|
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> OK
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> OK
..1..|..0..|..1..|..0..|
1...1|1...1|1...0|0...1|
..1..|..1..|..0..|..1..|
..1..|..1..|..0..|..1..|
0...0|0...1|1...1|1...1|
..1..|..1..|..0..|..0..|
..1..|..1..|..0..|..0..|
1...0|0...1|1...0|0...0|
..1..|..0..|..0..|..0..|
..1..|..0..|..0..|..0..|
0...0|0...0|0...1|1...0|
..0..|..1..|..0..|..1..|
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> OK
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> OK
..1..|..0..|..1..|..0..|
1...1|1...1|1...0|0...1|
..1..|..1..|..0..|..1..|
..1..|..1..|..0..|..1..|
0...0|0...1|1...1|1...1|
..1..|..1..|..0..|..0..|
..1..|..1..|..0..|..0..|
0...1|1...0|0...1|1...0|
..0..|..1..|..0..|..0..|
..0..|..1..|..0..|..0..|
1...0|0...0|0...0|0...0|
..1..|..0..|..1..|..0..|
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> OK
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> OK
..1..|..0..|..1..|..0..|
1...1|1...1|1...0|0...1|
..1..|..1..|..0..|..1..|
..1..|..1..|..0..|..1..|
0...0|0...1|1...1|1...1|
..1..|..1..|..0..|..0..|
..1..|..1..|..0..|..0..|
0...1|1...0|0...1|1...0|
..0..|..1..|..0..|..0..|
..0..|..1..|..0..|..0..|
1...0|0...0|0...0|0...0|
..1..|..0..|..0..|..1..|
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> OK

Per velocizzare il programma bisognerebbe riuscire a potare pesantemente l'albero delle soluzioni.
Ma come fare?

Saluti a tutti.

Gianfranco

[giobimbo]

La strategia per trovare una soluzione qualsiasi è semplice: prima si trova una disposizione corretta per le quattro caselle centrali della griglia, poi con le tessere rimaste si riempiono le 12 caselle ai bordi, una dopo l'altra, in senso orario partendo dalla prima casella che segue una casella d'angolo.
Bisognerebbe quindi trovare tutte le soluzioni centrali e per ognuna di esse trovare le soluzioni laterali; potrebbe anche darsi che il numero delle soluzioni laterali sia uguale per ogni soluzione centrale...

Tutto sta a vedere se si può trasformare tale strategia in un programma per Decimal Basic.

[Gianfranco]

Grazie Giobimbo,
la tua proposta riduce decisamente il numero delle prove da fare.
Può senz'altro trasformarsi in un programma Decimal Basic.
Se riesco a combinare qualcosa, posterò qui i risultati.

Ciao
Gianfranco