In 1994, the All-Russian Olympiad in Informatics presented a deceptively elegant problem. It didn’t require advanced mathematics, and it didn’t hide behind obscure data structures. It was just a rectangular grid and some $1 \times 2$ tiles.
You can still find the original Russian problem statement in the ITMO archives (look for Problem 2: “Паркет”, or Parquet).
Problem 2: Parquet
You need to completely cover a rectangular room of size N x M (1 ≤ N ≤ 8, 1 ≤ M ≤ 20) with parquet tiles. Each parquet tile is a rectangle of size 1 x 2. The whole rectangle must be covered without breaks or overlapping.
Write a program that calculates the total number of distinct ways to completely cover this room with parquet tiles.
In English literature, this is widely known as the Domino Tiling problem.
I first encountered this problem as a 14-year-old in the 10th grade. Two older members of my local computer club had just returned from that 1994 Olympiad, bringing the problem back with them like a cognitive virus. They sketched it out for the rest of the club, and I was instantly infected by its simplicity. It hijacked my brain, sticking with me for the next three decades (I would end up going to the Olympiad myself the following year, in 1995).
Before we write a single line of code, we must simplify the problem by looking at the edge cases. This is where most students in 1994 started, looking for mathematical shortcuts to save precious CPU time on their 286 hardware.
The Odd $\times$ Odd Board
Before we even try to tile anything, we can eliminate a massive chunk of potential inputs. What if the room is $3 \times 3$? Or $5 \times 7$?
The arithmetic is rigid: a $3 \times 3$ grid has $9$ squares of total area. A single $1 \times 2$ domino covers exactly $2$ squares. Because you cannot break or overlap tiles, there is no mathematical universe where you can sum up enough 2s to equal an odd number like 9.
If the total area $(N \times M)$ is odd, the answer is immediately 0.
Illustration 1: The Impossible Odd Grid
The $1 \times M$ Board
If $N = 1$, the problem is almost insultingly simple.
We know from the previous rule that if $M$ is odd (e.g., $1 \times 3$), it’s impossible. If $M$ is even (e.g., $1 \times 4$), you have no choices to make. You cannot orient any tiles vertically. You must lay all dominoes horizontally, end-to-end. There is exactly 1 distinct way to tile a $1 \times \text{even}$ board.
Illustration 2: The Trivial 1D Case
The $2 \times M$ Board
This is the special case that sets the trap. When $N = 2$, the problem undergoes a startling mathematical metamorphosis. Let’s map out the first few values of $M$ (the columns).
When $M = 1$, the area is 2. There is exactly 1 way to tile it (a single vertical domino).
When $M = 2$, the area is 4. You can use two vertical dominoes side-by-side, or you can stack two horizontal dominoes. There are 2 ways.
When $M = 3$, the area is 6. If we sketch out the permutations, we find exactly 3 ways.
The sequence of answers as $M$ grows is $1, 2, 3...$ If we manually sketched out a $2 \times 4$ grid, we would find exactly $5$ ways. A $2 \times 5$ grid yields exactly $8$ ways.
$1, 2, 3, 5, 8...$
This sequence isn’t an accident; it is the Fibonacci sequence. But why?
Why does a 2D geometric tiling problem suddenly turn into the Fibonacci numbers? It comes down to how the right-most edge of the grid is completed. As the illustration below shows, to finish a $2 \times M$ board, you only have two valid moves:
- Place one vertical domino, which leaves a $2 \times (M-1)$ board left to tile.
- Place two horizontal dominoes, which leaves a $2 \times (M-2)$ board left to tile.
Therefore, the total number of ways to tile a board of length $M$ is simply the sum of the ways to tile the two smaller boards:
$$f(M) = f(M-1) + f(M-2)$$Illustration 3: The Fibonacci Decomposition
Finding this pattern gave many 14-year-olds a false sense of security. It made the problem feel linear, solvable, and tame. They were convinced that every $N$ would generate a simple sequence just like this.
And then they tried to calculate a $3 \times M$ board.