Skip to main content

The Problem Pit: Dominoes, Trominoes, and the Madness of Covering Boards


The Pit of Tiling: Dominoes, Trominoes, and the Madness of Covering Boards

Some math problems look like games. Tiling problems are the purest of these: you have a shape (a board), you have some tiles (dominoes, trominoes, etc.), and you want to cover the board without overlaps or gaps.

It feels like a puzzle you’d get in a children’s magazine.

That’s what I thought when I first tried to tile a rectangle with dominoes. Then I fell into a pit that connected geometry, combinatorics, algebra, and computational complexity.

Step 1: Dominoes on a Chessboard — The Happy Start

Take a standard chessboard, 8×88 \times 8. Can you tile it with dominoes, each covering two adjacent squares?

Yes — and easily. Just line them up in rows.

What about smaller boards?

  • A 2×n2 \times n board: clearly possible, just lay them end to end. In fact, the number of ways is exactly the Fibonacci numbers! (each tiling ends with a vertical domino or two horizontals).

  • A 3×n3 \times n board? Already trickier.

So far, tilings looked fun, solvable, neat.

But then I tried the mutilated chessboard.

Step 2: The Mutilated Chessboard Problem

Suppose you remove two opposite corners from the 8×88 \times 8 chessboard. Can you still tile it with dominoes?

At first, I tried small boards, made sketches, attempted placements. Every attempt failed.

Then I saw the trick: each domino covers one black and one white square. The mutilated board has 30 blacks and 32 whites (or vice versa). Impossible.

That blew my mind. Tiling wasn’t just geometry — it was parity.

But this parity argument only worked here. For more general tilings, I had no shortcut.

Step 3: The First Wrong Turn — Brute Force

I thought: why not just count all tilings by brute force? For 2×n2 \times n, this works fine (Fibonacci). For 3×n3 \times n, recursion can handle it.

But for an 8×88 \times 8 board? The number of domino tilings is

12,988,816.12,988,816.

Already enormous.

And for larger boards, it explodes beyond imagination. Brute force was hopeless.

Dead end #1.

Step 4: Algebra to the Rescue (Kasteleyn and Pfaffians)

Then I learned a shocking fact: there’s a closed-form formula for the number of domino tilings of an m×nm \times n rectangle.

Kasteleyn (1961) showed that domino tilings can be counted using determinants of adjacency matrices — essentially using linear algebra to encode matchings.

For the 2n×2n2n \times 2n board, the number of tilings is

∏j=1n∏k=1n(4cos⁡2jπ2n+1+4cos⁡2kπ2n+1)1/4.\prod_{j=1}^n \prod_{k=1}^n \left(4\cos^2\frac{j\pi}{2n+1} + 4\cos^2\frac{k\pi}{2n+1}\right)^{1/4}.

I tried plugging in small nn. For n=4n=4 (the 8×88 \times 8 board), this indeed gives 12,988,816.

This was exhilarating — algebra had cracked the puzzle!

But then I realized: the formula was deep, involving Pfaffians, orientations, and heavy machinery. What started as a puzzle had turned into advanced graph theory.

Step 5: Trominoes — A New Abyss

I thought: maybe trominoes (three-square tiles) would be easier.

Wrong.

Take a 2×n2 \times n board. Can you tile it with L-shaped trominoes?

Only if nn is a multiple of 3. Proof: the area is 2n2n, and each tromino covers 3 squares, so 2n2n must be divisible by 3. That’s neat.

But what about tiling a 3×n3 \times n rectangle? I tried drawing cases, making recursive formulas. The casework exploded.

And for arbitrary shapes, I learned the brutal truth: tiling with trominoes is NP-complete.

So a puzzle that looked like fitting Lego pieces was secretly as hard as the hardest problems in computer science.

Dead end #2.

Step 6: Wrong Heuristics

I tried to use “coloring arguments” like with dominoes. For some cases, they ruled out impossibility. But often they failed. Trominoes don’t align with simple chessboard parity.

I tried greedy placement (fill the corners, then recurse). Always led to dead ends.

I tried symmetry-based reasoning. Again, counterexamples arose.

Every intuitive heuristic failed.

Step 7: The Tileability Problem

Then I hit the general question:

Given a region on the square lattice, can it be tiled with a given set of tiles?

This problem is undecidable in full generality. With some sets of tiles, there is no algorithm that always answers.

I was stunned. What started as a game turned into Turing machines.

Dead end #3 — or maybe the whole abyss.

Step 8: Random Tilings and Physics

Just when I thought it couldn’t get stranger, I found random tilings.

Pick a domino tiling of a large rectangle at random. The tilings form patterns: in the middle, randomness; near the edges, frozen regular structures.

This is the arctic circle theorem: in the Aztec diamond tiling, random behavior appears only inside a circle, while the outside freezes.

So tilings weren’t just combinatorics. They were statistical mechanics.

Step 9: Open Problems

Even now, tilings are full of mysteries:

  • Exact enumeration of tromino tilings for general rectangles remains complicated.

  • Tiling arbitrary polyominoes is computationally intractable.

  • Random tilings connect to limit shapes, entropy, and even to algebraic geometry.

  • Wang tilings (with colored edges) are related to aperiodic tilings and the Penrose tiles — which tile the plane but never periodically.

Every step deeper just widened the pit.

Step 10: Climbing Out (With Cuts and Bruises)

Here’s what I carried from the tiling pit:

  • Domino tilings lead to Fibonacci numbers, Pfaffians, and arctic circles.

  • Tromino tilings lead straight into NP-completeness.

  • Coloring arguments sometimes help, sometimes fail.

  • Random tilings tie into physics.

  • General tiling problems touch undecidability itself.

I went in thinking I’d play with Lego blocks. I came out face-to-face with Turing machines and statistical mechanics.

That’s The Problem Pit: a simple game at the surface, an abyss below.


Labels:

Comments

Post a Comment