Fact-checked by Grok 2 weeks ago

Mutilated chessboard problem

The mutilated chessboard problem is a classic impossibility puzzle in mathematics and combinatorics, posed by philosopher Max Black in his 1946 book Critical Thinking.^[1] It asks whether an 8×8 chessboard, with two opposite corner squares removed (leaving 62 squares), can be perfectly tiled using 31 dominoes, where each domino covers exactly two adjacent squares.^[2] The standard proof relies on a simple coloring argument, treating the chessboard as a bipartite graph colored in the traditional alternating black-and-white pattern.^[3] Opposite corners of the board are the same color—both white or both black—resulting in the removal of two squares of the same color and leaving 32 squares of one color and 30 of the other.^[4] Since each domino must cover one black square and one white square, the imbalance makes a complete tiling impossible.^[2] This problem illustrates the power of invariant-based proofs in demonstrating impossibility without exhaustive search, a technique rooted in graph theory and often used in mathematical education to teach proof strategies.^[3] It has inspired numerous generalizations, such as mutilated boards with different removals or higher-dimensional variants, and appears in formal verification contexts where automated theorem provers struggle with its resolution complexity.^[2] Despite its simplicity, the puzzle highlights how subtle structural properties can thwart brute-force approaches, influencing fields from recreational mathematics to computational logic.^[1]

Problem Description

Statement and Setup

The mutilated chessboard problem involves an 8×8 grid, consisting of 64 squares, from which two opposite corners—such as the bottom-left and top-right—are removed, leaving 62 squares.^[3] A domino is defined as a 2×1 tile that covers exactly two adjacent squares, either horizontally or vertically.^[3] The central question is whether it is possible to tile the remaining 62 squares completely with 31 such dominoes, ensuring no overlaps and no gaps.^[3] This puzzle was first posed by philosopher Max Black in his 1946 book Critical Thinking.^[5] In the standard alternating black-and-white coloring of a chessboard, where adjacent squares differ in color, the two opposite corners share the same color—both white or both black.^[6] Removing these two squares of the same color thus leaves an imbalance: 30 squares of one color and 32 of the other.^[6] A text-based representation of the mutilated board (using algebraic notation, with 'X' marking the removed corners at a1 and h8, assuming a1 is black in this example) is as follows:

  a b c d e f g h
8 . . . . . . . X
7 . . . . . . . .
6 . . . . . . . .
5 . . . . . . . .
4 . . . . . . . .
3 . . . . . . . .
2 . . . . . . . .
1 X . . . . . . .
  a b c d e f g h
  a b c d e f g h
8 . . . . . . . X
7 . . . . . . . .
6 . . . . . . . .
5 . . . . . . . .
4 . . . . . . . .
3 . . . . . . . .
2 . . . . . . . .
1 X . . . . . . .
  a b c d e f g h

This configuration highlights the removal of diagonally opposite corners, preserving the board's rectangular shape but altering its total area and color distribution.^[3]

Common Misconceptions

A common intuition leading to the misconception that the mutilated chessboard is tileable stems from the observation that the board has 62 squares remaining after removing two opposite corners, an even number that appears sufficient for coverage by 31 dominoes, each covering two squares.^[7] This overlooks the structural constraints of the board beyond mere count.^[8] Many casual solvers attempt to place dominoes manually, starting from the edges or center, and often succeed in covering large portions of the board before encountering isolated squares that cannot be paired without overlap or gap.^[9] These efforts typically result in frustration, as the tiling seems nearly complete—perhaps covering 60 squares with 30 dominoes—yet leaves two unconnectable remnants, without revealing the underlying reason for the failure.^[7] Another frequent error is the belief that local adjacency of squares guarantees a global tiling, assuming that since most squares are pairwise connectable, the entire board should follow suit, while disregarding the overall parity imbalance across the structure.^[8] This view ignores how removals can disrupt the board's balanced pairing potential. The standard chessboard coloring serves as a subtle indicator of this parity issue, though it is often unnoticed in initial attempts.^[9] For instance, one partial tiling strategy might cover the central 6x6 region completely and pair most border squares, but ultimately strands two disconnected squares of the same type, preventing full coverage.^[7] Such examples reinforce the deceptive appearance of near-success, perpetuating the idea that a complete solution is just a matter of better arrangement rather than inherent impossibility.^[9]

Historical Context

Early Origins

The mutilated chessboard problem is part of a tradition in recreational mathematics exploring the feasibility of covering boards and regions with dominoes, highlighting parity and coverage issues in rectangular grids. Such puzzles fostered investigations into when tilings were possible or impossible. The problem received its first formal statement from British-American philosopher Max Black in 1946, in his book Critical Thinking: An Introduction to Logic and Scientific Method. Black introduced the puzzle in a discussion of logical methods, using it to exemplify a scenario where partial successes (such as tiling smaller mutilated boards) might misleadingly suggest a general solution for the full 8×8 case.^[5] Black's original intent was pedagogical, aimed at illuminating the pitfalls of inductive reasoning: while one could verify tilings for progressively larger boards with two opposite corners removed, extrapolating to the standard chessboard overlooks a subtle imbalance that renders the full tiling impossible. This philosophical framing emphasized the need for deductive rigor over mere pattern observation in mathematical proofs.^[10]

Popularization and Key Publications

The mutilated chessboard problem, first posed by philosopher Max Black in his 1946 book Critical Thinking as an example of critical reasoning, began to attract broader mathematical interest in the 1950s through connections to polyomino tiling. Polyominoes—geometric figures formed by joining equal squares edge-to-edge—provided a framework for studying tiling impossibilities, building conceptual foundations for arguments relying on colorings and invariants in grid-based tilings.^[11] Solomon W. Golomb provided one of the earliest discussions in the context of polyomino research in his 1954 paper "Checker Boards and Polyominoes," where he used the problem to illustrate impossibility in tiling mutilated boards with dominoes. This work laid groundwork for broader studies in combinatorial geometry. The problem's popularization accelerated with George Gamow and Marvin Stern's 1958 book Puzzle-Math, which presented it as an engaging "domino game" puzzle to demonstrate mathematical insight and impossibility proofs.^[12] That same year, Claude Berge included it in Théorie des graphes et ses applications, linking the tiling challenge to graph theory and matching problems in a formal mathematical framework. Martin Gardner significantly boosted public and educational awareness by featuring the problem in his December 1957 Scientific American column on "Mathematical Games," alongside explorations of polyominoes, which introduced it to a wide audience of enthusiasts and educators. By the 1960s, following these key publications, the mutilated chessboard had become a standard puzzle in mathematical education for teaching concepts of parity and invariant-based proofs.^[13]

Core Solution

Coloring Argument

The standard 8×8 chessboard features an alternating black-and-white coloring, where adjacent squares differ in color, yielding exactly 32 black squares and 32 white squares.^[14] This bipartite structure arises because no two squares of the same color share an edge, dividing the board into two equal partitions.^[1] In the mutilated chessboard problem, the two removed squares are diagonally opposite corners, which are always the same color—typically both white if the top-left square is black.^[14] Their removal thus leaves 30 squares of one color (white) and 32 of the other (black), creating an imbalance in the partitions.^[1] Each standard domino, covering two adjacent squares, necessarily spans one black and one white square due to the alternating pattern.^[14] Therefore, any complete tiling with 31 dominoes would cover exactly 31 black squares and 31 white squares, which is impossible given the 30 white and 32 black squares remaining.^[1] More formally, the chessboard can be modeled as a bipartite graph with black and white squares as partitions and edges between adjacent squares; a domino tiling corresponds to a perfect matching.^[1] The size of any matching cannot exceed the size of the smaller partition, here limited to 30, preventing a covering of all 62 squares.^[1]

Alternative Proof Techniques

One notable alternative to the coloring argument is the inductive proof proposed by Shmuel Winograd, which relies on counting the parity of domino placements across rows and columns. Assume a complete domino tiling of the mutilated 8×8 board exists. Consider the seven horizontal lines separating the eight rows; for each such line, the number of vertical dominoes crossing it must be odd because the removed corners (one in the first row and one in the eighth row, assuming standard positioning) disrupt the even pairing of squares in those rows, forcing an imbalance that propagates through the tiling. Since there are seven such crossings, each with an odd count, their total yields an odd number of vertical dominoes. A similar analysis applied to the columns shows an odd number of horizontal dominoes. The total number of dominoes would then be the sum of two odd numbers, which is even, contradicting the required 31 (odd) dominoes for the 62 squares. This parity mismatch establishes the impossibility without reference to colors.^[14] A graph-theoretic perspective models the problem as finding a perfect matching in the grid graph, where vertices represent squares and edges connect horizontally or vertically adjacent ones; the graph is bipartite with partitions corresponding to the chessboard's natural division. To demonstrate no such matching exists, Hall's marriage theorem is applied: for every subset S of vertices in one partition, the neighborhood N(S) must satisfy |N(S)| ≥ |S|. In the mutilated board, the removal of two vertices from the same partition leaves partitions of unequal size (30 and 32). For instance, taking the entire larger partition as S (|S|=32), |N(S)|=30 < |S|, violating the condition and proving no perfect matching (tiling) is possible. This framework generalizes to other mutilated configurations and emphasizes matching deficiencies beyond mere size imbalance.^[9] Finally, computational verification approaches, while not practical for exhaustive enumeration due to the vast search space, provide conceptual confirmation through automated methods. A backtracking algorithm could systematically attempt to place dominoes, pruning invalid partial tilings, but the exponential complexity—on the order of 4 choices per square in the worst case, leading to over 2^{62} potential configurations—renders full exhaustive search infeasible on standard hardware, often exceeding available time and memory even with optimizations. Instead, formal verification tools like SAT solvers or theorem provers offer efficient checks: for instance, encoding the tiling constraints as a satisfiability problem yields an unsatisfiable instance, confirmed by short clausal proofs validated by machine checkers. Such methods underscore the problem's utility in testing automated reasoning systems.^[2]^[1]

Generalizations

Gomory's Theorem

In 1973, mathematician Ralph E. Gomory established a key generalization of the mutilated chessboard problem, proving that an 8×8 chessboard with any two squares of opposite colors removed can always be perfectly tiled with 31 dominoes. This result, known as Gomory's theorem, demonstrates that the color imbalance in the classic impossible case is not only necessary but also sufficient for tilability on the standard chessboard when exactly one square of each color is excised.^[15] The theorem's key insight lies in the preservation of color balance: an intact 8×8 chessboard has 32 black and 32 white squares, and removing one of each color leaves exactly 31 squares of each, ensuring that the bipartite graph of the board (with edges connecting adjacent squares) admits a perfect matching, as required for domino tiling. However, mere balance does not guarantee tilability in general mutilated boards; Gomory's proof specifically leverages the structure of the 8×8 grid to confirm existence.^[16] Gomory's constructive proof relies on the existence of a Hamiltonian cycle in the grid graph of the chessboard, which visits every square exactly once and returns to the start, alternating between black and white squares due to the bipartite nature of the graph. Removing two opposite-color squares from this cycle partitions it into either a single path of 62 squares (if the removed squares are adjacent in the cycle) or two disjoint paths whose lengths sum to 62 (if not).^[16] In both cases, the resulting paths have an even number of squares because the removed vertices belong to different color classes, ensuring even-length segments in the alternating cycle; each such even-length path can then be tiled sequentially with dominoes along its edges, covering the entire remaining board without overlap or gap. For instance, removing two adjacent squares along a row—such as a1 (typically black) and b1 (white)—preserves the color balance and allows tiling via Gomory's method, as the Hamiltonian cycle can be adjusted to form tileable paths around the excision.^[16] This contrasts with the original problem's removal of same-color corners, which disrupts tilability.

Broader Tiling Implications

The mutilated chessboard problem extends naturally to larger even-sided boards, such as 2n × 2n grids under the standard checkerboard coloring. Removing two squares of the same color creates a color imbalance, with n² squares of one color and n² - 2 of the other remaining, rendering domino tiling impossible since each domino covers exactly one black and one white square.^[1] In contrast, removing two squares of opposite colors preserves the equality of n² - 1 black and n² - 1 white squares, allowing a domino tiling via inductive constructions that pair rows or divide the board into smaller rectangles; this generalizes Gomory's result for the 8×8 case to arbitrary even rectangular boards.^[9] Coloring arguments similar to the checkerboard parity extend to mutilated polyominoes and tilings with larger polyominoes beyond dominoes. For trominoes, which cover three squares, a modulo-3 coloring partitions the board into three equal classes; removing squares disrupts the counts unless their colors balance the deficiency appropriately, enabling tiling with straight or L-shaped trominoes when the total area is divisible by 3, such as an 8×8 board minus one square. These modular colorings generalize to tetrominoes and higher polyominoes, where k-color schemes (for k equal to the tile size) detect obstructions in mutilated configurations by quantifying coverage disparities across color classes.^[17] The problem's implications reach further into periodic and toroidal tilings, exemplified by the de Bruijn–Klarner theorem, which provides necessary and sufficient conditions for tiling an m × n rectangle with a × b rectangles: the first row and first column must be tileable, and ab must divide mn. This underscores boundary effects as critical barriers in planar tilings, where edge constraints can prevent coverage even if area conditions hold; in toroidal settings, absent boundaries simplify the problem, permitting tilings solely when the total area is a multiple of the tile area, thus highlighting how mutilations exploit boundary-induced invariants like color parity in the chessboard case.^[18] Computationally, deciding domino tilings for arbitrary mutilations—regions formed by removing any even number of squares from a rectangular board—is solvable in polynomial time, O(n³ polylog n) where n bounds the region's complexity, by modeling the region as a bipartite graph and computing a maximum matching to verify perfect coverage. However, extending to arbitrary polyomino tiles or mutilations with general shapes renders the problem NP-complete, as the search for compatible placements grows exponentially without the bipartite structure of dominoes.^[19]

Applications and Extensions

In Automated Reasoning

In 1964, John McCarthy proposed the mutilated chessboard problem as a challenging benchmark for automated proof discovery in early artificial intelligence systems, particularly highlighting difficulties in formalizing and proving impossibility results using first-order logic theorem provers.^[20] This application tested LISP-based systems, such as those developed in the Stanford Artificial Intelligence Laboratory, where the problem's combinatorial nature exposed limitations in generating creative or invariant-based proofs without human guidance.^[21] The problem has been represented as a planning task in automated reasoning, modeling the chessboard as a state space where each state captures the configuration of uncovered squares and tiling actions correspond to placing dominoes under adjacency and coverage constraints.^[22] This formulation underscores the role of search algorithms in exploring vast state spaces, but brute-force approaches fail due to exponential growth in possibilities for the 62 remaining squares. Early successes in handling the problem involved encoding it propositionally and using satisfiability (SAT) solvers to detect unsatisfiability, as demonstrated by propositional satisfaction algorithms, though these required careful reduction to avoid intractable clause sets.^[21] Limitations persisted in resolution-based provers, where the problem generates exponentially long proofs without invariants, prompting the use of state-space invariants for pruning infeasible paths.^[2] The coloring argument, which reveals the color imbalance as an invariant, serves as a key target for automation in these systems.^[22] Historically, the mutilated chessboard problem demonstrated the critical need for heuristic search techniques in automated reasoning for combinatorial proofs, influencing developments in AI planning and theorem proving by emphasizing representation changes to reduce search complexity.^[23]

In Graph Theory and Algorithms

The mutilated chessboard problem can be reformulated in graph theory as a bipartite matching problem on a grid graph. The chessboard is represented as an 8×8 grid graph where each square corresponds to a vertex, and edges connect vertices representing adjacent squares; the graph is bipartite with partitions corresponding to black and white squares. Removing two opposite corners deletes two vertices from the same partition (e.g., both white), resulting in partitions of unequal size (30 and 32), which precludes a perfect matching since any matching cannot exceed the smaller partition size.^[24]^[4] To computationally verify the absence of a perfect matching, efficient bipartite matching algorithms can be applied to the graph. The Hopcroft-Karp algorithm computes a maximum matching in O(E √V) time, where V is the number of vertices (62 after removals) and E is the number of edges (approximately 112 in the mutilated grid); running it yields a maximum matching of size 30, confirming that 31 dominoes cannot cover the board.^[25] Extensions of this formulation incorporate randomized algorithms for related tiling problems, particularly in scenarios requiring approximate or probabilistic solutions. For instance, the Mulmuley-Vazirani-Vazirani algorithm uses randomization via the isolation lemma to find a perfect matching (or detect its absence) in expected polynomial time, adaptable to mutilated boards for efficient verification in larger defective grids; this approach supports approximate tilings by identifying near-maximum matchings when exact coverage is impossible. Such techniques extend to fault-tolerant computing, where randomized matching helps model resilient layouts under random defects. In VLSI design, the bipartite matching model for domino tilings addresses defect avoidance in chip layouts, treating faulty cells as removed vertices and using maximum matchings to route interconnects or allocate resources around imperfections; post-1980s applications leverage this for yield optimization in integrated circuits, where mutilated-like configurations simulate manufacturing defects.^[25]

References

[1]
[PDF] A Simple Formalization and Proof for the Mutilated Chess Board
Robin- son [15] outlines the history of the problem, citing Max Black as its origina- tor. Anybody can grasp the argument instantly, but even formalizing ...Missing: source | Show results with:source
[2]
[PDF] Clausal Proofs of Mutilated Chessboards
Mutilated chessboard problems have been called a “tough nut to crack” for automated reasoning. They are, for instance, hard for resolution, resulting in ...
[3]
[PDF] A formalization of the mutilated chessboard problem - andrew.cmu.ed
Jul 19, 2019 · The mutilated chessboard problem is often presented as an example of a problem where an “aha!” insight makes the solution obvious. The argument ...
[4]
[PDF] Domino tilings - UC Davis Mathematics
Mar 10, 2021 · These problems are known as “mutilated chessboard” puzzles. The top board cannot be perfectly covered by dominoes, but the bottom two can. ( ...<|control11|><|separator|>
[5]
Revisiting the mutilated chessboard or the many roles of a picture
May 7, 2020 · paper by the way that the first formulation of the mutilated chessboard problem is attributed to Max Black. elements do require insight. Of ...
[6]
Mutilated chessboard problem
The mutilated chessboard problem is a tiling puzzle proposed by philosopher Max Black in his book Critical Thinking (1946). It was later discussed by ...
[7]
Example 7: The case of the mutilated chessboard - PD4CS
Jul 3, 2014 · We can tile a mutilated board only if one white and one black corner are removed (but the problem said corners on opposite sides of a diagonal ...
[8]
Solutions to Martin Gardner's best mathematical puzzles
Oct 27, 2014 · If you were able to cover all but two squares of the mutilated chessboard, the remaining two squares would be of the same colour (the opposite ...Missing: mistakes | Show results with:mistakes
[9]
[PDF] The Mutilated Chess Board - Gathering 4 Gardner
The classic problem then asks - is it possible to cover the board when two opposite corners are removed? The first attempt fails, and the second, and the third, ...
[10]
Solomon Golomb (1932–2016) - Stephen Wolfram Writings
May 25, 2016 · Sol didn't invent polyominoes—though he did invent the name. But what he did was to make systematic what had appeared only in isolated puzzles ...
[11]
[PDF] A Simple Formalization and Proof for the Mutilated Chess Board
The impossibility of tiling the mutilated chess board has been formalized and verified using Isabelle. The formalization is concise because it is expressed.
[12]
Puzzle-math - George Gamow, Marvin Stern - Google Books
Title, Puzzle-math ; Authors, George Gamow, Marvin Stern ; Publisher, Viking Press, 1958 ; ISBN, 0670583359, 9780670583355 ; Length, 119 pages.
[13]
Creative Thinking In Math Classrooms - imaginED
Jun 8, 2017 · Here is another problem, made famous by Martin Gardner, called the Mutilated Chessboard. ... Matt Trask: How To Spend A Math Education So I'm ...
[14]
The mutilated checkerboard
Mar 29, 1999 · However, the mutilated checkerboard has 32 squares of one color and 30 squares of the other color. We regard this proof as creative, because it ...Missing: chessboard | Show results with:chessboard
[15]
Mathematical Gems. by Ross Honsberger - jstor
It is trite that if two diagonally opposite corner squares are removed from an ordinary 8 x 8 chessboard, then the remainder ... (Gomory's theorem) says ...
[16]
[PDF] 2D Tiling: Domino, Tetromino and Percolation
Chessboard, Gomory's Theorem and Hamiltonian Paths. 8 × 8 chessboard is covered fully by non-overlapping dominoes. The puzzle. (Max Black, 1946): if ...
[17]
[PDF] The Mutilated Chessboard Colouring Arguments - User Web Pages
From this disparity, we are led to the conclusion that the mutilated chessboard cannot be tiled by dominoes, no matter how hard one might try. Colouring ...
[18]
[PDF] Tilings - Federico Ardila
The full answer: Theorem. (de Bruijn-Klarner, 1969). An m × n rectangle can be tiled with a × b rectangles if and only if: • The first row and first column ...
[19]
[PDF] Tiling with Squares and Packing Dominos in Polynomial Time - arXiv
Aug 9, 2021 · The mutilated chessboard and the dominos are examples of the type ... Checker boards and polyominoes. The American Mathematical Monthly ...
[20]
[PDF] A TOUGH NUT FOR PROOF PROCEDURES - Stanford University
Abstract. It is well known to be impossible to tile with dominoes a checker- board with two opposite corners deleted.
[21]
https://www-formal.stanford.edu/jmc/creative/node2.html
[22]
The interaction of representation and reasoning - PMC
Figure 2 describes the Mutilated Checker Board Problem, in which a change of representation makes a dramatic difference to the efficiency of problem ...<|control11|><|separator|>
[23]
[PDF] Search: An Overview
example is the mutilated chessboard problem: ... The basic framework, there called heuristic search, was the one called state-space search in the present chapter.
[24]
[PDF] Solutions to Problem Set 5
Oct 12, 2005 · Given a truncated chessboard, show how to construct a bipartite graph G that has a per fect matching if and only if the chessboard can be tiled ...Missing: mutilated theory
[25]
Tiling with Squares and Packing Dominos in Polynomial Time - arXiv
Nov 22, 2020 · In this paper, we consider planar tiling and packing problems with polyomino pieces and a polyomino container P. We give two polynomial time algorithms.