Seite 1 von 1

dominosa

BeitragVerfasst: 27.11.2004 07:34
von Gast
ist eigentlich bekannt, welches die groesstmoegliche Anzahl
von Loesungen ist fuer ein Dominosa Puzzle ?

1292697 , die Zahl der domino-tilings of a 7*8-rectangle
ist obere Grenze. Hier ist eins mit
545376 Loesungen:

4 4 0 3 5 5 0 1
4 3 4 0 3 5 1 4
6 4 0 0 5 4 1 1
2 6 0 2 0 5 2 1
6 5 6 0 5 2 2 2
5 1 6 6 6 3 2 4
1 3 1 6 3 3 3 2


Guenter.

Re: dominosa

BeitragVerfasst: 27.11.2004 21:56
von Otto
> ist eigentlich bekannt, welches die groesstmoegliche
> Anzahl von Loesungen ist fuer ein Dominosa Puzzle?

Nein, zumindest mir nicht.

> Hier ist eins mit 545376 Loesungen

Ordentlich. Hätte nicht geglaubt, daß es eine Aufgabe mit so vielen Lösungen gibt.

~ÔttÔ~

BeitragVerfasst: 01.12.2004 07:03
von Gast
Here is one with 730924 solutions:

6 6 1 1 0 1 4 4
2 6 6 1 1 5 1 4
5 2 1 3 2 1 4 0
5 5 3 2 2 2 0 0
5 3 2 4 2 0 0 6
3 6 4 3 0 5 6 5
3 3 6 4 3 0 5 4

for dominoes with maximal 0,1,..,6 points on each half I have
boards with 1,3,10,88,1012,22888,730924 solutions.
They all have a large number of critical 2*2-subsquares with
constant diagonal. If you draw the diagonals you get an
array looking like electron-spin-arrays or magnetization arrays:


\ \ \ \ / \ \
\ . / . \ / /
\ . / / \ . /
/ / / \ / / /
/ . / . / . /
\ \ \ \ \ \ /

for the 7*6 2x2-diagonals of the dominosa above.

--------------------------------

There is a nice formula for the number of domino-tilings of a n*m board
due to Kasteleyn:

t=2^(m*n/2)*PRODUCT [i=1..m,j=1..n] (cos(pi*i/(m+1))^2+cos(pi*j/(n+1))^2)^.25

this gives 1292697 as an upper bound for a 7*8 rectangle.


Guenter.