Is there a database of all domino tilings of an n by m rectangle (for small n, m)?

Question

I would like to see the actual dominos in all domino tilings of any small rectangle (or similar). I'm not sure what an efficient algorithm is for constructively enumerating them by computer. Yes, there are closed form expressions for counting them, but that doesn't help in constructing them (other than verifying that one's algorithm is likely correct). But it seems to me that once someone, somewhere has done that, the results might be saved somewhere (in some kind of parsable file format) and available to others. If not, what's the best way to understand how to constructively enumerate all the solutions, at least for small n and m?

Answer 1

Start with an empty rectangle and traverse the squares from left to right, top to bottom. If you encounter a square that hasn’t been tiled yet, tile it with the square either to its right or below it (if that square exists and is untiled), and recurse.

Here’s Java code that implements this approach. It seems to be quite efficient – the number of dead ends reached is about an order of magnitude lower than the number of tilings found. For a non-square rectangle, the number of dead ends reached is lower if you use more rows than columns (which makes sense, as the dead ends occur in the last two rows, no matter how many rows there are, and the rows are shorter this way).