Yamagishi Complexity Torus LabYamagishi Lab

[Paper 627] Whether an $8\times8$ Board Missing Two Squares Can Be Tiled by Dominoes Is Decided by Their Colours Alone

Abstract

The ways to cover a board with $2\times1$ dominoes, without gaps or overlaps, are counted, for the $8\times8$ board itself and for boards with two squares removed. No new theorem or law is claimed.

First, the $8\times8$ board has $12988816$ tilings——counting column by column, remembering which squares stick into the next column, agreed with Kasteleyn’s product formula on every board with sides $2$ to $8$ and even area. The $2\times n$ boards give the Fibonacci numbers $1$, $2$, $3$, $5$, $8$, reaching $89$ at $n=10$ (Section 2).

Second, and this is the core. Removing two squares of the same colour leaves $0$ tilings——coloured like a chessboard, every domino covers one square of each colour. Opposite corners share a colour, so removing them leaves $30$ squares of one colour and $32$ of the other, which cannot match the $31$ of each colour that $31$ dominoes cover. Counting all $2016$ ways to remove two squares, all $992$ removing the same colour gave $0$ (Section 3).

Third, removing two squares of different colours leaves a board that can be tiled, wherever they are——all $1024$ removals of different colours gave at least one tiling. The number depends on where: the fewest is $418000$ ($0.032182$ of the full board) and the most $6494408$, reached when a corner and its neighbour are removed, exactly half the full board (Section 4).

Fourth, on large boards the logarithm per square approaches Catalan’s constant——the natural logarithm of the number of tilings divided by the number of squares is $0.255931$ for $8\times8$ and $\mathbf{0.290072}$ for $200\times200$, differing by $0.001489$ from Catalan’s constant $G$ divided by $\pi$, $0.291561$ (Section 5).

Keywords: domino tiling, mutilated chessboard, Gomory’s theorem, Kasteleyn formula, perfect matching.

Scope (what is not claimed)

No new theorem or law is claimed——the product formula for the number of tilings (Kasteleyn, and Temperley and Fisher, $1961$), that the board without opposite corners cannot be tiled (the mutilated chessboard problem), that removing two squares of different colours always leaves a tileable board (known as Gomory’s theorem), and the large-board limit $G/\pi$ are all known. Gomory’s theorem is not proved——it is only confirmed by counting the $1024$ removals of different colours on $8\times8$. General boards with holes and pieces other than dominoes are not treated. Relation to earlier papers: Paper 601 showed that half of the Fifteen Puzzle’s positions are out of reach because the board can be coloured in two——the same colouring here makes a board missing two squares of one colour untileable. Paper 625 showed that since a knight changes colour at every move, a board with an odd number of squares has no knight’s tour returning to its start——here, since a domino covers one square of each colour, the colours must balance. What is added is matching the column-by-column count with the product formula, counting all $2016$ ways to remove two squares and matching them with the colour count, and placing the separator on the colours of the two squares removed.

1. Notation and the Question

Setting: a board of $m$ rows and $n$ columns is covered, without gaps or overlaps, by $2\times1$ dominoes each covering two adjacent squares. The number of ways is $T(m,n)$. Squares are written $(r,c)$ with rows and columns counted from $0$, and coloured by the parity of $r+c$.

Question: how many tilings does $8\times8$ have, and when two squares are removed, what decides whether it can be tiled?

2. Tilings of the Whole Board

Computation 2.1: tilings were counted column by column, remembering which squares stick into the next column. For boards with both sides even they were also found by Kasteleyn’s product formula

$$T(m,n)=\prod_{j=1}^{m/2}\prod_{k=1}^{n/2}\left(4\cos^2\frac{\pi j}{m+1}+4\cos^2\frac{\pi k}{n+1}\right)$$

(for a board with one odd side, the upper limit for that side becomes $(m+1)/2$). The two agreed on every board with sides $2$ to $8$ and even area.

boardcountedproduct formula
$2\times8$$34$$34.000000$
$4\times4$$36$$36.000000$
$6\times6$$6728$$6728.000000$
$8\times8$$12988816$$12988816.000000$

Observation 2.2 the $2\times n$ boards give $1$, $2$, $3$, $5$, $8$, $13$, $21$, $34$, $55$, $89$, the Fibonacci numbers. The leftmost column is filled either by one vertical domino or by two horizontal dominoes filling two columns, leaving a $2\times(n-1)$ or a $2\times(n-2)$ board——the rule of adding the previous two comes from how the edge is filled.

3. Removing Two Squares of the Same Colour

Computation 3.1: the $8\times8$ board has $32$ squares of each colour. The opposite corners $(0,0)$ and $(7,7)$ share a colour, and removing them leaves $30$ of one colour and $32$ of the other. $31$ dominoes cover exactly $31$ squares of each colour. Counting all $992$ removals of two squares of the same colour column by column, every one gave $0$.

Observation 3.2 this is the core: a domino covers two adjacent squares, and adjacent squares always differ in colour, so however it is placed it covers one of each. So for a tiling, the two colours must be equal in number——removing two of the same colour puts them $2$ apart, and the count is fixed at $0$ before any placement is tried. The count never gave anything but $0$ over these $992$.

4. Removing Two Squares of Different Colours

Computation 4.1: all $1024$ removals of two squares of different colours were counted. Every one could be tiled at least once.

squares removed (example)tilingsratio to the full board
fewest: $(0,1)$ and $(6,6)$$418000$$0.032182$
adjacent: $(0,0)$ and $(0,1)$$6494408$$0.500000$
top-left and bottom-left corners: $(0,0)$ and $(7,0)$$2436304$—
most: $(7,6)$ and $(7,7)$$6494408$$0.500000$

Observation 4.2 removing a corner and its neighbour leaves exactly half the tilings of the full board. On the full board the corner square is covered by either a horizontal or a vertical domino. Reflecting the board in its diagonal swaps the two, so each takes half——the tilings of the board without a corner and its neighbour are as many as the tilings with a domino placed there, so they number half of $12988816$, $6494408$.

Observation 4.3 with different colours, the number of tilings varies with the place from about $0.03$ to $0.5$ of the full board, but never reaches $0$. Whether the colours match decides whether it is $0$; the place decides how many——the two questions answer different quantities.

5. Large Boards

Computation 5.1: for square boards, the natural logarithm of the number of tilings divided by the number of squares was found from the product formula.

board$8\times8$$20\times20$$60\times60$$200\times200$$G/\pi$
log per square$0.255931$$0.276908$$0.286619$$\mathbf{0.290072}$$0.291561$

The difference between $200\times200$ and $G/\pi$ is $0.001489$. The larger the board, the weaker the edges and the closer the value.

6. The Separator

Observation 6.1 the separator is whether the two squares removed share a colour. If they do, all $992$ give $0$; if not, all $1024$ can be tiled——the place moves the number of tilings from $418000$ to $6494408$, but does not move whether there are any.

Observation 6.2 beside Paper 601 and Paper 625. In Paper 601, the blank changing colour at every move halved the reachable positions of the Fifteen Puzzle; in Paper 625, the knight changing colour at every move ruled out closed tours on odd boards——here, a domino covering one square of each colour makes boards missing two of one colour untileable. In all three, the chessboard colouring decides the impossible before any placement is tried.

Observation 6.3 what is not said. Gomory’s theorem is not proved for general boards, and general boards with holes and pieces other than dominoes are not treated——what is shown is the agreement of two routes and the count of all $2016$ ways to remove two squares from $8\times8$.

7. Roll Call and Closing

  1. $8\times8$ has $12988816$ tilings (Computation 2.1): two routes agree.
  2. $2\times n$ gives the Fibonacci numbers (Observation 2.2): from how the edge is filled.
  3. same colour removed leaves $30$ and $32$ (Computation 3.1): cannot match $31$ dominoes.
  4. all $992$ same-colour removals give $0$ (Computation 3.1): by counting.
  5. a domino covers one of each colour (Observation 3.2): the core.
  6. all $1024$ different-colour removals can be tiled (Computation 4.1): agrees with Gomory’s theorem.
  7. the fewest is $418000$ (Computation 4.1): $0.032182$ of the full board.
  8. a corner and its neighbour give exactly half (Observation 4.2): by the diagonal reflection.
  9. $\mathbf{0.290072}$ for $200\times200$ (Computation 5.1): approaching $G/\pi$.
  10. the colouring decides before placement (Observation 6.2): Paper 601 and Paper 625.

Closing: The $8\times8$ board has $12988816$ domino tilings, and counting column by column agreed with Kasteleyn’s product formula. Whether a board missing two squares can be tiled is decided by their colours alone——since a domino always covers one square of each colour, all $992$ removals of the same colour gave $0$ and all $1024$ removals of different colours could be tiled. The place moves the number of tilings from $418000$ to $6494408$, but not whether it is $0$. On large boards the logarithm per square approaches $G/\pi$. Placed among the earlier papers——the chessboard colouring that decided the unreachable positions in Paper 601 and the tours that cannot return in Paper 625 here decides the boards that cannot be tiled. To be honest——Gomory’s theorem is only counted on $8\times8$, not proved for general boards.

References

  1. Kasteleyn, P. W. (1961). The statistics of dimers on a lattice: I. The number of dimer arrangements on a quadratic lattice. Physica.
  2. Temperley, H. N. V., & Fisher, M. E. (1961). Dimer problem in statistical mechanics—an exact result. Philosophical Magazine.
  3. Yamagishi, Y. (2026). Half of the Fifteen Puzzle’s Positions Can Never Be Reached [Paper 601]. Zenodo. 10.5281/zenodo.22805752
  4. Yamagishi, Y. (2026). On a Board with an Odd Number of Squares, No Knight’s Tour Returns to Its Start [Paper 625]. Zenodo. 10.5281/zenodo.23014535

Reference

Yamagishi, Y. (2026). Whether an $8\times8$ Board Missing Two Squares Can Be Tiled by Dominoes Is Decided by Their Colours Alone [Paper 627]. YOI: https://www.yamagishiyuuki.com/yoi/627
DOI: 10.5281/zenodo.23014541
ORCID: 0009-0006-8587-3450

PDF (English) · PDF (Japanese) · Date proof of the English PDF (OpenTimestamps .ots) · SHA256SUMS

The record page for this paper (in Japanese, with the PDFs in each language and the date proof): YOI 627. This paper is a preprint and has not been peer reviewed.