View source for Mutilated chessboard problem

{{Short description|On domino tiling after removing two corners}}
{{good article}}
{{Use mdy dates|cs1-dates=ly|date=October 2022}}
{{Use list-defined references|date=October 2022}}
[[File:Mutilated chessboard vectorized.svg|thumb|The mutilated chessboard]]
[[File:Mutilated chessboard problem example.jpg|thumb|upright|Unsuccessful solution to the mutilated chessboard problem: as well as the two corners, two center squares remain uncovered.]]
The '''mutilated chessboard problem''' is a [[tiling puzzle]] posed by [[Max Black]] in 1946 that asks:

<blockquote>Suppose a standard 8×8 [[chessboard]] (or [[checkerboard]]) has two diagonally opposite corners removed, leaving 62 squares. Is it possible to place 31 [[dominoes]] of size 2×1 so as to cover all of these squares?</blockquote>

It is an [[impossible puzzle]]: there is no [[domino tiling]] meeting these conditions. One proof of its impossibility uses the fact that, with the corners removed, the chessboard has 32 squares of one color and 30 of the other, but each domino must cover equally many squares of each color. More generally, if any two squares are removed from the chessboard, the rest can be tiled by dominoes if and only if the removed squares are of different colors. This problem has been used as a test case for [[automated reasoning]], [[creativity]], and the [[philosophy of mathematics]].

==History==
The mutilated chessboard problem is an instance of [[domino tiling]] of grids and [[polyomino]]es, also known as "dimer models", a general class of problems whose study in [[statistical mechanics]] dates to the work of [[Ralph H. Fowler]] and [[George Stanley Rushbrooke]] in 1937.{{r|fowler-rushbrooke}} Domino tilings also have a long history of practical use in pavement design and the arrangement of [[tatami]] flooring.{{r|tatami}}

The mutilated chessboard problem itself was proposed by philosopher [[Max Black]] in his book ''Critical Thinking'' (1946), with a hint at the coloring-based solution to its impossibility.{{r|black|robinson}} It was popularized in the 1950s through later discussions by  [[Solomon W. Golomb]] (1954),{{r|golomb}} [[George Gamow]] and Marvin Stern (1958),{{r|gamow-stern}} [[Claude Berge]] (1958),{{r|robinson|berge}} and [[Martin Gardner]] in his ''[[Scientific American]]'' column "[[List of Martin Gardner Mathematical Games columns|Mathematical Games]]" (1957).{{r|gardner}}

The use of the mutilated chessboard problem in [[automated reasoning]] stems from a proposal for its use by [[John McCarthy (computer scientist)|John McCarthy]] in 1964.{{r|mccarthy64|kerber-pollet}} It has also been studied in [[cognitive science]] as a test case for creative insight,{{r|kaplan-simon|akin-akin|bgvd}} Black's original motivation for the problem.{{r|black}} In the [[philosophy of mathematics]], it has been examined in studies of the nature of [[mathematical proof]].{{r|mackenzie|kerber|tanswell|starikova-vanbendegem}}

== Solution ==
The puzzle is impossible to complete. A domino placed on the chessboard will always cover one white square and one black square. Therefore, any collection of dominoes placed on the board will cover equal numbers of squares of each color. But any two opposite squares have the same color: both black or both white. If they are removed, there will be fewer squares of that color and more of the other color, making the numbers of squares of each color unequal and the board impossible to cover.{{r|gardner}} The same idea shows that no [[domino tiling]] can exist whenever any two squares of the same color (not just the opposite corners) are removed from the chessboard.{{r|honsberger}}

Several other proofs of impossibility have also been found. A proof by [[Shmuel Winograd]] starts with induction. In a given tiling of the board, if a row has an odd number of squares not covered by vertical dominoes from the previous row, then an odd number of vertical dominoes must extend into the next row. The first row trivially has an odd number of squares (namely, 7) not covered by dominoes of the previous row. Thus, by induction, each of the seven pairs of consecutive rows houses an odd number of vertical dominoes, producing an odd total number. By the same reasoning, the total number of horizontal dominoes must also be odd. As the sum of two odd numbers, the total number of dominoes—vertical and horizontal—must be even. But to cover the mutilated chessboard, 31 dominoes are needed, an odd number.{{r|mccarthy99|mendelsohn}} Another method counts the edges of each color around the boundary of the mutilated chessboard. Their numbers must be equal in any tileable region of the chessboard, because each domino has three edges of each color, and each internal edge between dominoes pairs off boundaries of opposite colors. However, the mutilated chessboard has more edges of one color than the other.{{r|propp}}

[[File:Gomory's theorem.svg|thumb|upright=1.35|Gomory's theorem: Removing any two oppositely-colored squares of a chessboard leaves a region that can be tiled by dominoes. The two removed squares partition a [[Hamiltonian cycle]] through the squares into one (left) or two (right) paths through an even number of squares, allowing the modified chessboard to be tiled by dominoes laid along the paths.]]
[[File:Equicolored unmatchable.svg|thumb|upright|A region of the chessboard that has no domino tiling, but for which coloring-based impossibility proofs do not work]]
{{anchor|Gomory's theorem}}If two squares of opposite colors are removed, then the remaining board can always be tiled with dominoes; this result is '''Gomory's theorem''',{{r|watkins}} after mathematician [[Ralph E. Gomory]], whose proof was published in 1973.{{r|honsberger|mendelsohn}} Gomory's theorem can be proven using a [[Hamiltonian cycle]] of the [[grid graph]] formed by the chessboard squares. The removal of any two oppositely colored squares splits this cycle into two paths with an even number of squares each. Both of these paths are easy to partition into dominoes by following them.{{r|watkins}} Gomory's theorem is specific to the removal of only one square of each color. Removing larger numbers of squares, with equal numbers of each color, can result in a region that has no domino tiling, but for which coloring-based impossibility proofs do not work.{{r|wright}}

==Application to automated reasoning==
Domino tiling problems on [[polyomino]]es, such as the mutilated chessboard problem, can be solved in [[polynomial time]], either by converting them into problems in [[group theory]],{{r|propp|thurston}} or as instances of [[bipartite matching]]. In the latter formulation, one obtains a [[bipartite graph]] with a vertex for each available chessboard square and an edge for every pair of adjacent squares; the problem is to find a system of edges that touches each vertex exactly once. As in the coloring-based proof of the impossibility of the mutilated chessboard problem, the fact that this graph has more vertices of one color than the other implies that it fails the necessary conditions of [[Hall's marriage theorem]], so no matching exists.{{r|wright|urquhart|bpmb}} The problem can also be solved by formulating it as a [[constraint satisfaction problem]], and applying [[semidefinite programming]] to a [[Relaxation (approximation)|relaxation]].{{r|semidefinite}}

In 1964, [[John McCarthy (computer scientist)|John McCarthy]] proposed the mutilated chessboard as a hard problem for [[automated proof]] systems, formulating it in [[first-order logic]] and asking for a system that can automatically determine the unsolvability of this formulation.{{r|mccarthy64}} Most considerations of this problem provide solutions "in the conceptual sense" that do not apply to McCarthy's logic formulation of the problem.{{r|andrews-bishop}} Despite the existence of general methods such as those based on graph matching, it is exponentially hard for [[Resolution (logic)|resolution]] to solve McCarthy's logical formulation of the problem,{{r|dantchev-riis|alekhnovich|razborov}} highlighting the need for methods in [[artificial intelligence]] that can automatically change to a more suitable problem representation{{r|korf}} and for [[knowledge representation]] systems that can manage the equivalences between different representations.{{r|kerber-pollet}} Short proofs are possible using resolution with additional variables,{{r|krishnamurthy}} or in stronger proof systems allowing the expression of avoidable tiling patterns that can prune the search space.{{r|clausal}} Higher-level [[proof assistant]]s are capable of handling the coloring-based impossibility proof directly; these include [[Isabelle (proof assistant)|Isabelle]],{{r|isabelle}} the [[Mizar system]],{{r|mizar}} and [[Nqthm]].{{r|subramanian}}
{{Clear}}

== Related problems ==
{{Chess diagram small
| tright
| numbers=neither
| letters=neither
|
|md|  |  |  |  |  |  |
|  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |oo
| Wazir's tour problem
}}
A similar problem asks if a [[wazir (chess)|wazir]] starting at a corner square of an ordinary chessboard can visit every square exactly once, and finish at the opposite corner square. The wazir is a [[fairy chess piece]] that can move only one square vertically or horizontally (not diagonally). Using similar reasoning to the mutilated chessboard problem's classic solution, this wazir's tour does not exist. For example, if the initial square is white, as each move alternates between black and white squares, the final square of any complete tour is black. However, the opposite corner square is white.{{r|wazir}} This sort of tour of a chessboard also forms the basis of a type of puzzle called [[Numbrix]], which asks for a tour in which the positions of certain squares match given clues.{{r|hanson-nash}} The impossibility of a corner-to-corner tour shows the impossibility of a Numbrix puzzle with the clues 1 in one corner and 64 in the opposite corner.

[[De Bruijn's theorem]] concerns the impossibility of packing certain [[cuboid]]s into a larger cuboid. For instance, it is impossible, according to this theorem, to fill a {{nowrap|6 × 6 × 6}} box with {{nowrap|1 × 2 × 4}} cuboids. The proof uses a similar chessboard-coloring argument to the mutilated chessboard problem.{{r|debruijn}}
{{clear}}

== References ==
{{reflist|refs=

<ref name=akin-akin>{{citation
 | last1 = Akin | first1 = Ömer
 | last2 = Akin | first2 = Cem
 | date = January 1998
 | doi = 10.1016/s0926-5805(97)00057-5
 | issue = 2–3
 | journal = Automation in Construction
 | pages = 123–138
 | title = On the process of creativity in puzzles, inventions, and designs
 | volume = 7}}</ref>

<ref name=alekhnovich>{{citation
 | last = Alekhnovich | first = Michael
 | doi = 10.1016/S0304-3975(03)00395-5 | doi-access = free
 | issue = 1–3
 | journal = [[Theoretical Computer Science (journal)|Theoretical Computer Science]]
 | mr = 2020358
 | pages = 513–525
 | title = Mutilated chessboard problem is exponentially hard for resolution
 | volume = 310
 | year = 2004}}</ref>

<ref name=andrews-bishop>{{citation
 | last1 = Andrews
 | first1 = Peter B.
 | last2 = Bishop
 | first2 = Matthew
 | editor1-last = Miglioli
 | editor1-first = Pierangelo
 | editor2-last = Moscato
 | editor2-first = Ugo
 | editor3-last = Mundici
 | editor3-first = Daniele
 | editor4-last = Ornaghi
 | editor4-first = Mario
 | contribution = On sets, types, fixed points, and checkerboards
 | contribution-url = https://gtps.math.cmu.edu/tw96.ps.Z
 | doi = 10.1007/3-540-61208-4_1
 | pages = 1–15
 | publisher = Springer
 | quote = most treatments of the problem in the literature solve it in the conceptual sense, but do not actually provide proofs of the theorem in either of McCarthy's original formulations
 | series = Lecture Notes in Computer Science
 | title = Theorem Proving with Analytic Tableaux and Related Methods, 5th International Workshop, TABLEAUX '96, Terrasini, Palermo, Italy, May 15–17, 1996, Proceedings
 | volume = 1071
 | year = 1996
 | isbn = 978-3-540-61208-7
 | access-date = 2022-07-18
 | archive-date = 2022-07-18
 | archive-url = https://web.archive.org/web/20220718075425/https://gtps.math.cmu.edu/tw96.ps.Z
 | url-status = live
 }}</ref>

<ref name=berge>{{citation
 | last = Berge | first = Claude | author-link = Claude Berge
 | language = fr
 | page = 176
 | publisher = Dunod
 | title = Théorie des graphes et ses applications
 | year = 1958}}</ref>

<ref name=bgvd>{{citation
 | last1 = Bilalić | first1 = Merim
 | last2 = Graf | first2 = Mario
 | last3 = Vaci | first3 = Nemanja
 | last4 = Danek | first4 = Amory H.
 | date = August 2019
 | doi = 10.1111/cogs.12771 | doi-access = free
 | issue = 8
 | journal = [[Cognitive Science (journal)|Cognitive Science]]
 | title = When the solution is on the doorstep: Better solving performance, but diminished aha! experience for chess experts on the mutilated checkerboard problem
 | volume = 43| pages = e12771
 | pmid = 31446653
 }}</ref>

<ref name=black>{{citation
 | last = Black | first = Max | author-link = Max Black
 | pages = 157, 433
 | publisher = Prentice Hall
 | title = Critical Thinking: An Introduction To Logic And Scientific Method
 | year = 1946}}</ref>

<ref name=bpmb>{{citation
 |last1            = Codel
 |first1           = Cayden R.
 |last2            = Reeves
 |first2           = Joseph E.
 |last3            = Heule
 |first3           = Marijn J. H.
 |author3-link     = Marijn Heule
 |last4            = Bryant
 |first4           = Randal E.
 |editor1-last     = Balyo
 |editor1-first    = Tomáš
 |editor2-last     = Froleyks
 |editor2-first    = Nils
 |editor3-last     = Heule
 |editor3-first    = Marijn
 |editor4-last     = Iser
 |editor4-first    = Markus
 |editor5-last     = Järvisalo
 |editor5-first    = Matti
 |editor6-last     = Suda
 |editor6-first    = Martin
 |contribution     = Bipartite perfect matching benchmarks
 |contribution-url = https://www.cs.cmu.edu/~jereeves/research/bipart-paper.pdf
 |hdl              = 10138/333647
 |location         = Helsinki
 |pages            = 52–53
 |publisher        = Department of Computer Science, University of Helsinki
 |title            = Proceedings of SAT Competition 2021: Solver and Benchmark Descriptions
 |series           = Department of Computer Science Report Series B
 |volume           = B-2021-1
 |year             = 2021
 |access-date      = 2022-07-18
 |archive-date     = 2022-07-18
 |archive-url      = https://web.archive.org/web/20220718194032/https://www.cs.cmu.edu/~jereeves/research/bipart-paper.pdf
 |url-status       = live
}}</ref>

<ref name=clausal>{{citation
 | last1 = Heule | first1 = Marijn J. H. | author1-link = Marijn Heule
 | last2 = Kiesl | first2 = Benjamin
 | last3 = Biere | first3 = Armin
 | editor1-last = Badger | editor1-first = Julia M.
 | editor2-last = Rozier | editor2-first = Kristin Yvonne | editor2-link = Kristin Yvonne Rozier
 | contribution = Clausal proofs of mutilated chessboards
 | doi = 10.1007/978-3-030-20652-9_13
 | pages = 204–210
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = NASA Formal Methods – 11th International Symposium, NFM 2019, Houston, TX, USA, May 7–9, 2019, Proceedings
 | volume = 11460
 | year = 2019| isbn = 978-3-030-20651-2 | s2cid = 92989148 }}</ref>

<ref name=dantchev-riis>{{citation
 | last1 = Dantchev
 | first1 = Stefan S.
 | last2 = Riis
 | first2 = Søren
 | contribution = 'Planar' tautologies hard for resolution
 | contribution-url = https://dro.dur.ac.uk/670/1/
 | doi = 10.1109/SFCS.2001.959896
 | pages = 220–229
 | publisher = IEEE Computer Society
 | title = 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14–17 October 2001, Las Vegas, Nevada, USA
 | title-link = Symposium on Foundations of Computer Science
 | year = 2001
 | s2cid = 18849777
 | access-date = 18 July 2022
 | archive-date = 14 September 2022
 | archive-url = https://web.archive.org/web/20220914190415/https://dro.dur.ac.uk/670/1/
 | url-status = live
 }}</ref>

<ref name=debruijn>{{citation
 | last = de Bruijn | first = N. G. | author-link = Nicolaas Govert de Bruijn
 | doi = 10.2307/2316785
 | journal = [[The American Mathematical Monthly]]
 | mr = 0234841
 | pages = 37–40
 | title = Filling boxes with bricks
 | volume = 76
 | year = 1969| issue = 1 | jstor = 2316785 | url = https://research.tue.nl/nl/publications/filling-boxes-with-bricks(e45f1645-f5f4-4f3c-8370-0a8d26d470d8).html }}</ref>

<ref name=fowler-rushbrooke>{{citation
 | last1 = Fowler | first1 = R. H. | author1-link = Ralph H. Fowler
 | last2 = Rushbrooke | first2 = G. S. | author2-link = George Stanley Rushbrooke
 | doi = 10.1039/tf9373301272
 | journal = [[Transactions of the Faraday Society]]
 | page = 1272
 | title = An attempt to extend the statistical theory of perfect solutions
 | volume = 33
 | year = 1937}}</ref>

<ref name=gamow-stern>{{citation
 | last1 = Gamow | first1 = George | author1-link = George Gamow
 | last2 = Stern | first2 = Marvin
 | contribution = Domino game
 | isbn = 978-0-333-08637-7
 | pages = 87–90
 | publisher = Viking Press
 | title = Puzzle-Math
 | year = 1958}}</ref>

<ref name=gardner>{{citation
 | last = Gardner | first = Martin | author-link = Martin Gardner
 | date = February 1957
 | department = Mathematical Games
 | issue = 2
 | journal = [[Scientific American]]
 | jstor = 24941903
 | pages = 152–158
 | title = An assortment of maddening puzzles
 | volume = 196| doi = 10.1038/scientificamerican0257-152 }}; for solution, see
{{citation
 | last = Gardner | first = Martin | author-link = Martin Gardner
 | date = March 1957
 | department = Mathematical Games
 | issue = 3
 | journal = [[Scientific American]]
 | jstor = 24940785
 | pages = 160–168
 | title = Some old and new versions of ticktacktoe, plus the answers to last month's puzzles
 | volume = 196| doi = 10.1038/scientificamerican0357-160 }}. Reprinted in ''My Best Mathematical and Logic Puzzles'' (Dover Publications, 1994), pages 2 and 39.</ref>

<ref name=golomb>{{citation
 | last = Golomb | first = S. W. | author-link = Solomon W. Golomb
 | doi = 10.1080/00029890.1954.11988548
 | journal = [[The American Mathematical Monthly]]
 | jstor = 2307321
 | mr = 67055
 | pages = 675–682
 | title = Checker boards and polyominoes
 | volume = 61
 | year = 1954| issue = 10 }}</ref>

<ref name=hanson-nash>{{citation
 | last1 = Hanson | first1 = Mary Grace
 | last2 = Nash | first2 = David A.
 | arxiv = 1706.09389
 | date = Spring 2018
 | issue = 8
 | journal = [[Pi Mu Epsilon Journal]]
 | pages = 505–514
 | title = Minimal and maximal Numbrix puzzles
 | volume = 14}}</ref>

<ref name=honsberger>{{citation
 | last = Honsberger | first = R. | author-link = Ross Honsberger
 | contribution = Gomory's theorem
 | pages = 65–67
 | publisher = Mathematical Association of America
 | title = Mathematical Gems I
 | year = 1973}}</ref>

<ref name=isabelle>{{citation
 | last = Paulson
 | first = Lawrence C.
 | doi = 10.1093/jigpal/9.3.475
 | issue = 3
 | journal = Logic Journal of the IGPL
 | mr = 1828741
 | pages = 475–485
 | title = A simple formalization and proof for the mutilated chess board
 | url = https://www.cl.cam.ac.uk/~lp15/papers/Reports/mutil.pdf
 | volume = 9
 | year = 2001
 | access-date = 2022-07-18
 | archive-date = 2022-08-08
 | archive-url = https://web.archive.org/web/20220808125039/https://www.cl.cam.ac.uk/~lp15/papers/Reports/mutil.pdf
 | url-status = live
 }}</ref>

<ref name=kaplan-simon>{{citation
 | last1 = Kaplan | first1 = Craig A.
 | last2 = Simon | first2 = Herbert A. | author2-link = Herbert A. Simon
 | date = July 1990
 | doi = 10.1016/0010-0285(90)90008-r
 | issue = 3
 | journal = [[Cognitive Psychology (journal)|Cognitive Psychology]]
 | pages = 374–419
 | title = In search of insight
 | volume = 22| s2cid = 54334455
 }}</ref>

<ref name=kerber>{{citation
 | last = Kerber | first = Manfred
 | editor1-last = Wyatt | editor1-first = Jeremy L.
 | editor2-last = Petters | editor2-first = Dean D.
 | editor3-last = Hogg | editor3-first = David C.
 | contribution = A proof and some representations
 | doi = 10.1007/978-3-319-06614-1_5
 | pages = 65–73
 | publisher = Springer International Publishing
 | series = Cognitive Systems Monographs
 | title = From Animals to Robots and Back: Reflections on Hard Problems in the Study of Cognition, A Collection in Honour of Aaron Sloman
 | volume = 22
 | year = 2014| isbn = 978-3-319-06613-4
 }}</ref>

<ref name=kerber-pollet>{{citation
 | last1 = Kerber | first1 = Manfred
 | last2 = Pollet | first2 = Martin
 | editor-last = Kohlhase | editor-first = Michael
 | contribution = A tough nut for mathematical knowledge management
 | contribution-url = https://www.cs.bham.ac.uk/~mmk/papers/05-MKM.html
 | doi = 10.1007/11618027_6
 | pages = 81–95
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = Mathematical Knowledge Management, 4th International Conference, MKM 2005, Bremen, Germany, July 15-17, 2005, Revised Selected Papers
 | volume = 3863
 | year = 2005| isbn = 978-3-540-31430-1
 }}</ref>

<ref name=korf>{{citation
 | last = Korf | first = Richard E.
 | doi = 10.1016/0004-3702(80)90033-8
 | issue = 1
 | journal = [[Artificial Intelligence (journal)|Artificial Intelligence]]
 | mr = 587851
 | pages = 41–78
 | title = Toward a model of representation changes
 | volume = 14
 | year = 1980}}</ref>

<ref name=krishnamurthy>{{citation
 | last = Krishnamurthy | first = Balakrishnan
 | doi = 10.1007/BF00265682
 | issue = 3
 | journal = [[Acta Informatica]]
 | mr = 806206
 | pages = 253–275
 | title = Short proofs for tricky formulas
 | volume = 22
 | year = 1985| s2cid = 2459540
 }}</ref>

<ref name=mackenzie>{{citation
 | last = MacKenzie | first = Donald
 | doi = 10.1098/rsta.2005.1649
 | issue = 1835
 | journal = [[Philosophical Transactions of the Royal Society]]
 | jstor = 30039731
 | mr = 2197653
 | pages = 2335–2350
 | title = Computing and the cultures of proving
 | volume = 363
 | year = 2005| pmid = 16188609
 | bibcode = 2005RSPTA.363.2335M
 | s2cid = 18225791
 }}</ref>

<ref name=mccarthy64>{{citation
 | last = McCarthy
 | first = John
 | author-link = John McCarthy (computer scientist)
 | date = July 17, 1964
 | series = Stanford AI Memo
 | title = A tough nut for proof procedures
 | url = https://jmc.stanford.edu/articles/toughnut.html
 | volume = 16
 | access-date = July 18, 2022
 | archive-date = May 16, 2021
 | archive-url = https://web.archive.org/web/20210516113211/http://jmc.stanford.edu/articles/toughnut.html
 | url-status = live
 }}</ref>

<ref name=mccarthy99>{{citation
 | last = McCarthy
 | first = John
 | author-link = John McCarthy (computer scientist)
 | accessdate = 2007-04-27
 | contribution = Creative Solutions to Problems
 | contribution-url = http://jmc.stanford.edu/articles/creative.html
 | title = AISB Workshop on Artificial Intelligence and Creativity
 | year = 1999
 | archive-date = 2018-10-23
 | archive-url = https://web.archive.org/web/20181023181750/http://jmc.stanford.edu/articles/creative.html
 | url-status = live
 }}</ref>

<ref name=mendelsohn>{{citation
 | last = Mendelsohn | first = N. S.
 | doi = 10.2307/4146865
 | issue = 2
 | journal = [[The College Mathematics Journal]]
 | jstor = 4146865
 | pages = 115–120
 | title = Tiling with dominoes
 | volume = 35
 | year = 2004}}. Mendelsohn credits the original publication of Gomory's theorem to {{harvtxt|Honsberger|1973}}.</ref>

<ref name=mizar>{{citation
 | last = Rudnicki
 | first = Piotr
 | doi = 10.7939/R3QV3C738
 | publisher = University of Alberta Department of Computer Science
 | series = Technical Report
 | title = The Mutilated Checkerboard Problem in the Lightweight Set Theory of Mizar
 | url = https://era.library.ualberta.ca/items/ae7346a0-6a95-433b-bb8c-5a35900329d1
 | volume = TR96-09
 | year = 1996
 | access-date = 2022-07-18
 | archive-date = 2022-07-18
 | archive-url = https://web.archive.org/web/20220718200746/https://era.library.ualberta.ca/items/ae7346a0-6a95-433b-bb8c-5a35900329d1
 | url-status = live
 }}</ref>

<ref name=propp>{{citation
 | last = Propp | first = Jim | author-link = Jim Propp
 | doi = 10.1007/s00283-021-10089-3
 | issue = 2
 | journal = [[The Mathematical Intelligencer]]
 | mr = 4278473
 | pages = 40–46
 | title = Conway's influence on the study of random tilings
 | volume = 43
 | year = 2021| s2cid = 236397105 }}</ref>

<ref name=razborov>{{citation
 | last = Razborov
 | first = Alexander A.
 | author-link = Alexander Razborov
 | doi = 10.1016/j.jcss.2004.01.004
 | issue = 1
 | journal = [[Journal of Computer and System Sciences]]
 | mr = 2070797
 | pages = 3–27
 | title = Resolution lower bounds for perfect matching principles
 | url = http://people.cs.uchicago.edu/~razborov/files/matching.pdf
 | volume = 69
 | year = 2004
 | access-date = 2022-07-19
 | archive-date = 2022-08-08
 | archive-url = https://web.archive.org/web/20220808151212/http://people.cs.uchicago.edu/~razborov/files/matching.pdf
 | url-status = live
 }}</ref>

<ref name=robinson>{{citation
 | last = Robinson | first = J. A.
 | editor-last = Boyer | editor-first = Robert S.
 | contribution = Formal and Informal Proofs
 | doi = 10.1007/978-94-011-3488-0_13
 | pages = 267–282
 | publisher = Springer Netherlands
 | series = Automated Reasoning Series
 | title = Automated Reasoning: Essays in Honor of Woody Bledsoe
 | volume = 1
 | year = 1991| isbn = 978-94-010-5542-0
 }}; see especially Section 13.1, "The mutilated chess board problem", [https://books.google.com/books?id=guSoCAAAQBAJ&pg=PA271 pp. 271–274] {{Webarchive|url=https://web.archive.org/web/20220718074354/https://books.google.com/books?id=guSoCAAAQBAJ&pg=PA271 |date=2022-07-18 }}.</ref>

<ref name=semidefinite>{{citation
 | last1 = de Klerk
 | first1 = Etienne
 | last2 = Van Maaren
 | first2 = Hans
 | last3 = Warners
 | first3 = Joost P.
 | doi = 10.1023/A:1006362203438
 | issue = 1–2
 | journal = [[Journal of Automated Reasoning]]
 | mr = 1750258
 | pages = 37–65
 | title = Relaxations of the satisfiability problem using semidefinite programming
 | url = https://research.tilburguniversity.edu/en/publications/relaxations-of-the-satisfiability-problem-using-semidefinite-prog
 | volume = 24
 | year = 2000
 | s2cid = 5727281
 | access-date = 2022-07-19
 | archive-date = 2021-06-20
 | archive-url = https://web.archive.org/web/20210620184800/https://research.tilburguniversity.edu/en/publications/relaxations-of-the-satisfiability-problem-using-semidefinite-prog
 | url-status = live
 }}</ref>

<ref name=starikova-vanbendegem>{{citation
 | last1 = Starikova
 | first1 = Irina
 | last2 = Van Bendegem
 | first2 = Jean Paul
 | doi = 10.2143/LEA.255.0.3290192
 | issue = 255
 | journal = Logique et Analyse
 | mr = 4396339
 | pages = 289–312
 | title = Revisiting the mutilated chessboard or the many roles of a picture
 | url = https://www.researchgate.net/publication/341220441
 | volume = 64
 | year = 2021
 | access-date = 2022-07-19
 | archive-date = 2022-07-19
 | archive-url = https://web.archive.org/web/20220719004449/https://www.researchgate.net/publication/341220441_Revisiting_the_mutilated_chessboard_or_the_many_roles_of_a_picture
 | url-status = live
 }}</ref>

<ref name=subramanian>{{citation
 | last = Subramanian | first = Sakthi
 | doi = 10.1093/logcom/6.4.573
 | issue = 4
 | journal = [[Journal of Logic and Computation]]
 | mr = 1406233
 | pages = 573–598
 | title = An interactive solution to the <math>n\times n</math> mutilated checkerboard problem
 | volume = 6
 | year = 1996}}</ref>

<ref name=tanswell>{{citation
 | last = Tanswell | first = Fenner
 | doi = 10.1093/philmat/nkv008
 | issue = 3
 | journal = [[Philosophia Mathematica]]
 | mr = 3404036
 | pages = 295–310
 | series = Series III
 | title = A problem with the dependence of informal proofs on formal proofs
 | volume = 23
 | year = 2015}}</ref>

<ref name=tatami>{{citation
 | last1 = Erickson | first1 = Alejandro
 | last2 = Ruskey | first2 = Frank | author2-link = Frank Ruskey
 | last3 = Schurch | first3 = Mark
 | last4 = Woodcock | first4 = Jennifer
 | editor1-last = Thai | editor1-first = My T. | editor1-link = My T. Thai
 | editor2-last = Sahni | editor2-first = Sartaj | editor2-link = Sartaj Sahni
 | arxiv = 1103.3309
 | contribution = Auspicious tatami mat arrangements
 | doi = 10.1007/978-3-642-14031-0_32
 | mr = 2720105
 | pages = 288–297
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = Computing and Combinatorics, 16th Annual International Conference, COCOON 2010, Nha Trang, Vietnam, July 19–21, 2010, Proceedings
 | volume = 6196
 | year = 2010| isbn = 978-3-642-14030-3
 | s2cid = 6603662
 }}</ref>

<ref name=thurston>{{citation
 | last = Thurston | first = William P. | author-link = William Thurston
 | doi = 10.2307/2324578
 | issue = 8
 | journal = [[The American Mathematical Monthly]]
 | jstor = 2324578
 | mr = 1072815
 | pages = 757–773
 | title = Conway's tiling groups
 | volume = 97
 | year = 1990}}</ref>

<ref name=urquhart>{{citation
 | last = Urquhart | first = Alasdair
 | doi = 10.1023/A:1021231610627
 | issue = 3
 | journal = Annals of Mathematics and Artificial Intelligence
 | mr = 1969128
 | pages = 241–250
 | title = Resolution proofs of matching principles
 | volume = 37
 | year = 2003| s2cid = 6753523
 }}</ref>

<ref name=watkins>{{citation
 | last = Watkins | first = John J.
 | isbn = 978-0-691-11503-0
 | pages = [https://archive.org/details/acrossboardma00watk/page/12 12–14]
 | publisher = Princeton University Press
 | title = Across the Board: The Mathematics of Chessboard Problems
 | year = 2004}}</ref>

<ref name=wazir>{{citation
 | last1 = Bivens | first1 = Irl C.
 | last2 = Holshouser | first2 = Arthur L.
 | last3 = Klein | first3 = Benjamin G.
 | date = October 2008
 | doi = 10.1080/0025570X.2008.11953562
 | issue = 4
 | journal = [[Mathematics Magazine]]
 | jstor = 27643123
 | pages = 276–284
 | title = Wazir circuits on an obstructed chessboard
 | volume = 81| s2cid = 125950546
 }}</ref>

<ref name=wright>{{citation
 | last = Wright
 | first = Colin
 | issue = 1
 | journal = Recreational Mathematics Magazine
 | mr = 3323392
 | pages = 4–9
 | title = The mutilated chess board (revisited)
 | url = https://www.solipsys.co.uk/Writings/TheMutilatedChessBoardRevisited.pdf
 | year = 2014
 | access-date = 2022-07-18
 | archive-date = 2022-08-08
 | archive-url = https://web.archive.org/web/20220808180737/https://www.solipsys.co.uk/Writings/TheMutilatedChessBoardRevisited.pdf
 | url-status = live
 }}</ref>

}}

== External links ==
{{Commons category|Mutilated chessboard problem}}
*[http://demonstrations.wolfram.com/GomorysTheorem/ Gomory's Theorem] by Jay Warendorff, [[The Wolfram Demonstrations Project]].

[[Category:Tiling puzzles]]
[[Category:Logic puzzles]]
[[Category:Mathematical chess problems]]
[[Category:Unsolvable puzzles]]