Domino Tiling

The answer is 1183.

The trick is to realize that this problem is effectively asking for the number of perfect matchings on the $5 \times 6$ square grid graph . (A domino corresponds to an edge chosen in the matching.) Moreover, the square grid graph is planar . Finding the number of perfect matchings in a planar graph can be computed efficiently (in $O \left( |V|^3 \right)$ time) using FKT algorithm . Thus this is just an easy application of the FKT algorithm. (Other matching algorithms are discussed here .)

The FKT algorithm works as follows; with an input of a planar graph $G$ :

1. Compute a planar embedding of $G$ .
2. Give an orientation for every edge of $G$ such that each face has an odd number of edges oriented clockwise.
3. Construct the $(1, -1, 0)$ -adjacency matrix $(A_{ij})$ of $G$ : $A_{ij}$ is 1 if the edge between $i$ and $j$ is directed to $j$ , is -1 if it's directed to $i$ , and is 0 if it's not present.
4. Compute the determinant of $(A_{ij})$ .
5. Return the square root of the determinant.

In general graphs, step 2 is not efficiently computable (unless $P = \#P$ ). In planar graphs, it can be computed efficiently (see the Wikipedia article; it adds orientations freely unless when it is forced to orient in a way to give a face the required odd number of edges). However, we know our graph already; we can just compute step 2 ourselves. The orientation I use is simple:

Given that orientation, it's easy to hard-code the matrix. We can simply compute the determinant and find the square root of the resulting matrix. Since the grid is $5 \times 6$ , we have $5 \cdot 6 = 30$ vertices, so it should run quickly enough. Python 3 code follows:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

import copy
import fractions
Frac = fractions.Fraction

def det(A):
    A = copy.deepcopy(A)
    n = len(A)
    mult = 1
    for i in range(n):
        for j in range(i, n):
            if A[j][i]: break
        else:
            return 0
        if j != i:
            A[i], A[j] = A[j], A[i]
            mult *= -1
        for j in range(i+1, n):
            for k in range(i+1, n):
                A[j][k] -= A[j][i] * A[i][k] / A[i][i]
            A[j][i] = 0
    res = 1
    for i in range(n): res *= A[i][i]
    return res * mult

def sqrt(n):
    mn = 0
    mx = 1
    while mx**2 <= n:
        mx *= 2
    while mx - mn > 1:
        md = (mn + mx) // 2
        if md**2 <= n:
            mn = md
        else:
            mx = md
    return mn

def count(n,m):
    A = [[Frac(0)]*(n*m) for _ in range(n*m)]
    for i in range(n):
        for j in range(m):
            if i > 0: A[i*m+j][(i-1)*m+j] = Frac(-1)
            if i < n-1: A[i*m+j][(i+1)*m+j] = Frac(1)
            if j > 0: A[i*m+j][i*m+(j-1)] = (Frac(1) if i % 2 else Frac(-1))
            if j < m-1: A[i*m+j][i*m+(j+1)] = (Frac(-1) if i % 2 else Frac(1))
    return sqrt(det(A))

print(count(5, 6))
# prints 1183

This code can even work for the original problem, a $9 \times 12$ grid. (It runs in approximately 10 seconds.) The answer is 1937528668711. I decided to use only $5 \times 6$ ; it's just beyond brute force approach, but it's still small enough that precision errors don't matter yet. (With $9 \times 12$ , precision errors might matter. In Python, I used the fractions library above, to make sure that they are not present; however, using other languages, it's very likely that people will use the data type double , which is prone to precision errors.)

The number of ways to tile a domino board of dimension $m\times n$ is given by:

$\prod _{j=1}^3\prod _{k=1}^3\left(4\cos ^2\left(\frac{\pi j}{5+1}\right)+5\cos ^2\left(\frac{\pi k}{6+1}\right)\right)$

Evaluating, we get 1183.

since constraints are very small, we can just use recursive backtracking :p assume we are at (x,y), if we can put a horizontal domino, put it. then try a vertical domino, then backtrack. a[5][6] corresponds to the current board. code: https://ideone.com/gLBPuD (only ran for 0,1 s on local machine)

I am completly mind blown by some of the solution posted here, especialy @Ivan Koswar 's one. It mad me realize how amazing humans are. I saw this problem two years ago, i had no idea how to tackle it, yesterday i decided to give it a try and what do you know i solved it ! (well, my solution is far from efficient), this is the reason why i love this website !

Here is my solution (for any N x M grid):

EDIT: cleaning, work with any domino dimension (N D x M D).

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170

#include <iostream>
#include "stdlib.h"
#include <cmath>

int const HORIZONTALE = 1;
int const VERTICALE = 2;
int const EMPTY = 0;
//grid dimension N x M
int N = 0;
int M = 0;
//domino dimension N_D x M_D 
int N_D = 0;
int M_D = 0;
//grid
int** grid = NULL;

using namespace std;

bool placeDomino(int type, int & x, int & y, int val){  
    int condition = M_D;
    int i = 1;
    int x_0 = x;
    int y_0 = y;

    bool ok;

    if(type == VERTICALE){
        condition = N_D;
    }

    while(x < M && y < N && grid[y][x] == EMPTY && i <= N_D * M_D){
        grid[y][x] = val;

        if(i % condition == 0){
            x = x_0;
            y++;
        }
        else{
            x++;
        }
        i++;    
    }
    ok = i > N_D * M_D;

    if(ok){
        y = y_0;
        if(x == M && y < N){
            x = 0;
            y++;
        }
        //place cursor in a empty slot
        while(y < N && grid[y][x] != EMPTY){         
            x++;
            if(x == M && y < N){
                x = 0;
                y++;
            }
        }       
    }

    return i > N_D * M_D;
}
void removeDomino(int type, int x , int y){
    int id = 0;

    if(x < M && y < N){
        id = grid[y][x];
    }
    int condition = M_D;
    int i = 1;
    int x_0 = x;

    if(type == VERTICALE){
        condition = N_D;
    }

    while(x < M && y < N && grid[y][x] == id && i <= N_D * M_D){
        grid[y][x] = EMPTY;

        if(i % condition == 0){
            x = x_0;
            y++;
        }
        else{
            x++;
        }
        i++;
    }   
}
int dominoTiling_r(int i, int & x, int & y, int occupied=0){
    int T = 0;
    int spin;

    if(occupied == N * M){
        T = 1;
        /*
         * uncomment to see each solution
        for(int z = 0; z < N; z++){
            for(int w = 0; w < M; w++){

                cout << grid[z][w] << " ";
                if(grid[z][w] < 10){
                    cout << " " ;
                }

            }
            cout << endl;
        }
        cout << endl;
        */
    }
    else{

        int x_0 = x;
        int y_0 = y;

        spin = HORIZONTALE;

        if(placeDomino(spin, x, y, i+1)){
            T += dominoTiling_r(i+1, x, y, occupied + N_D * M_D);
        }
        removeDomino(spin, x_0, y_0);

        x = x_0;
        y = y_0;

        spin = VERTICALE;
        if(placeDomino(spin, x, y, i+1)){
            T += dominoTiling_r(i+1, x, y, occupied + N_D * M_D);
        }
        removeDomino(spin, x_0, y_0);   
    }

    return T;

}
int dominoTiling(int n, int m, int d_n = 1, int d_m = 2){
    N = n;
    M = m;

    N_D = d_n;
    M_D = d_m;

    grid = new int*[N];

    for(int i = 0; i < N; i++){
        grid[i] = new int[M];
        for(int j = 0; j < M; j++){
            grid[i][j] = EMPTY;
        }
    }

    int x = 0;
    int y = 0;

    int cpt = dominoTiling_r(0, x, y);

    for(int i = 0; i < N; i++){
        delete[] grid[i];
    }

    delete[] grid;

    return cpt;
}

int main(){
    cout << dominoTiling(5, 6) << endl;
    return 0;
}