xxxvii. Mutilated Chessboard and Tilings

Problem (Black 1946, Gamow–Stern 1958). Remove two diagonally opposite corners of a chessboard. Can the remaining 62 squares be tiled by 31 dominoes?

Answer. No: every domino covers one white and one black square, but both removed corners have the same colour, leaving 32 of one colour and 30 of the other. Colouring arguments are the main tool for “impossible” tilings; for “possible” ones, a construction or a counting DP.

Question	Answer	Tool
$8\times 8$ minus two opposite corners, dominoes	impossible	chessboard colouring
$8\times 8$ minus one white and one black square, dominoes	always possible (Gomory)	Hamiltonian cycle of the board
$m\times n$ by $1\times k$ strips	possible iff $k\mid m$ or $k\mid n$	colouring by $(i+j)\mathrm{mod}k$
$8\times 8$ minus one square, $1\times 3$ strips	possible iff the hole is at $(2,2),(2,5),(5,2),(5,5)$ (0-indexed)	two diagonal 3-colourings
$2^k\times 2^k$ minus any square, L-trominoes	always possible	divide and conquer, see Tromino Tiling
number of domino tilings of $8\times 8$	$12988816$	profile DP, Kasteleyn’s formula
domino tilings of a region with holes	count by profile DP $O(nm{2}^m)$; existence = perfect matching	Profile DP, Bipartite Matching

// Number of domino tilings of a grid with blocked cells '#', broken-profile DP in O(n m 2^m).
// Bit j of the mask: the next unprocessed cell in column j is already covered.
ll dominoTilings(const vector<string>& g) {
    int n = sz(g), m = sz(g[0]); vector<ll> dp(1 << m, 0), nd(1 << m); dp[0] = 1;
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
        fill(all(nd), 0);
        for (int mask = 0; mask < (1 << m); mask++) if (ll v = dp[mask]) {
            if (mask >> j & 1) { nd[mask ^ 1 << j] += v; continue; }                 // covered from above or the left
            if (g[i][j] == '#') { nd[mask] += v; continue; }
            if (i + 1 < n && g[i + 1][j] != '#') nd[mask | 1 << j] += v;             // vertical domino
            if (j + 1 < m && !(mask >> (j + 1) & 1) && g[i][j + 1] != '#') nd[mask | 1 << (j + 1)] += v;   // horizontal
        }
        swap(dp, nd);
    }
    return dp[0];
}
 
// Can the free cells ('.') be tiled by 1 x k strips? Backtracking on the first free cell.
bool stripTile(vector<string>& g, int k) {
    int n = sz(g), m = sz(g[0]), r = -1, c = -1;
    for (int i = 0; i < n && r < 0; i++) for (int j = 0; j < m; j++) if (g[i][j] == '.') { r = i, c = j; break; }
    if (r < 0) return true;
    for (int dir = 0; dir < 2; dir++) {                  // the first free cell must be the left or top end of its strip
        bool ok = true;
        for (int t = 0; t < k && ok; t++) { int x = r + dir * t, y = c + (1 - dir) * t; ok = x < n && y < m && g[x][y] == '.'; }
        if (!ok) continue;
        for (int t = 0; t < k; t++) g[r + dir * t][c + (1 - dir) * t] = '#';
        bool res = stripTile(g, k);
        for (int t = 0; t < k; t++) g[r + dir * t][c + (1 - dir) * t] = '.';
        if (res) return true;
    }
    return false;
}

Proof: Gomory's theorem

The $8\times 8$ board has a Hamiltonian cycle in its grid graph: go right along row 0, then snake through rows $\mathrm{1..7}$ inside columns $\mathrm{1..7}$ (row 1 leftwards, row 2 rightwards, …, row 7 leftwards, ending at $(7,1)$), and return up column 0. Consecutive cells of the cycle have opposite colours, so two cells of opposite colours sit at positions of the cycle that differ by an odd number. Removing them cuts the cycle into two arcs (one is empty if they are adjacent), each with an even number of cells; pairing consecutive cells along each arc tiles it with dominoes. The same proof works for every $m\times n$ board with $m$ even and $n\ge 2$ (the snake needs an odd number $m-1$ of rows), hence for every board with $mn$ even and $m,n\ge 2$. Checked with the DP: all $32\cdot 32$ removals on $8\times 8$ and $6\times 6$ give a positive count.

Proof: 1 × k strips tile m × n iff k divides m or n

If $k\mid n$, tile each row with horizontal strips; similarly for $m$. Conversely colour cell $(i,j)$ with $(i+j)\mathrm{mod}k$. A strip covers $k$ consecutive values of $i+j$, hence one cell of each colour, so a tileable region has equally many cells of every colour. Write $m=qk+r$, $n=pk+s$ with $1\le r,s<k$ and, by symmetry, $r\le s$. The board splits into a $qk\times n$ block (each column holds $qk$ consecutive values of $i+j$: equal counts), an $r\times pk$ block (equal counts by rows), and an $r\times s$ corner. In the corner, colour $r-1$ appears exactly $r$ times (sum $i+j=r-1$ has $r$ solutions with $i<r$, $j<s$, and $r-1+k>r+s-2$ is out of range). Colour $k-1$ appears $\max (0,r+s-k)<r$ times (sum exactly $k-1$, since $2k-1>r+s-2$; solutions $i\in [k-s,r-1]$). So the corner, and hence the whole board, has unequal colour counts: no tiling.

Proof: the 1 × 3 strips on 8 × 8 minus one square

Colour $(i,j)$ by $(i+j)\mathrm{mod}3$ and separately by $(i-j)\mathrm{mod}3$; a horizontal or vertical $1\times 3$ strip covers each colour once in both colourings. On $8\times 8$ the sum $i+j=t$ occurs $\min (t+1,15-t)$ times, so residue $1$ occurs $2+5+8+5+2=22$ times and residues $0$ and $2$ occur 21 times each. A tiling of the 63 remaining cells covers each colour 21 times. So the hole must be a cell with $i+j\equiv 1(\mathrm{mod}3)$. For $i-j=d$ there are $8-|d|$ cells, so residue $0$ occurs $2+5+8+5+2=22$ times and the hole has $i-j\equiv 0(\mathrm{mod}3)$. Together $2i\equiv 1$, i.e. $i\equiv 2(\mathrm{mod}3)$, and $j\equiv i$: the hole is at $i,j\in \{2,5\}$, four cells. For each of them stripTile finds a tiling, and for the other 60 it reports none.

The number of domino tilings of an $m\times n$ board is given by Kasteleyn’s formula (Kasteleyn; Temperley and Fisher, 1961), proved with Pfaffians:

$$T(m,n)=\prod _{j=1}^{\lceil m/2\rceil }\prod _{k=1}^{\lceil n/2\rceil }\left(4{\cos }^2\frac{\pi j}{m+1}+4{\cos }^2\frac{\pi k}{n+1}\right),$$

stated here without proof; it agrees with dominoTilings for all $m,n\le 10$ ($T(8,8)=12988816$, and it grows like $e^{Gmn/\pi }$ with Catalan’s constant $G$).

Related notes

• Parity, Coloring and Mod Observations
• Profile DP
• Tromino Tiling