Generating all possible Domino tilings on a $4 \times 4$ grid

Question

I have a task to write a program which generates all possible combinations of tiling domino on a $4 \times 4$ grid. I have found many articles about tilings, but it is for me quite difficult and I didn't find any article with an algorithm that allows generating all possible combinations.

Could someone give me some tips? How should I start with that? Thanks in advance.

Answer 1

Do this recursively:

1. Find the top-left empty square on the board.
2. If there is no empty square, all squares are covered with dominos, just print the solution and return.
3. If there is an empty square, try to put a domino horizontally, then vertically. If that is possible, put a domino on the board and go to the step 1 again.

Some backtracking is necessary along the way. You can easily grasp the idea by looking at the following Python script:

In Python:

class Table:
    table = [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
    domino = 0
    count = 0

    def findEmptyCell(self):
        for i in range(0, 4):
            for j in range(0, 4):
                if self.table[i][j] == 0:
                    return (i, j)
        return None

    def placeDomino(self):
        cell = self.findEmptyCell()
        if cell is None:
            # we have a full board with no empy cells
            self.print()
            return
        # try to put a new domino horizontally
        x = cell[0]
        y = cell[1]
        self.domino += 1
        self.table[x][y] = self.domino
        if y < 3 and self.table[x][y + 1] == 0:
            self.table[x][y + 1] = self.domino
            self.placeDomino()
            self.table[x][y + 1] = 0
        if x < 3 and self.table[x + 1][y] == 0:
            self.table[x + 1][y] = self.domino
            self.placeDomino()
            self.table[x + 1][y] = 0
        self.table[x][y] = 0
        self.domino -= 1


    def print(self):
        self.count += 1
        print("=== Solution #%d ===" % self.count)
        for i in range(0, 4):
            print("%d%d%d%d" % (self.table[i][0], self.table[i][1], self.table[i][2], self.table[i][3]))
        print('')

t = Table()
t.placeDomino()

Here is the output, 36 solutions in total (with dominoes numbered from 1 to 8):

=== Solution #1 ===
1122
3344
5566
7788

=== Solution #2 ===
1122
3344
5567
8867

=== Solution #3 ===
1122
3344
5667
5887

=== Solution #4 ===
1122
3344
5677
5688

=== Solution #5 ===
1122
3344
5678
5678

=== Solution #6 ===
1122
3345
6645
7788

=== Solution #7 ===
1122
3345
6745
6788

=== Solution #8 ===
1122
3445
3665
7788

=== Solution #9 ===
1122
3455
3466
7788

=== Solution #10 ===
1122
3455
3467
8867

=== Solution #11 ===
1122
3456
3456
7788

=== Solution #12 ===
1123
4423
5566
7788

=== Solution #13 ===
1123
4423
5567
8867

=== Solution #14 ===
1123
4423
5667
5887

=== Solution #15 ===
1123
4423
5677
5688

=== Solution #16 ===
1123
4423
5678
5678

=== Solution #17 ===
1123
4523
4566
7788

=== Solution #18 ===
1123
4523
4567
8867

=== Solution #19 ===
1223
1443
5566
7788

=== Solution #20 ===
1223
1443
5567
8867

=== Solution #21 ===
1223
1443
5667
5887

=== Solution #22 ===
1223
1443
5677
5688

=== Solution #23 ===
1223
1443
5678
5678

=== Solution #24 ===
1223
1453
6457
6887

=== Solution #25 ===
1233
1244
5566
7788

=== Solution #26 ===
1233
1244
5567
8867

=== Solution #27 ===
1233
1244
5667
5887

=== Solution #28 ===
1233
1244
5677
5688

=== Solution #29 ===
1233
1244
5678
5678

=== Solution #30 ===
1233
1245
6645
7788

=== Solution #31 ===
1233
1245
6745
6788

=== Solution #32 ===
1234
1234
5566
7788

=== Solution #33 ===
1234
1234
5567
8867

=== Solution #34 ===
1234
1234
5667
5887

=== Solution #35 ===
1234
1234
5677
5688

=== Solution #36 ===
1234
1234
5678
5678