Newsgroup: it.hobby.enigmi
Titolo: Le tessere del domino

Ho proposto sul sito questo puzzle nell'aprile del 2000,
ma le soluzioni cominciano ad arrivare solo adesso.
Si tratta di coprire una scacchiera 8x7 con le 28 antiche
tessere del domino. Ciamato "Testa" il lato piu' corto di
ciascun domino, le regole sono le seguenti:
1) Non deve esserci nessun contatto testa-testa.
2) OGNI contatto testa-fianco, ove siano presenti i numeri,
deve far combaciare numeri uguali, quindi l'unica eccezione 
e' lo zero (numero mancante) che puo' fare da jolly.
3) A puzzle completato, si conta il valore delle teste sul 
perimetro: nell'esempio sotto le uniche teste sul perimetro 
sono 6,2,5, quindi perimetro=6+2+5+...
Vince chi fa il perimetro piu' basso.
+---+---+---+---+---+---+---+---+
| 2 | 2   5 | 5 | 5   3 |       |
+   +---+---+   +---+---+   +   +
| 6 | 6   2 | 2 |               |
+---+---+---+---+---+   +   +   +
| 6   2 | 2 | 0   3 |           |
+---+---+   +---+---+   +   +   +
| 0 |   | 4 |                   |
+   +   +---+   +   +   +   +   +
| 2 |                           |
+---+   +   +   +   +   +   +   +
|                               |
+   +   +   +   +   +   +   +   +
|                               |
+---+---+---+---+---+---+---+---+
Ciao  :o)
Livio Zucca
----------------------------------
GIU' LE MANI DA INTERNET!
http://www.geocities.com/liviozuc
PS: Per vedere l'ascii-art usare caratteri fissi (es: Courier)
-- 
Posted from 
mail-1.tiscalinet.it
 [195.130.225.147] 
via Mailgate.ORG Server - 
http://www.Mailgate.ORG

 Vince chi fa il perimetro piu' basso.
Ma quante pagine hai ? questa non l'avevo ancora vista.
Ne butto li' una trovata con qualche tentativo a mano. 
 +---+---+---+---+---+---+---+---+
 | 5   5 | 0 | 4 | 4   4 | 0 | 2 |
 +---+---+   +   +---+---+   +   +
 | 5 | 5 | 2 | 3 | 4 | 4 | 6 | 2 |
 +   +   +---+---+   +   +---+---+
 | 6 | 2 | 2 | 3 | 0 | 6 | 6   2 |
 +---+---+---+---+---+---+---+---+
 | 0   0 | 2 | 3 | 3   6 | 6 | 2 |
 +---+---+   +   +---+---+   +   +
 | 3   0 | 4 | 5 | 5   1 | 1 | 1 |
 +---+---+---+---+---+---+---+---+
 | 3 | 4 | 4   5 | 5 | 1 | 1   1 |
 +   +   +---+---+   +   +---+---+
 | 3 | 1 | 1   3 | 0 | 0 | 6   6 |
 +---+---+---+---+---+---+---+---+
alto    4+2 = 6
basso   3+1 = 4
sx      5+3 = 8
dx    2+1+6 = 9
Tot 27
Siccome il 27 e' saltato fuori a caso, senz'altro e' lontano
dalla soluzione ottimale, ma tanto per cominciare...
:) ciao dario

PS: Per vedere l'ascii-art usare caratteri fissi (es: Courier)
Courier  --The Best!!
-- 
Ci sentiamo  |  Remigio Zedda  || Attenzione! campo "From:" alterato
ciao Remigio |                 ||==> E-mail: 
remi...@tiscalinet.it
-------------|      ..si` d'accordo.. ma con la Deb e` un'altra cosa!
/* Linux 2.2.17 su Debian GNU/Linux 2.2 Potato */

 ma le soluzioni cominciano ad arrivare solo adesso....
Adesso mi spiego il motivo...
;-))
Cmq nel momento che posto questo msg vedo che iniziano
ad arrivare le prime soluzioni .... ma a me piacerebbe
trovare, se possibile, una soluzione non "brute force"
anche perche' quasi sicuramente tale soluzione non e'
ottenibile prima di qualche anno...
Vediamo su cosa ho ragionato io, magari potrebbe essere
d'aiuto per qualcuno. Non si puo' mai dire...a volte capita.
Non avendo programmi per trovare tutte le soluzioni possibili
per il posizionamento delle tessere, ho cercato di "potare"
quanto possibile.
1) Sappiamo che le 4 tessere angolari creano in ogni caso
   una presenza di 1 testa sul perimetro, per cui non e' li
   che dobbiamo ottimizzare lo schema ma nelle rimanenti parti.
2) Se guardiamo la scacchiera con la base di lato 8 possiamo
   avere 8 differenti posizioni delle tessere angolari, evitando
   rotazioni e riflessioni, ma solo 4 di esse possono essere
   soluzioni valide perche' le altre 4 prevedono che su almeno
   uno dei due lati corti ci siano due tessere verticali tali da
   lasciare solo 3 caselle libere che possono essere a loro
   volta riempite da una tessera orizzontale ed una verticale
   e questo e' in opposizione alla condizione 1).
3) Ecco i quattro schemi per chi ha seguito fin'ora....Li chiamo 
   in maniera univoca leggendo prima gli spazi vuoti in alto ed
   in basso e poi quelli vuoti a sx ed a dx.
Schema: 4455
+---+---+---+---+---+---+---+---+
|       |               |       |
+---+---+   +   +   +   +---+---+
|                               |
+   +   +   +   +   +   +   +   +
|                               |
+   +   +   +   +   +   +   +   +
|                               |
+   +   +   +   +   +   +   +   +
|                               |
+   +   +   +   +   +   +   +   +
|                               |
+---+---+   +   +   +   +---+---+
|       |               |       |
+---+---+---+---+---+---+---+---+
Schema: 4545
+---+---+---+---+---+---+---+---+
|       |               |       |
+---+---+   +   +   +   +---+---+
|                               |
+   +   +   +   +   +   +   +   +
|                               |
+   +   +   +   +   +   +   +   +
|                               |
+   +   +   +   +   +   +   +   +
|                               |
+---+   +   +   +   +   +   +   +
|   |                           |
+   +   +   +   +   +   +---+---+
|   |                   |       |
+---+---+---+---+---+---+---+---+
Schema: 5544
+---+---+---+---+---+---+---+---+
|       |                   |   |
+---+---+   +   +   +   +   +   +
|                           |   |
+   +   +   +   +   +   +   +---+
|                               |
+   +   +   +   +   +   +   +   +
|                               |
+   +   +   +   +   +   +   +   +
|                               |
+---+   +   +   +   +   +   +   +
|   |                           |
+   +   +   +   +   +   +---+---+
|   |                   |       |
+---+---+---+---+---+---+---+---+
Schema: 4644
+---+---+---+---+---+---+---+---+
|       |               |       |
+---+---+   +   +   +   +---+---+
|                               |
+   +   +   +   +   +   +   +   +
|                               |
+   +   +   +   +   +   +   +   +
|                               |
+   +   +   +   +   +   +   +   +
|                               |
+---+   +   +   +   +   +   +---+
|   |                       |   |
+   +   +   +   +   +   +   +   +
|   |                       |   |
+---+---+---+---+---+---+---+---+
...Non e' molto ma e' un buon metodo per tagliare "tante"
combinazioni inutili. Ma non e' tutto...
Infatti analizzando i possibili riempimenti degli spazi vuoti
del perimetro possiamo subito verificare quali siano quelle
che consentono una minore presenza di "teste". 
Infatti, in accordo con le regole date, sappiamo che...:
a)
Gli spazi di lato 4 possono prevedere due possibili riempimenti:
+---+---+---+---+      +---+---+---+---+
|       |   |   |      |   |       |   |
+---+---+   +   +      +   +---+---+   +
        |   |   |      |   |       |   |
        +---+---+      +---+       +---+
b)
Gli spazi di lato 5 possono prevedere due possibili riempimenti:
+---+---+---+---+---+     +---+---+---+---+---+
|       |   |       |     |   |       |   |   |
+---+---+   +---+---+     +   +---+---+   +   + 
        |   |             |   |       |   |   |
        +---+             +---+       +---+---+
c)
Gli spazi di lato 6 possono prevedere tre possibili riempimenti:
+---+---+---+---+---+---+   +---+---+---+---+---+---+
|       |   |       |   |   |   |   |       |   |   |
+---+---+   +---+---+   +   +   +   +---+---+   +   + 
        |   |       |   |   |   |   |       |   |   |
        +---+       +---+   +---+---+       +---+---+
+---+---+---+---+---+---+
|       |   |   |       |
+---+---+   +   +---+---+
        |   |   |
        +---+---+
Si verifica "a mano" che l'ultimo schema proposto "4644"
prevede ben 12 "teste" a fronte di sole 10 "teste" presenti
negli altri schemi precedenti, per cui .... mi son detto:
"Minore quantita' di addendi == Minore valore perimetro".
Almeno spero... ;-))
Cmq e' in questa direzione che continuo la mia ricerca
e se qualcuno ha una buona idea per potare ulteriormente
sara' ben gradita anche se in senso negativo...
CiaO,
Massimo
-- 
Posted from 
net128-007.mclink.it
 [195.110.128.7] 


sara' ben gradita anche se in senso negativo...
Mah, a me sembra praticamente obbligato un solo schema, quello che
ricavi dalla mia suluzione brutissime force.
Cmq e` come il parquet. Per fare 7*8 senza pipe (=testa-testa) devi
IMHO necessariamente usare 8 elementi del tipo 2orizz.+2vert. e poi
altri 4 elementi allungando gli stessi con un orizzontale messo
alternativamente all'interno e di contorno.


 1|1  0.0  1|0  4.3
Forse il gruppo a dx in basso dovrebbe essere 
0|2                                              
4|3                                              
4.3
ciao :) dario






No. E` un porcaio:-(( Ho fatto casino o ricopiando o facendolo. C'e`
errore nella casella c1 (come gli scacchi): 0 non puo` legare sia 1,
sia 4.
Ora rifacendolo non mi viene piu` (se mai mi e venuto).
Arrivo a 23 + 3 jolly (tutti da da 1) :-((((((((
1.0  0|1  1.3  3|1
2.6  6|6  6.3  3|1
2|6  6.6  6|3  3.0
4|4  4.5  5|5  5.2
4.4  4|0  5.5  0|2
4|4  0|2  5|5  0|2
1|3  3.2  1|0  1.2
Cambiamenti fatti ora:
Orizzontali a3, cd1, gh1
Verticali a4, a2, b1, c2


1|3  3.2  0|1  1.2
Sono le e12<->f12 (notazione scacchi). Resta peggiorata anche la somma.
Diventa: 21 + 3 jolly. I jolly sono due da 1 e uno da 2. Fa 25 o 21 ?



.
.
Fa 21,
ma e' ancora alto. Sara' colpa di Linux  ;o)))))
.
Ciao  :o)
Livio
--------------------------------
Inviato via 
http://usenet.iol.it
 

ma e' ancora alto. Sara' colpa di Linux  ;o)))))
Ah, bene che gli zeri non contino. Ma a quanto deve andare non e`
dato saperlo? Dovrei escludere la testa col 4.. 'na parola:-((
Linux non c'entra, lo faccio col domino vero, altrimenti non credo
convenga. Invece si potrebbe fare forse con excel. Magari
automatizzando la segnalazione di errore d'aggancio. E la somma.



.
.
Tramite il SW di cui parlo nell'altro thread,
questa notte ho lanciato il PC per trovare tutte le combinazioni delle 28
tessere su scacchiera 8x7 senza contatti testa-testa. E' interessante
notare che le soluzioni sono esattamente 5. Le ho messe qua:
.
http://www.geocities.com/liviozuc/images/domino5.gif
.
Da quaste si
potrebbe partire per fare una ricerca sistematica (maybe).


ma e' ancora alto. Sara' colpa di Linux  ;o)))))
E lo credo che e` alto!! Addirittura lo scemo! :-((((
Continuavo a pensare a zero = quello che rappresenta:-(((((((((((((
Eccolo molto piu` basso: 16 :-))
Ho solo spostato gli zeri portandoli sul bordo al posto dei loro
omonimi. (ho anche snellito le notazioni: a|b = orizzontale)
1|1  0 1  1|3  3 0
2|6  6 6  6|3  3 1
2 6  6|6  6 3  3|0
4 4  4|5  5 5  5|2
4|4  4 0  5|5  5 2
4 4  3 2  5 0  1 2
1 0  3|2  0 0  1|2
Deve scendere ancora molto?
Se si` mi tocca andare a vedere gli altri 4 schemi di griglia, o
pensare a ricavarli. Ma questo e` il piu` spontaneo e ordinato.
Cavoli, sul bordo ho solo il doppio 4 e il doppio 3.. non e` facile
poterli legare in altro modo.



.
Ma ne ho da meno :)


 tessere del domino.
Ecco la mia soluzione:
perimetro = 10
...
spoiler
...
+---+---+---+---+---+---+---+---+
| 0 | 0 | 2   2 | 2 | 1 | 1   1 |
+   +   +---+---+   +   +---+---+
| 1 | 4 | 4   4 | 4 | 6 | 6   3 |
+---+---+---+---+---+---+---+---+
| 1   4 | 4 | 4 | 4   6 | 6 | 3 |
+---+---+   +   +---+---+   +   +
| 1   3 | 3 | 5 | 5   6 | 6 | 3 |
+---+---+---+---+---+---+-------+
| 1 | 3 | 3   5 | 5 | 6 | 6   0 |
+   +   +---+---+   +   +---+---+
| 5 | 2 | 3 | 5 | 5 | 2 | 0 | 2 |
+---+---+   +   +---+---+   +   +
| 0   2 | 0 | 0 | 5   2 | 0 | 1 |
+---+---+---+---+---+---+---+---+
Alessandro

Alessandro
Bellissimo come sei riuscito a piazzare i 66 55 44 (doppi) :-))
C'e` pero` la tessera 60 (con lo zero in h3), che non dovrebbe essere
regolare: lega sia 2, sia 3 :-((   Se riesci a mantenere il perimetro
dovrebbe essere un minimo assoluto IMHO.


 ha scritto: 
Ecco la mia soluzione:
perimetro = 10
.
.
Questa soluzione mi sorprende! La tessera 6-0 mi pare
corretta nella lettera dell'enunciato e anche nello spirito. Il punto 2
recita "OGNI contatto testa-fianco, ove siano presenti i numeri, deve far
combaciare numeri uguali", mentre il seguito e' un commento piu' fuorviante
(jolly) che chiarificatore. Anche nello spirito e' corretto perche' nelle
tessere antiche lo zero non c'e'. Io l'accetto e fino a prova contraria la
prendo come record. La pubblichero' sul sito.
