Squares in Domino Tilings

Small Boards For N = 1, the one possible tiling does not contain a square.

Claim. Every domino tiling of an Nx(N+1) board contains a square, for N>1. ^[1]

Proof For sake of contradiction, assume a tiling has no squares. The domino covering the upper left corner must be vertical or horizontal. In either case, this first domino and the no-square requirement forces the placement of a diagonal staircase of dominos. Regardless of board size, this reaches the bottom edge and strands a cell whose only remaining covering would complete a square; contradiction.

▮ starting domino   ▮ forced   ▯ stranded

Small Boards. For N = 1, 2, 3, there are tilings that avoid a non-corner square.

Claim. Every domino tiling of an Nx(N+1) board contains a non-corner square, for N>3.

Proof. For sake of contradiction, assume a tiling has no corner squares. There are four ways the top-left 2x2 can be covered. Each of these forces placement that results in a stranded square, as seen below. The patterns scale to arbitrarily large board sizes. Since these tilings can't be completed, we conclude that every such tiling contains a non-corner square.

▮ starting domino   ▮ forced   ▯ stranded   corner-square zone.

Small Boards For N = 1, 2, 3, 4, 5, there are center-square-free tilings.

Claim. Every domino tiling of an Nx(N+1) board contains a center square, for N>5.

Proof

Take N >= 6. The six centermost cells — and the one-cell overhang of any half-domino — lie in columns 2 .. N, rows 2 .. N-1, so any 2x2 block two of those tiles form is a center square. In the sections below, we will show that each of these center configurations makes it impossible to tile a board when center squares are forbidden.

Naming

First, classify a tiling by its center code: the compass direction (N/S/E/W) from each of the six cells to its domino partner, read row by row (e.g. NEW,WSE). We show these as horizontal blocks, but on boards where N is odd, they are positioned vertically to keep them centered.

Of the 108 locally-valid codes, 39 remain after removing duplicates (by rotation or reflection).

First pass

If two tiles of a code form a 2x2 block, that block is a center square. This drops 29 of the 39.

Ten survivors

Forced-Move Propagation

Each survivor is run through forced-move propagation on the N x (N+1) board, never placing a domino that would complete an interior 2x2. For seven of the ten, this results in a stranded cell. The other three stall out.

The Parallel Three

Next, we need to evaluate these remaining three in more detail. We'll call them "The Parallel Three" because all of their bricks are parallel, unlike the others that were recently eliminated. In a search of boards up to N=13, none of them permit center-square-free tilings, which is promising. But this isn't enough to prove our claim on all large boards.

Observe that contradictions in the previous round came from non-parallel bricks creating cascades of forced pieces ("staircases"). For each of the parallel three, we will place additional parallel pieces that are indirectly forced: filling one of their spots with a brick in any other orientation would result in a cascade of forced pieces that leads to a contradiction.

Eventually a spot turns up where every orientation cascades to a contradiction. Any of them will then do, so we take the north-easternmost, lay it down as one more yellow brick, and let the cascade it causes run on to a stranded cell.

Tap any of the yellow bricks to preview the cascade of forced pieces if it had been placed differently. Tap anywhere on the grid to close this preview.

So each of the three is eliminated without ever searching whole tilings: every step is a local deduction about one cell. But the pattern is recomputed per board rather than proved in general, so the claim still rests on the sizes shown here.