Donate to Remove ads

Got a credit card? use our Credit Card & Finance Calculators

Thanks to johnstevens77,Bhoddhisatva,scotia,Anonymous,Cornytiv34, for Donating to support the site

Dominoes

cinelli
Lemon Slice
Posts: 550
Joined: November 9th, 2016, 11:33 am
Has thanked: 231 times
Been thanked: 160 times

Re: Dominoes

#437370

Postby cinelli » August 25th, 2021, 5:23 pm

As staffordian has pointed out, there is a daily dominoes puzzle in the i newspaper. However the puzzle I set comes from a different source. Unusually, as well as the solution I also have a method and it is almost identical to the correct solutions of modellingman and Gengulphus. Namely place the 0-3, 1-6, 0-6, 3-3, 3-5, 2-3 and 3-6 dominoes then try placing another and look at the consequences.

The talk about proving uniqueness of a solution led to my wondering whether one can count the number of arrangements of dominoes over a rectangular area. Wikipedia has an article on this (search for "domino tiling") and two researchers have presented a fearsome formula for the number of ways of covering an m by n space with 1 x 2 tiles. The formula surprisingly includes two cosine terms. For a 7 by 8 rectangle my own quick program computes a product of 16 terms and gives 1292695.4 ways, not an integer, possibly due to accumulating rounding error. But finding the number of ways is one thing. Finding a systematic way of generating all these and checking for a solution is another, I think.

Cinelli

9873210
Lemon Slice
Posts: 984
Joined: December 9th, 2016, 6:44 am
Has thanked: 226 times
Been thanked: 295 times

Re: Dominoes

#437395

Postby 9873210 » August 25th, 2021, 7:26 pm

cinelli wrote:But finding the number of ways is one thing. Finding a systematic way of generating all these and checking for a solution is another, I think.

Cinelli

I don't think systematically generating all the tilings is hard.

The basic step on a partially filled grid is:

Code: Select all

look for the topmost, leftmost empty square
If none  {
    you have found a tiling
    return
} else {
// try both orientation
    if you can place a horizontal tile there, do so and recurse.
    if you can place a vertical tile there, do so and recurse.
}
return



If you just want to count the tilings checking if you can place a tile is just checking if the square to the right or below exists and is free. In the context of solving the original domino puzzle you would also check if it creates a duplicate of an already placed tile.

Gengulphus
Lemon Quarter
Posts: 4255
Joined: November 4th, 2016, 1:17 am
Been thanked: 2628 times

Re: Dominoes

#437554

Postby Gengulphus » August 26th, 2021, 11:40 am

cinelli wrote:As staffordian has pointed out, there is a daily dominoes puzzle in the i newspaper. However the puzzle I set comes from a different source. Unusually, as well as the solution I also have a method and it is almost identical to the correct solutions of modellingman and Gengulphus. Namely place the 0-3, 1-6, 0-6, 3-3, 3-5, 2-3 and 3-6 dominoes then try placing another and look at the consequences.

The talk about proving uniqueness of a solution led to my wondering whether one can count the number of arrangements of dominoes over a rectangular area. Wikipedia has an article on this (search for "domino tiling") and two researchers have presented a fearsome formula for the number of ways of covering an m by n space with 1 x 2 tiles. The formula surprisingly includes two cosine terms. For a 7 by 8 rectangle my own quick program computes a product of 16 terms and gives 1292695.4 ways, not an integer, possibly due to accumulating rounding error. But finding the number of ways is one thing. Finding a systematic way of generating all these and checking for a solution is another, I think.

Here's a table giving the answers for m by n rectangles up to those with m+n = 19. Not values I've calculated myself - I've obtained them from https://oeis.org/A099390, specifically its "Table of n, a(n) for n = 1..1035" link, which goes up to m+n = 46. I haven't investigated the "LINKS" section of that page, but there will probably be quite a bit about calculating values among them (and probably also a number of 'dead' links, I'm afraid - OEIS has enormous numbers of links in its database, and many of them get broken e.g. because mathematicians move on to another university, retire, etc).


9873210 wrote:I don't think systematically generating all the tilings is hard.

The basic step on a partially filled grid is:

Code: Select all

look for the topmost, leftmost empty square
If none  {
    you have found a tiling
    return
} else {
// try both orientation
    if you can place a horizontal tile there, do so and recurse.
    if you can place a vertical tile there, do so and recurse.
}
return


If you just want to count the tilings checking if you can place a tile is just checking if the square to the right or below exists and is free. In the context of solving the original domino puzzle you would also check if it creates a duplicate of an already placed tile.

That will work for reasonably small rectangles, such as the 7x8 rectangle in the original domino tiling. But if you look at the numbers near the bottom of the "Table of n, a(n) for n = 1..1035" link mentioned above, it's pretty clear that a program along those lines won't complete in the lifetime of anyone here - and probably the lifetime of the inhabitable universe! Even the 14,479,521,761 figure for a 9x10 rectangle in my table above is likely to take a very noticeable amount of time to calculate...

The way I think I would go about it for an m rows by n columns rectangle would involve working upwards through values of m, counting both complete tilings and tilings that are incomplete because some of their bottom row cells are halves of vertical dominos which cannot actually be fully placed until we move up to m+1 rows by n columns. This is probably best illustrated by the first few numbers of columns, starting with two columns (i.e. the case n=2).

We know that the number of cells covered by the dominoes that have been placed so far is even, so the number of cells in the bottom row that are incomplete halves of vertical dominoes must be even, i.e. 0 or 2. If it's 0, we have a complete tiling (as illustrated on the left below); if it's 2, we have the single type of incomplete tiling which is possible when n=2 (on the right):

+---+---+              +---+---+
| | top | |
: : m-1 : fully :
: fully : rows : tiled :
| tiled | | |
+ + +---+---+
| | bottom row | | |
+---+---+ + + +

Call the numbers of complete and incomplete tilings possible of those two types xx(m) and oo(m) respectively, with "x" indicating a 'closed-off' cell in the bottom row and "o" indicating an 'open' cell in the bottom row. We can easily see that xx(1) = 1 (1x2 rectangle covered by a single horizontal domino) and oo(1) = 1 (1x2 rectangle covered by no horizontal dominoes and two to-be-completed vertical half-dominoes).

What happens if we increase m by 1? Each of the xx(m) complete tilings can become a complete tiling of the (m+1) by n rectangle if we add a horizontal domino below it, or an incomplete tiling of that rectangle if we add two to-be-completed vertical half-dominoes below it, while each of the oo(m) incomplete tilings is forced to become a complete tiling of that rectangle because we must fill in the two other halves of its two vertical half-dominoes. Furthermore, there is no ambiguity about how any complete or incomplete tiling of the (m+1) by n rectangle arose. So we can conclude that:

xx(m+1) = xx(m) + oo(m)
oo(m+1) = xx(m)

So xx(2) = xx(1) + oo(1) = 1+1 = 2, oo(2) = xx(1) = 1, and thereafter xx(m+2) = xx(m+1) + oo(m+1) = xx(m+1) + xx(m). That last formula xx(m+2) = xx(m+1) + xx(m) together with xx(1) = 1, xx(2) = 2 says that the sequence xx(m) of complete tilings is basically the Fibonacci numbers - which is why they can easily be seen in the second column and second row of the above table.

Tackling n=4 next, as above we know that the number of incomplete vertical half-tiles on the bottom row must be even, i.e. 0, 2 or 4. Furthermore, if we consider a checkerboard colouring of the cells, there are equal numbers of black and white cells, and every full domino must cover one of each, so equal numbers of those incomplete vertical half-tiles must be on black and white cells. That means that we should count six types of tiling, as follows with the notation I'll use for the counts below them:

+---+---+---+---+
| |
: :
: fully tiled :
| |
+ +
| |
+---+---+---+---+
xxxx(m)

+---+---+---+---+ +---+---+---+---+ +---+---+---+---+ +---+---+---+---+
| | | | | | | |
: : : : : : : :
: fully tiled : : fully tiled : : fully tiled : : fully tiled :
| | | | | | | |
+---+---+ + +---+ +---+ + +---+---+ + + +---+---+
| | | | | | | | | | | | | | | | |
+ + +---+---+ + +---+---+ + +---+ + +---+ +---+---+ + +
ooxx(m) oxxo(m) xoox(m) xxoo(m)

+---+---+---+---+
| |
: :
: fully tiled :
| |
+---+---+---+---+
| | | | |
+ + + + +
oooo(m)

When we add an extra row to any of these, we're forced to complete its half-dominoes (if it has any), and may have one or more options to add horizontal dominoes. Any cells on the new bottom row that haven't been covered by those horizontal dominoes and completions of vertical half-dominoes must then be covered with new vertical half-dominoes. So:

* A tiling in the xxxx(m) category generates a tiling in each of the xxxx(m+1), ooxx(m+1), oxxo(m+1), xxoo(m+1) and oooo(m+1) category (but not one in the xoox(m+1) category).
* A tiling in the ooxx(m) category generates a tiling in each of the xxxx(m+1) and xxoo(m+1) categories.
* A tiling in the oxxo(m) category generates a tiling in each of the xxxx(m+1) and xoox(m+1) categories.
* A tiling in the xoox(m) category generates a tiling in the oxxo(m+1) category.
* A tiling in the xxoo(m) category generates a tiling in each of the xxxx(m+1) and ooxx(m+1) categories.
* A tiling in the oooo(m) category generates a tiling in the xxxx(m+1) category.

Again, each tiling we've generated can only have arisen in one of those ways, and so:

xxxx(m+1) = xxxx(m) + ooxx(m) + oxxo(m) + xxoo(m) + oooo(m)
ooxx(m+1) = xxxx(m) + xxoo(m)
oxxo(m+1) = xxxx(m) + xoox(m)
xoox(m+1) = oxxo(m)
xxoo(m+1) = xxxx(m) + ooxx(m)
oooo(m+1) = xxxx(m)

Those formulae allow us to start from xxxx(1) = 1, ooxx(1) = 1, oxxo(1) = 1, xoox(1) = 0, xxoo(1) = 1, oooo(1) = 1 for m=1, and generate the counts for higher values of m at the cost of doing seven additions and two copyings per extra value of m. I've stuck them into a spreadsheet and the results were:


As expected, the xxxx(m) column of that table agrees with the n=4 column of the earlier table.

I skipped over n=3 above because 3 being odd complicates matters a bit. In terms of the counts of complete tilings we're after, it means that those counts are obviously 0 whenever m is also odd. In terms of the above approach using counts of both complete and incomplete tilings, it means that the number of vertical half-tiles in the last row of a tiling must be even if m is even and odd if m is odd, and that the checkerboard argument implies that there must be equal numbers of vertical half-tiles of each colour if m is even and one more of the colour of the board's corner cells if m is odd. As a result, the counts we need to work with are xxx(m), oox(m) and xoo(m) if m is even and oxx(m), xxo(m) and ooo(m) if m is odd:

+---+---+---+     +---+---+---+     +---+---+---+
| | | | | |
: fully : : fully : : fully :
: tiled : : tiled : : tiled :
| | | | | | m even
+ + +---+---+ + + +---+---+
| | | | | | | | | |
+---+---+---+ + + +---+ +---+ + +
xxx(m) oox(m) xoo(m)

+---+---+---+ +---+---+---+ +---+---+---+
| | | | | |
: fully : : fully : : fully :
: tiled : : tiled : : tiled :
| | | | | | m odd
+---+ + + +---+ +---+---+---+
| | | | | | | | | |
+ +---+---+ +---+---+ + + + + +
oxx(m) xxo(m) ooo(m)

The initial values are oxx(1) = 1, xxo(1) = 1 and ooo(1) = 1, and the formulae that relate the values for m+1 to those for m are:

For m odd: xxx(m+1) = oxx(m) + xxo(m) + ooo(m); oox(m+1) = xxo(m); xoo(m+1) = oxx(m)
For m even: oxx(m+1) = xxx(m) + xoo(m); xxo(m+1) = xxx(m) + oox(m); ooo(m+1) = xxx(m)

As we're only interested in the m even cases, we can apply the m odd formulae once to the initial values to get xxx(2) = 3, oox(2) = 1, xoo(2) = 1, and use an instance of each set of formulae to get the following for m even:

xxx(m+2) = oxx(m+1) + xxo(m+1) + ooo(m+1) = 3xxx(m) + oox(m) + xoo(m)
oox(m+2) = xxo(m+1) = xxx(m) + oox(m)
xoo(m+2) = oxx(m+1) = xxx(m) + xoo(m)

Since by symmetry oox(m) and xoo are always equal, we can reduce that further to:

Initial values: xxx(2) = 3, oox(2) = 1
Formulae to increase m by 2: xxx(m+2) = 3xxx(m) + 2oox(m), oox(m+2) = xxx(m) + oox(m)

and it can be checked that those allow the sequence of values for even values of m in the n=3 column of the first table above to be calculated, using just 2 multiplications and 2 additions for each additional value of m. There is the fact that the numbers grow exponentially and quickly, as was also the case for n=2 and n=4 - only moderately quickly for n=2, more quickly for n=3, more quickly still for n=4. And similar formulae can be worked out for higher values of n, and will result in even more rapid exponential growth of the counts obtained. They'll result in rather more additions and multiplications per increase in m, but it will be a fixed number of them per such increase and so it will be an immensely more efficient process than generating every tiling and incrementing a count for each one you find.

One final point to make is that the rapid growth of the counts as m and n increase means that if you want to take that process of calculating the numbers of domino tilings of rectangles all that far, you'll need to use an arbitrary-precision integer arithmetic package to do the additions and multiplications rather than ordinary computer arithmetic. And I'd guess that the ultimate limiting factor on doing those calculations is likely to be how much memory you have on your computer in which to store the enormous numbers!

Gengulphus

9873210
Lemon Slice
Posts: 984
Joined: December 9th, 2016, 6:44 am
Has thanked: 226 times
Been thanked: 295 times

Re: Dominoes

#437627

Postby 9873210 » August 26th, 2021, 5:15 pm

Gengulphus wrote:
9873210 wrote:
cinelli wrote:But finding the number of ways is one thing. Finding a systematic way of generating all these and checking for a solution is another, I think.

Cinelli

I don't think systematically generating all the tilings is hard.

[clip short algorithm]


That will work for reasonably small rectangles, such as the 7x8 rectangle in the original domino tiling. But if you look at the numbers near the bottom of the "Table of n, a(n) for n = 1..1035" link mentioned above, it's pretty clear that a program along those lines won't complete in the lifetime of anyone here - and probably the lifetime of the inhabitable universe! Even the 14,479,521,761 figure for a 9x10 rectangle in my table above is likely to take a very noticeable amount of time to calculate...

The way I think I would go about it for an m rows by n columns rectangle would involve working ...
[clip long algorithm]


You did not solve the problem of generating all the solutions, you solved the problem of counting all the solutions. I don't think your algorithm offers any useful optimizations for generating solutions. If there are lots of solutions then generating them all takes a long time, there's no way round that, other than deciding to solve a different problem.

Gengulphus
Lemon Quarter
Posts: 4255
Joined: November 4th, 2016, 1:17 am
Been thanked: 2628 times

Re: Dominoes

#437713

Postby Gengulphus » August 26th, 2021, 10:26 pm

9873210 wrote:
Gengulphus wrote:
9873210 wrote:I don't think systematically generating all the tilings is hard.

[clip short algorithm]


That will work for reasonably small rectangles, such as the 7x8 rectangle in the original domino tiling. But if you look at the numbers near the bottom of the "Table of n, a(n) for n = 1..1035" link mentioned above, it's pretty clear that a program along those lines won't complete in the lifetime of anyone here - and probably the lifetime of the inhabitable universe! Even the 14,479,521,761 figure for a 9x10 rectangle in my table above is likely to take a very noticeable amount of time to calculate...

The way I think I would go about it for an m rows by n columns rectangle would involve working ...
[clip long algorithm]


You did not solve the problem of generating all the solutions, you solved the problem of counting all the solutions. I don't think your algorithm offers any useful optimizations for generating solutions. If there are lots of solutions then generating them all takes a long time, there's no way round that, other than deciding to solve a different problem.

In the post of mine you've quoted from, I quoted a post of cinelli's in which he commented both on counting tilings ("The talk about proving uniqueness of a solution led to my wondering whether one can count the number of arrangements of dominoes over a rectangular area.") and on generating them ("Finding a systematic way of generating all these and checking for a solution is another, I think."). Then I quoted from a post of yours in which you commented both on counting tilings ("If you just want to count the tilings checking if you can place a tile is just checking if the square to the right or below exists and is free.") and on generating them ("I don't think systematically generating all the tilings is hard."). I included all of those four sentences in the quotes in my post, which you've edited down for the quote in your post to just include the last of them.

I.e. you've indulged in selective quoting to make it appear as if I was changing the problem. I wasn't - I was just choosing to comment mainly on one of the two problems in the thread. The reason that I made that choice is that I had little to say about the tilings-generation problem (basically just that the numbers of tilings one needs to generate pretty quickly become very large), but something significant to say about the tilings-counting problem, namely that there are much better ways of solving it than generating all the tilings and counting them one by one.

And by the way, my example algorithms for counting the n=2, 3 and 4 are short, both in terms of the amount of code needed and in terms of execution time - initialise a few variables, execute a simple loop m - 1 or m/2 - 1 times. What you clipped was almost all explanations of why the algorithms work rather than the algorithms themselves.

Gengulphus


Return to “Games, Puzzles and Riddles”

Who is online

Users browsing this forum: No registered users and 11 guests