At the end of Chapter 4, we pushed computer science to its absolute breaking point.
Through bitmasks, Transfer Matrices, and the Berlekamp-Massey algorithm, we learned how to tile extremely long hallways. But what if the board is perfectly square and simply very large? What if we want to find the number of domino tilings for a standard $64 \times 64$ checkerboard?
If we try to define a right-edge profile for a $64 \times 64$ board, our bitmask requires $2^{64}$ states. That is 18.4 quintillion edge profiles. We cannot build a transfer matrix for it, and we cannot run a Dynamic Programming loop long enough to feed the sequence to Berlekamp-Massey.
For a board this size, algorithmic iteration is dead. To solve it, we have to ask a physicist.
The Jumpscare
In 1961, a Dutch physicist named Pieter Kasteleyn looked at this exact problem (known in physics as the dimer model).
He didn’t write a single line of code. He didn’t use arrays, bitmasks, or for loops. Instead, through pure statistical mechanics and graph theory, he proved that the exact number of ways to tile any $M \times N$ board is given by this exact closed-form equation:
Just look at that equation for a second.
We are placing rectangular wooden blocks on a grid of squares. There are no circles. There are no angles. Yet, right in the middle of the exact solution is $\pi$ and the cosine function.
Where on earth did trigonometry come from? How does multiplying a bunch of irrational cosine waves together output a perfectly clean, whole integer representing the number of ways to arrange dominoes?
It looks like alien technology. But over the next two chapters, we are going to build this exact formula from scratch. And I promise you, by the end of it, the $\pi$ and the cosines will make perfect, intuitive sense.
To understand it, we have to completely destroy how we look at the board.
Step 1: The Checkerboard
We need to stop looking at the board as a blank grid of squares. Instead, we are going to color it alternating black and white, exactly like a standard chessboard.
Why do we do this? Because it reveals a fundamental, unbreakable physical law of our dominoes: every single domino, whether placed vertically or horizontally, will always cover exactly one black square and exactly one white square.
It is impossible for a domino to cover two black squares or two white squares. It is always a perfect 1-to-1 pairing.
Step 2: The Bipartite Graph
Now that we know a domino is just a bridge between a black square and a white square, we can erase the squares entirely.
Imagine putting a dot (a node) in the center of every square. Then, draw a line (an edge) connecting every node to its immediate neighbors (up, down, left, right).
In graph theory, because our edges only ever connect a black node to a white node, this is called a Bipartite Graph.
We have completely changed the definition of our problem. We are no longer “tiling a board.” We are looking at a web of black and white dots, and we are trying to select a set of lines such that every single dot is connected to exactly one other dot. In mathematics, this is called finding a Perfect Matching.
Step 3: The Adjacency Matrix
To solve a graph, we bring back our old friend: the matrix. But this is not a Transfer Matrix. We don’t care about state transitions anymore. We just want to record which dots are touching.
We create a Bi-Adjacency Matrix (let’s call it $A$). The rows of the matrix represent our Black nodes, and the columns represent our White nodes. If Black Node 1 is touching White Node 1, we put a 1 in the matrix. If they are not touching, we put a 0.
Let’s look at the smallest possible board: a $2 \times 2$ grid (4 squares total).
- Top-Left is Black ($B_1$)
- Bottom-Right is Black ($B_2$)
- Top-Right is White ($W_1$)
- Bottom-Left is White ($W_2$)
Looking at the grid, $B_1$ is touching both $W_1$ and $W_2$. Likewise, $B_2$ is touching both $W_1$ and $W_2$. Our adjacency matrix $A$ looks like this:
$$A = \begin{pmatrix} 1 & 1 \cr 1 & 1 \end{pmatrix}$$The Cancellation Problem
In linear algebra, if you have a bi-adjacency matrix for a bipartite graph, taking the Determinant of that matrix is supposed to help you count the number of perfect matchings.
Let’s try it for our $2 \times 2$ board. The determinant of a $2 \times 2$ matrix is $(ad - bc)$.
$$\det(A) = (1 \times 1) - (1 \times 1) = 0$$The math says there are 0 ways to tile a $2 \times 2$ board. But we know from Chapter 2 that a $2 \times 2$ board has exactly 2 valid tilings (two horizontals, or two verticals).
Why did the determinant output zero? Because of the negative sign in the determinant formula. The matrix successfully found both valid tilings, but it assigned a $+1$ to the horizontal layout and a $-1$ to the vertical layout. When it added them together, they perfectly canceled each other out.
The determinant is mathematically “forgetting” our dominoes because of negative signs.
To fix this, Pieter Kasteleyn had to invent a magic trick.
The Magic Trick (Kasteleyn Orientation)
Why did the determinant fail us? It comes down to how determinants are calculated.
Deep inside the math of a determinant, there is an alternating sign sequence. As it multiplies the different permutations of the matrix to count all the possible combinations, it arbitrarily adds some and subtracts others.
If we have two valid domino layouts, the determinant might count the horizontal layout as $+1$ and the vertical layout as $-1$. They annihilate each other.
Pieter Kasteleyn stared at this problem and realized he needed a mathematical hack. He needed to alter the matrix so that the negative signs baked into the determinant formula would be canceled out by the numbers inside the matrix.
He needed something that, when multiplied, would flip a $-1$ into a $+1$.
In mathematics, there is a very famous number that does exactly that: the imaginary unit, $i$. Because $i = \sqrt{-1}$, we know that $i^2 = -1$.
Kasteleyn introduced a brilliant, simple rule: Weight the dominoes.
- If an edge in our graph represents a horizontal domino, we put a $1$ in the matrix.
- If an edge represents a vertical domino, we put an $i$ in the matrix.
Let’s rebuild our $2 \times 2$ Adjacency Matrix with this new rule. Remember, $B_1$ and $B_2$ are our black squares. $W_1$ and $W_2$ are our white squares. The connections between $B_1 \to W_1$ and $B_2 \to W_2$ are horizontal (weight $1$). The connections between $B_1 \to W_2$ and $B_2 \to W_1$ are vertical (weight $i$).
Our new, modified matrix looks like this:
$$A = \begin{pmatrix} 1 & i \cr i & 1 \end{pmatrix}$$Now, let’s take the determinant again using the exact same $(ad - bc)$ formula:
$$\det(A) = (1 \times 1) - (i \times i)$$$$\det(A) = 1 - (i^2)$$
Because $i^2 = -1$, the equation becomes:
$$\det(A) = 1 - (-1) = 2$$It worked.
The negative sign from the determinant and the negative sign from the imaginary vertical dominoes collided, turned into a positive, and correctly counted the exactly 2 valid tilings of a $2 \times 2$ board.
The Eigenvalue Escape
This wasn’t just a neat trick for a $2 \times 2$ board. Kasteleyn proved that this matrix orientation works for any rectangular grid. If you build an Adjacency Matrix using $1$s for horizontal edges and $i$s for vertical edges, the square root of the absolute value of its determinant will perfectly count the number of domino tilings.
We have officially solved the domino problem without iteration.
But there is one final hurdle. Let’s look at our $64 \times 64$ board again. A $64 \times 64$ board has 4,096 squares. That means our Bipartite Graph has 2,048 Black nodes and 2,048 White nodes.
Our Kasteleyn Matrix is a $2048 \times 2048$ grid of $1$s and $i$s.
For a modern computer, calculating the determinant of a $2048 \times 2048$ matrix is trivial. It would take a fraction of a second. But Pieter Kasteleyn published his paper in 1961. He didn’t have a modern computer. He couldn’t just type numpy.linalg.det(A) into Python.
He had to calculate the determinant of an infinitely scaling matrix by hand.
To do that, he used a fundamental property of linear algebra: the determinant of a matrix is equal to the product of all its eigenvalues.
Instead of trying to calculate the determinant directly, Kasteleyn set out to find the exact eigenvalues of this massive checkerboard matrix. And when you calculate the eigenvalues of a structured grid… that is exactly when the cosines and the $\pi$ appear.