A formal proof that placing the Kingdomino castle in an interior cardinal position necessitates holes in the kingdom

The Problem

One of my family's favorite games is Kingdomino. This 2017 Spiel des Jahres winner is a tile-laying game in which each player builds a kingdom, scoring points for clever placement of similar terrain pieces. As of this writing, I have logged 57 plays of this game, making it one of my most played games. We especially like it with the Age of Giants expansion. The game accomplishes the admirable goal that my five-year-old and I can both enjoy it at our own levels. The strategy is interesting, there's an appropriate level of risk-taking, and it's not so cutthroat that a friendly player won't point out a good move to an inexperienced one.

Each player starts with a square castle piece and draws a 2x1 tile each turn. The tile must be placed adjacent to the initial castle or adjacent to another tile such that at least one terrain edge matches. If you cannot play your tile, you discard it. Your kingdom must fit in a 5x5 grid, and there are only enough turns in the game that, if you are never forced to discard a tile, you will exactly fill the 5x5 space.

Sample ending board with castle in the middle
(Image by sethOn on BoardGameGeek)

It does not have to be the case that your castle is in the middle of the 5x5 grid, although in the base game there is a bonus for this. Depending on what tiles you draw and what combinations you seek, the castle can end up in any position.

After playing the game a few times, we noticed that sometimes players would be forced to have 1x1 "holes" in their kingdoms. That is, we encountered situations where the 2x1 tiles were not covering the 5x5 space. For a long time, we chalked this up to bad play. We believed there must have been some decision made previously that left the player with the necessity for this hole.

The more we played, though, the more we wondered whether the placement of the castle within the 5x5 grid determined whether there had to be a hole. That is, was it less a matter of "bad placement" and more a mathematical necessity based on the position of the castle. I do not remember now who among us first thought of this nor whether it was noticing a pattern or intuition. Once we brought it up, though, we did some post-game experimentation. Sure enough, our experiments seemed to show us that if the castle ended up in one of the interior cardinal positions, you would end up with a hole you could not fill with a 2x1 tile.

Doomed Castle Positions

We took this as a kind of folk wisdom, but my Computer Science sense was tingling. Experimental evidence that these were doomed positions is one thing, but could I write a proof that these positions inevitably led to holes?

I let this sit on the back burner for some time. I have not written a formal proof since writing my dissertation, since that's just not the kind of Computer Science I do. I wrote a ton of them in graduate school, and I remember the general ideas but not many of the specific techniques. It feels to me that we're dealing with a kind of parity problem, that the Kingdomino problem should map to another, more conveniently solved problem. That's a very Computer Science Grad School perspective, by the way: show that your problem can be transformed into an easier problem, and solve that one instead. The lack of inspiration for a similar problem meant that I didn't make any headway on this problem at all. That is, until this morning.

Even though I had not thought of an elegant mathematical solution to the problem, it struck me last night that I could probably approach the problem via proof by contradiction. This one always felt to me like a sort of cudgel, but it works: assume the thing you want to prove false is true, demonstrate that it leads inexorably to an impossible situation, and conclude that it must be true instead. I sat down this morning with a handful of tiles and made my case.

The Proof

Let's assume for the sake of the proof that if we start with our castle in one of the interior cardinal positions (C2, B3, D3, or C4, as shown above as Doomed Castle Positions) that there exists a tiling that produces a full 5x5 kingdom. 

We can assume without loss of generality that the castle starts in position C4. Every other case is symmetric to this one, and for our purposes, starting in any other position is irrelevant. Keep in mind, of course, that at the time you start the game, the castle is not actually fixed in any cell of the grid: it is the placement of the tiles that determine where in the grid the castle ends up. Still, these are the only cases that are relevant to the claim, so we can take it as given.

Step 1: Castle at C4

The space C5 must be filled with a tile, and that tile must be placed horizontally. Assume without loss of generality that we place it over the spaces B5-C5. This covers any other case because of the symmetry of the board: covering C5-D5 would yield the same topology, mirrored.

For the sake of the proof, we will be ignoring the terrain types on the tiles. After all, our assumption is that there is a 5x5 tiling, and so we can assume the player has access to tiles that make these legal moves within the game. Similarly, the tiles could be played in different sequences, but they will yield the same result. Here, for example, the player could have played a piece at D3-D4 for example, but the fact remains that in order to make a complete tiling, they would have to play at C5, as in this step.

Step 2: Play at B5-C5

The space at A5 can only be covered by a tile that spans A4-A5, so that is our next move.

Step 3: Play at A4-A5

Similarly, B4 can only be covered by a tile covering B3-B4.

Step 4: Play at B3-B4

Continue this idea for the next several steps: play a piece into the most constrained position, where only one placement can satisfy the game rules.

Step 5: Play at A2-A3

Step 6: Play at A1-B1

Step 7: Play at B2-C2

Step 8: Play at C1-D1

Step 9: Play at E1-E2

That gives us enough plays to demonstrate the contradiction. There are now two clear positions that must be covered, but cannot both be covered: D2 and C3. Playing to cover D2 will cover D3, but then no tile can legally be played on C3. Playing to cover C3 will cover D3, but then no legal play can cover D2. 

Step 10: Impossible to Satisfy D2 and C3

We have a contradiction, which proves that our initial claim is false. That is, we claimed that there was a 5x5 tiling, but we have shown that it is not possible. Therefore, there is no possible 5x5 tiling of Kingdomino when the castle piece is in an interior cardinal position. Put another way, if your castle is in an interior cardinal position, you will necessarily have an unfilled hole in your final kingdom.

The Implications

One obvious implication of this is for the strategy of Kingdomino. If you desire a 5x5 tiling, ensure that your castle piece is not in one of the interior cardinal positions. Of course, the game is won by score, and so a savvy player might accept such a position if a tile placement yields adequate rewards, but at least this helps such a player fully understand the costs and benefits.

This proof technique still strikes me as inelegant because it doesn't tell us anything about any other board configuration. That is, if we wanted to show any other case, we would have to demonstrate it tediously in the same way. I suspect there are underlying mathematical principles at play here that I am just not seeing.

Thanks for checking this out. If you have some other insight into the topological qualities of the game, or if you have a story about how your own play group discovered this phenomenon, I'd love to hear about it in the comments.

The Update

After my initial post, I shared a link to this on BoardGameGeek's Kingdomino page. Those forums really are a great place to bounce ideas and inspiration around. Ori Artvalion (@SaltyHorse) posted some insights that lead to a much cleaner formulation. Here's a link directly to Ori's post, and I encourage you to check it out! Ori's observation suggests that there are other board positions that lead to a case as I describe above, just as I suspected but could not formalize. Also, that post pointed me toward the mutilated chessboard problem, which now I have a vague recollection of having encountered in grad school, but that was a lifetime ago.