Solved via simulation.
The program is here:
http://stevelord.net/tile8.f
Side............Different.......................Unique
_______________________________________________
4.........................36...............................9
6.....................6728 ...........................930
8..............12988816.....................1629189
The way the code generates tilings is to ascribe to each cell one of four directions that its tile points (R,L,U,D) and then to walk through the grid using or incrementing and using these where legal. When the directions are exhausted (dead end) the program backs up to the previous cell. This method finds all the different solutions.
The trick to finding the unique solutions quickly is to rotate every different solution through the 7 possible ways and count the number of distinct variants (e.g. an entirely horizontal tiling will have one variant - all vertical. Since the generator finds all the different tilings, we count the horizontal solution just mentioned as only 1/2, since it will be found twice, etc.
The 8x8 takes 23 seconds to run, and I estimate the 10x10 would take 5.1 days on my 3.1 GHz MacBook Pro.
While I obtained these results through simulations, for the "different ways", there is an analytic solution:
a(n) = Prod_{j=1..n} Prod_{k=1..n} [4*cos(j*Pi/(2*n+1))^2 +4*cos(k*Pi/(2*n+1))^2]
refs: wikipedia "Domino Tiling" or the OEIS (put in the "different" sequence listed above).
For the "unique" sequence, I found no analytic solution nor an entry in the OEIS, so I added one: A316535.
For 2n=4 a set of 9 unique tilings are shown below. Here "1 2" is a horizontal tile and "4 above 3" is a vertical tile.
2n=4, Number different = 36, Number unique=9.
*** 1 ***
1 2 1 2
1 2 1 2
1 2 1 2
1 2 1 2
*** 2 ***
1 2 1 2
1 2 1 2
1 2 4 4
1 2 3 3
*** 3 ***
1 2 1 2
1 2 1 2
4 1 2 4
3 1 2 3
*** 4 ***
1 2 1 2
1 2 1 2
4 4 4 4
3 3 3 3
*** 5 ***
1 2 1 2
1 2 4 4
1 2 3 3
1 2 1 2
*** 6 ***
1 2 1 2
1 2 4 4
4 4 3 3
3 3 1 2
*** 7 ***
1 2 1 2
4 1 2 4
3 1 2 3
1 2 1 2
*** 8 ***
1 2 1 2
4 4 4 4
3 3 3 3
1 2 1 2
*** 9 ***
1 2 4 4
1 2 3 3
4 4 1 2
3 3 1 2
|
