Mathematical Chess Problems Codexery

Mutilated chessboard problem

An impossible domino tiling puzzle on a mutilated chessboard.

Last updated

The mutilated chessboard problem is a tiling puzzle that asks whether a standard 8×8 chessboard with two diagonally opposite corners removed can be covered by 31 dominoes of size 2×1. It is impossible, and its proof relies on a simple coloring argument showing that the board has unequal numbers of squares of each color. The problem has been used as a test case in automated reasoning, creativity, and the philosophy of mathematics.

Quick Facts

Proposed by
Max Black
Year proposed
1946
Board size
8×8
Squares remaining
62
Dominoes required
31
Domino size
2×1

Facts from the source article.

History

The mutilated chessboard problem belongs to the study of domino tilings, a class of problems in statistical mechanics first examined by Ralph H. Fowler and George Stanley Rushbrooke in 1937. Domino tilings have practical applications in pavement design and tatami flooring. Philosopher Max Black introduced the problem in his 1946 book Critical Thinking, hinting at a coloring-based proof of its impossibility. It gained popularity in the 1950s through discussions by Solomon W. Golomb, George Gamow and Marvin Stern, Claude Berge, and Martin Gardner in his Scientific American column.

John McCarthy proposed using the problem in automated reasoning in 1964. In cognitive science, it serves as a test for creative insight, Black’s original aim. Philosophers of mathematics also study it to explore the nature of mathematical proof.

Solution

The mutilated chessboard problem has no solution. A single domino always covers one black square and one white square, so any set of dominoes must cover an equal number of each color. Removing two opposite corners, which share the same color, leaves an imbalance: fewer squares of that color and more of the other. This makes a complete tiling impossible.

The same reasoning applies whenever any two same-colored squares are removed. Other proofs exist. One, by Shmuel Winograd, uses induction. If a row has an odd count of squares not covered by vertical dominoes from the row above, an odd number of vertical dominoes must extend into the next row.

The first row has seven such squares, so each of the seven row pairs contains an odd number of vertical dominoes, giving an odd total. The number of horizontal dominoes must also be odd. The sum of two odd numbers is even, but covering the mutilated board requires 31 dominoes, an odd number. Another proof counts the colored edges along the board’s boundary.

In any tileable region, the counts of black and white boundary edges must be equal, because each domino contributes three edges of each color and internal edges cancel opposite colors. The mutilated board, however, has more edges of one color than the other.

Application to automated reasoning

Domino tiling problems on polyominoes can be solved in polynomial time by converting them into problems in group theory or as instances of bipartite matching. In the latter formulation, a bipartite graph has a vertex for each square and an edge for every pair of adjacent squares; the problem is to find a system of edges touching each vertex exactly once. The graph has more vertices of one color, so it fails the necessary conditions of Hall's marriage theorem, and no matching exists.

The problem can also be solved as a constraint satisfaction problem using semidefinite programming. In 1964, John McCarthy proposed the mutilated chessboard as a hard problem for automated proof systems, formulating it in first-order logic. Most considerations provide solutions in the conceptual sense that do not apply to McCarthy's logic formulation. Despite general methods, it is exponentially hard for resolution to solve McCarthy's logical formulation, highlighting the need for methods that can automatically change to a more suitable problem representation.

Short proofs are possible using resolution with additional variables or stronger proof systems. Higher-level proof assistants such as Isabelle, the Mizar system, and Nqthm can handle the coloring-based impossibility proof directly.

Related problems

A wazir, a piece moving one square vertically or horizontally, cannot start at one corner of a chessboard, visit every square exactly once, and end at the opposite corner. If the starting corner is white, each move flips the square’s color, so any complete tour must end on a black square. The opposite corner, however, is white. The same color-alternation rule makes a knight’s corner-to-corner tour impossible as well.

This type of complete tour underlies Numbrix puzzles, meaning a puzzle with 1 in one corner and 64 in the opposite corner cannot be solved. A related impossibility appears in De Bruijn’s theorem, which proves that a 6×6×6 box cannot be filled with 1×2×4 cuboids. The proof uses a chessboard-style coloring argument similar to the one that rules out the wazir’s tour.

More in Mathematical Chess Problems

Sources

Compiled from Wikipedia and the sources listed below. Text from Wikipedia is available under CC BY-SA 4.0; this entry is adapted from it.

Spotted an error? Know more?

Reader corrections go straight into our review queue. Suggest an edit · How this site is sourced

Comments

Loading…
Open in the interactive codex →