On the number of tilings of a chessboard by dominoes

Question

A partial tiling of a chessboard by dominoes is a placement of dominoes on the board such that no two dominoes overlap. A tiling of a chessboard by dominoes is a partial tiling for which every square of the board is covered by some domino.

The problem I am interested in is the following: What is the number of tilings of an $N$ by $N$ chessboard by dominoes?

It turns out there is actually an explicit formula for the number of tilings of an $M$ by $N$ chessboard b dominoes:

https://wikimedia.org/api/rest_v1/media/math/render/svg/1bc328b90d68fd765e2666ad0c62bb42b2e2bd10

I am interested in an algorithmic approach to this problem. We need only consider the case $N$ even (for $N$ odd the number of tilings is clearly $0$). The only algorithm I have thought of to solve is a brute force recursion.

I create a function called number_of_tilings(partial_tiling) which accepts a partial tiling of the chessboard and outputs the number of ways to cover the uncovered squares with dominoes such that we end up with a tiling.

I create an auxiliary function called uncovered_square(partial_tiling) which accepts a partial tiling and outputs the upper-leftmost uncovered square in the tiling, or False if no such square exists.

The function number_of_tilings(partial_tiling) is defined recursively: if uncovered_square(partial_tiling) outputs False, then number_of_tilings(partial_tiling)=1 because partial_tiling is in fact a proper tiling. Otherwise uncovered_square(partial_tiling) outputs some square S. We place a dominoe horizontally at square S (if possible) and thus generate a new partial tiling t_horizontal. Similarly we define t_vertical. Finally we compute number_of_tilings(t_horizontal)+number_of_tilings(t_vertical).

The initial input of number_of_tilings is an $N$ by $N$ chessboard with no dominoes placed on it.

This algorithm gives the correct answer very quickly for N=2,4,6 but for N>=8 it is extremely slow (super-exponential time).

---

So my question is what other possible algorithms exist or can the brute-force algorithm be optimized?

Answer 1

This problem is already studied in the literature and doesn't seem to be very easy and straightforward. e.g. take a look at

http://www.math.cmu.edu/~bwsulliv/domino-tilings.pdf

The above link provides a polynomial time algorithm to calculate it.

In fact it first translate it to a graph problem, i.e. number of perfect matching in special graph class. Then defines an adjacency matrix for that graph and calculates permanent of that matrix which is equivalent to the number of perfect matchings.

Calculating the permanent of a matrix is hard in general graphs. But in this particular graph, or in planar graphs, it is possible to solve it. The idea of this part is not very intuitive though.

Answer 2

There's a pretty easy dynamic programming solution that runs in O(N*2^2N) or better:

1. generate all possible ways of filling the first row (less than 2^N).

2. Since dominoes are only 2 squares long, the effects of this only propagate to the 2nd row. There are less than 2^N possible configurations of the 2nd row. Calculate how many ways there are to generate each one.

3. Similarly, there are <= 2^N configurations of the third row produced by filling the first 2 rows, and so on. Given the # of ways to generate each configuration left by filling the first m rows, you can calculate the number of ways to generate each configuration left by filling the first m+1 rows in O(2^2N) time or better.

4. For each configuration produced by filling the first N-1 rows, there can be at most 1 way to fill the final row. Add up the # of ways to generate each configuration that leaves only even-length gaps in the last row, and that's your answer.

On a good box with tight code, I would expect this to take less than a minute for N=16. I can think of a bunch of ways to make it a little faster, but nothing that gets under O(2^N)