203:
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. 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.
30:
22:
219:
207:
355:
362:
349:
271:
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
190:
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
77:
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
385:
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
242:
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. Gomory's theorem is specific to the removal of only one square of each
202:
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
303:
and asking for a system that can automatically determine the unsolvability of this formulation. Most considerations of this problem provide solutions "in the conceptual sense" that do not apply to McCarthy's logic formulation of the problem. Despite the existence of general methods such as those
316:
systems that can manage the equivalences between different representations. Short proofs are possible using resolution with additional variables, or in stronger proof systems allowing the expression of avoidable tiling patterns that can prune the search space. Higher-level
390:, which asks for a tour in which the positions of certain squares match given clues. 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.
907:
Bilalić, Merim; Graf, Mario; Vaci, Nemanja; Danek, Amory H. (August 2019), "When the solution is on the doorstep: Better solving performance, but diminished aha! experience for chess experts on the mutilated checkerboard problem",
191:
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. The same idea shows that no
1530:
1111:
243:
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.
1589:
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
214:
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.
1987:
386:
square of any complete tour is black. However, the opposite corner square is white. This sort of tour of a chessboard also forms the basis of a type of puzzle called
210:
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
1556:
Theorem
Proving with Analytic Tableaux and Related Methods, 5th International Workshop, TABLEAUX '96, Terrasini, Palermo, Italy, May 15–17, 1996, Proceedings
1492:
1943:
1459:, Department of Computer Science Report Series B, vol. B-2021-1, Helsinki: Department of Computer Science, University of Helsinki, pp. 52–53,
1332:
156:
381:
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
948:
2103:
1606:
581:
1723:
1468:
78:
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
133:(1946), with a hint at the coloring-based solution to its impossibility. It was popularized in the 1950s through later discussions by
1905:
811:
Mathematical
Knowledge Management, 4th International Conference, MKM 2005, Bremen, Germany, July 15-17, 2005, Revised Selected Papers
1698:
474:
Computing and
Combinatorics, 16th Annual International Conference, COCOON 2010, Nha Trang, Vietnam, July 19–21, 2010, Proceedings
1650:
1016:
From
Animals to Robots and Back: Reflections on Hard Problems in the Study of Cognition, A Collection in Honour of Aaron Sloman
1850:
1571:
1294:
1031:
826:
657:
571:
499:
1164:
782:
2183:
33:
Unsuccessful solution to the mutilated chessboard problem: as well as the two corners, two center squares remain uncovered.
1014:
Kerber, Manfred (2014), "A proof and some representations", in Wyatt, Jeremy L.; Petters, Dean D.; Hogg, David C. (eds.),
226:
If two squares of opposite colors are removed, then the remaining board can always be tiled with dominoes; this result is
434:
2025:
Bivens, Irl C.; Holshouser, Arthur L.; Klein, Benjamin G. (October 2008), "Wazir circuits on an obstructed chessboard",
728:(March 1957), "Some old and new versions of ticktacktoe, plus the answers to last month's puzzles", Mathematical Games,
2157:
1152:
772:
292:
167:
195:
can exist whenever any two squares of the same color (not just the opposite corners) are removed from the chessboard.
2108:
1748:
1360:
603:
1991:
222:
A region of the chessboard that has no domino tiling, but for which coloring-based impossibility proofs do not work
1577:
1189:
277:
1608:
42nd Annual
Symposium on Foundations of Computer Science, FOCS 2001, 14–17 October 2001, Las Vegas, Nevada, USA
1497:
1236:
847:
1929:
118:
in 1937. Domino tilings also have a long history of practical use in pavement design and the arrangement of
1835:
NASA Formal
Methods – 11th International Symposium, NFM 2019, Houston, TX, USA, May 7–9, 2019, Proceedings
1628:
1313:
881:
Akin, Ömer; Akin, Cem (January 1998), "On the process of creativity in puzzles, inventions, and designs",
2188:
910:
1829:; Kiesl, Benjamin; Biere, Armin (2019), "Clausal proofs of mutilated chessboards", in Badger, Julia M.;
1455:, in Balyo, Tomáš; Froleyks, Nils; Heule, Marijn; Iser, Markus; Järvisalo, Matti; Suda, Martin (eds.),
322:
285:
273:
2099:
429:
175:
115:
87:
408:
cuboids. The proof uses a similar chessboard-coloring argument to the mutilated chessboard problem.
313:
281:
1648:
Alekhnovich, Michael (2004), "Mutilated chessboard problem is exponentially hard for resolution",
2173:
1048:
1018:, Cognitive Systems Monographs, vol. 22, Springer International Publishing, pp. 65–73,
309:
2178:
1966:
393:
1046:
Tanswell, Fenner (2015), "A problem with the dependence of informal proofs on formal proofs",
578:
61:) has two diagonally opposite corners removed, leaving 62 squares. Is it possible to place 31
2071:
1934:, Technical Report, vol. TR96-09, University of Alberta Department of Computer Science,
1830:
1690:
1449:
308:
to solve McCarthy's logical formulation of the problem, highlighting the need for methods in
107:
2137:
2027:
2012:
1901:
1805:
1769:
1719:
1673:
1518:
1423:
1389:
1328:
1257:
1107:
1069:
985:
957:
632:
509:
400:
into a larger cuboid. For instance, it is impossible, according to this theorem, to fill a
1874:
1286:
8:
2069:
Hanson, Mary Grace; Nash, David A. (Spring 2018), "Minimal and maximal
Numbrix puzzles",
730:
698:
174:
as a test case for creative insight, Black's original motivation for the problem. In the
163:
151:
79:
961:
2125:
2080:
2052:
2044:
1856:
1809:
1686:
1620:
1522:
1427:
1377:
1261:
1206:
997:
973:
864:
747:
743:
715:
711:
620:
513:
477:
321:
are capable of handling the coloring-based impossibility proof directly; these include
305:
272:
vertices of one color than the other implies that it fails the necessary conditions of
264:
179:
29:
1664:
894:
2056:
1846:
1761:
1567:
1290:
1265:
1083:
1027:
989:
929:
860:
822:
653:
598:
567:
495:
464:; Schurch, Mark; Woodcock, Jennifer (2010), "Auspicious tatami mat arrangements", in
382:
300:
235:
211:
171:
134:
70:
2153:
1860:
1624:
1001:
868:
806:
2117:
2040:
2036:
2000:
1935:
1889:
1838:
1813:
1793:
1784:
1757:
1707:
1659:
1612:
1559:
1526:
1506:
1460:
1431:
1411:
1369:
1355:
1245:
1198:
1095:
1057:
1019:
965:
919:
890:
856:
842:
814:
739:
707:
616:
612:
559:
558:, Automated Reasoning Series, vol. 1, Springer Netherlands, pp. 267–282,
517:
487:
443:
1837:, Lecture Notes in Computer Science, vol. 11460, Springer, pp. 204–210,
1554:, in Miglioli, Pierangelo; Moscato, Ugo; Mundici, Daniele; Ornaghi, Mario (eds.),
776:
21:
2133:
2008:
1897:
1842:
1801:
1765:
1715:
1669:
1514:
1419:
1385:
1324:
1253:
1156:
1134:
1103:
1065:
981:
628:
585:
563:
554:
Robinson, J. A. (1991), "Formal and
Informal Proofs", in Boyer, Robert S. (ed.),
505:
491:
476:, Lecture Notes in Computer Science, vol. 6196, Springer, pp. 288–297,
425:
318:
296:
268:
256:
231:
199:
111:
1023:
312:
that can automatically change to a more suitable problem representation and for
1711:
1249:
813:, Lecture Notes in Computer Science, vol. 3863, Springer, pp. 81–95,
725:
693:
276:, so no matching exists. The problem can also be solved by formulating it as a
146:
1558:, Lecture Notes in Computer Science, vol. 1071, Springer, pp. 1–15,
1510:
1415:
1099:
2167:
2004:
1893:
1616:
1061:
378:
192:
99:
74:
42:
1563:
432:(1937), "An attempt to extend the statistical theory of perfect solutions",
234:, whose proof was published in 1973. Gomory's theorem can be proven using a
1826:
1445:
993:
969:
933:
696:(February 1957), "An assortment of maddening puzzles", Mathematical Games,
672:
645:
469:
461:
326:
260:
142:
138:
106:, also known as "dimer models", a general class of problems whose study in
58:
1493:"Relaxations of the satisfiability problem using semidefinite programming"
218:
1931:
The
Mutilated Checkerboard Problem in the Lightweight Set Theory of Mizar
447:
2048:
1782:
Krishnamurthy, Balakrishnan (1985), "Short proofs for tricky formulas",
1464:
977:
751:
719:
2129:
1797:
1402:
Urquhart, Alasdair (2003), "Resolution proofs of matching principles",
1381:
1210:
924:
818:
624:
465:
239:
198:
Several other proofs of impossibility have also been found. A proof by
83:
54:
1939:
1551:
1457:
Proceedings of SAT Competition 2021: Solver and
Benchmark Descriptions
1746:
Korf, Richard E. (1980), "Toward a model of representation changes",
1231:
1214:. Mendelsohn credits the original publication of Gomory's theorem to
533:
252:
206:
126:
103:
46:
2121:
1373:
1202:
1084:"Revisiting the mutilated chessboard or the many roles of a picture"
577:; see especially Section 13.1, "The mutilated chess board problem",
125:
The mutilated chessboard problem itself was proposed by philosopher
2085:
946:
MacKenzie, Donald (2005), "Computing and the cultures of proving",
62:
482:
538:
Critical Thinking: An Introduction To Logic And Scientific Method
387:
1875:"A simple formalization and proof for the mutilated chess board"
1602:
1491:
de Klerk, Etienne; Van Maaren, Hans; Warners, Joost P. (2000),
397:
119:
1234:(2021), "Conway's influence on the study of random tilings",
459:
330:
255:, such as the mutilated chessboard problem, can be solved in
1963:
Subramanian, Sakthi (1996), "An interactive solution to the
1691:"Resolution lower bounds for perfect matching principles"
1490:
1283:
Across the Board: The Mathematics of Chessboard Problems
295:
proposed the mutilated chessboard as a hard problem for
1161:
AISB Workshop on Artificial Intelligence and Creativity
1443:
304:
based on graph matching, it is exponentially hard for
2024:
1969:
1141:, Mathematical Association of America, pp. 65–67
1081:
1075:
556:
Automated Reasoning: Essays in Honor of Woody Bledsoe
246:
906:
807:"A tough nut for mathematical knowledge management"
178:, it has been examined in studies of the nature of
98:The mutilated chessboard problem is an instance of
1981:
1187:Mendelsohn, N. S. (2004), "Tiling with dominoes",
1082:Starikova, Irina; Van Bendegem, Jean Paul (2021),
1552:"On sets, types, fixed points, and checkerboards"
1404:Annals of Mathematics and Artificial Intelligence
354:
2165:
800:
798:
424:
418:
342:
65:of size 2×1 so as to cover all of these squares?
1825:
949:Philosophical Transactions of the Royal Society
162:The use of the mutilated chessboard problem in
1543:
396:concerns the impossibility of packing certain
1781:
1775:
1594:
1549:
1182:
1180:
1129:
1127:
795:
259:, either by converting them into problems in
1600:
1484:
834:
804:
767:
765:
2062:
1962:
1956:
1647:
1641:
1611:, IEEE Computer Society, pp. 220–229,
1550:Andrews, Peter B.; Bishop, Matthew (1996),
840:
759:(Dover Publications, 1994), pages 2 and 39.
267:. In the latter formulation, one obtains a
16:On domino tiling after removing two corners
2068:
1603:"'Planar' tautologies hard for resolution"
1276:
1274:
1215:
1186:
1177:
1145:
1133:
1124:
644:
638:
601:(1954), "Checker boards and polyominoes",
549:
547:
2098:
2084:
1663:
1601:Dantchev, Stefan S.; Riis, Søren (2001),
1307:
1305:
945:
939:
923:
874:
762:
688:
686:
481:
2092:
1927:
1866:
1685:
1679:
1401:
1395:
1354:
1348:
1226:
1224:
1151:
1045:
1039:
880:
805:Kerber, Manfred; Pollet, Martin (2005),
771:
553:
217:
205:
28:
20:
1872:
1819:
1699:Journal of Computer and System Sciences
1450:"Bipartite perfect matching benchmarks"
1314:"The mutilated chess board (revisited)"
1285:, Princeton University Press, pp.
1280:
1271:
724:
692:
677:Théorie des graphes et ses applications
648:; Stern, Marvin (1958), "Domino game",
544:
528:
526:
361:
2166:
1311:
1302:
1013:
1007:
757:My Best Mathematical and Logic Puzzles
683:
597:
2018:
1921:
1444:Codel, Cayden R.; Reeves, Joseph E.;
1230:
1221:
845:(July 1990), "In search of insight",
671:
591:
532:
453:
345:
170:in 1964. It has also been studied in
166:stems from a proposal for its use by
1745:
1739:
1437:
900:
665:
523:
435:Transactions of the Faraday Society
336:
13:
2158:The Wolfram Demonstrations Project
1358:(1990), "Conway's tiling groups",
781:, Stanford AI Memo, vol. 16,
744:10.1038/scientificamerican0357-160
712:10.1038/scientificamerican0257-152
540:, Prentice Hall, pp. 157, 433
247:Application to automated reasoning
14:
2200:
2147:
2109:The American Mathematical Monthly
1989:mutilated checkerboard problem",
1361:The American Mathematical Monthly
1321:Recreational Mathematics Magazine
604:The American Mathematical Monthly
1992:Journal of Logic and Computation
1157:"Creative Solutions to Problems"
778:A tough nut for proof procedures
652:, Viking Press, pp. 87–90,
360:
353:
347:
1946:from the original on 2022-07-18
1911:from the original on 2022-08-08
1729:from the original on 2022-08-08
1631:from the original on 2022-09-14
1580:from the original on 2022-07-18
1533:from the original on 2021-06-20
1474:from the original on 2022-07-18
1338:from the original on 2022-08-08
1190:The College Mathematics Journal
1167:from the original on 2018-10-23
1114:from the original on 2022-07-19
785:from the original on 2021-05-16
679:(in French), Dunod, p. 176
278:constraint satisfaction problem
2041:10.1080/0025570X.2008.11953562
1498:Journal of Automated Reasoning
1237:The Mathematical Intelligencer
809:, in Kohlhase, Michael (ed.),
617:10.1080/00029890.1954.11988548
1:
1873:Paulson, Lawrence C. (2001),
1665:10.1016/S0304-3975(03)00395-5
895:10.1016/s0926-5805(97)00057-5
411:
1843:10.1007/978-3-030-20652-9_13
1762:10.1016/0004-3702(80)90033-8
1651:Theoretical Computer Science
1448:; Bryant, Randal E. (2021),
1137:(1973), "Gomory's theorem",
861:10.1016/0010-0285(90)90008-r
564:10.1007/978-94-011-3488-0_13
492:10.1007/978-3-642-14031-0_32
377:A similar problem asks if a
39:mutilated chessboard problem
7:
2184:Mathematical chess problems
2104:"Filling boxes with bricks"
1024:10.1007/978-3-319-06614-1_5
299:systems, formulating it in
185:
10:
2205:
1712:10.1016/j.jcss.2004.01.004
1250:10.1007/s00283-021-10089-3
883:Automation in Construction
251:Domino tiling problems on
93:
1982:{\displaystyle n\times n}
1882:Logic Journal of the IGPL
1281:Watkins, John J. (2004),
1100:10.2143/LEA.255.0.3290192
176:philosophy of mathematics
141:and Marvin Stern (1958),
116:George Stanley Rushbrooke
88:philosophy of mathematics
1928:Rudnicki, Piotr (1996),
1617:10.1109/SFCS.2001.959896
314:knowledge representation
282:semidefinite programming
25:The mutilated chessboard
1749:Artificial Intelligence
1564:10.1007/3-540-61208-4_1
1511:10.1023/A:1006362203438
1416:10.1023/A:1021231610627
1049:Philosophia Mathematica
310:artificial intelligence
274:Hall's marriage theorem
53:Suppose a standard 8×8
2005:10.1093/logcom/6.4.573
1983:
1894:10.1093/jigpal/9.3.475
1831:Rozier, Kristin Yvonne
1687:Razborov, Alexander A.
1312:Wright, Colin (2014),
1062:10.1093/philmat/nkv008
970:10.1098/rsta.2005.1649
230:, after mathematician
223:
215:
67:
34:
26:
2072:Pi Mu Epsilon Journal
1984:
460:Erickson, Alejandro;
372:Wazir's tour problem
263:, or as instances of
221:
209:
110:dates to the work of
108:statistical mechanics
51:
32:
24:
2028:Mathematics Magazine
1967:
1356:Thurston, William P.
848:Cognitive Psychology
723:; for solution, see
448:10.1039/tf9373301272
2156:by Jay Warendorff,
1827:Heule, Marijn J. H.
1446:Heule, Marijn J. H.
1139:Mathematical Gems I
962:2005RSPTA.363.2335M
956:(1835): 2335–2350,
731:Scientific American
699:Scientific American
394:De Bruijn's theorem
164:automated reasoning
152:Scientific American
80:automated reasoning
49:in 1946 that asks:
2189:Unsolvable puzzles
1979:
1798:10.1007/BF00265682
1088:Logique et Analyse
925:10.1111/cogs.12771
841:Kaplan, Craig A.;
819:10.1007/11618027_6
584:2022-07-18 at the
265:bipartite matching
224:
216:
180:mathematical proof
157:Mathematical Games
35:
27:
1940:10.7939/R3QV3C738
1852:978-3-030-20651-2
1573:978-3-540-61208-7
1296:978-0-691-11503-0
1216:Honsberger (1973)
1033:978-3-319-06613-4
911:Cognitive Science
843:Simon, Herbert A.
828:978-3-540-31430-1
775:(July 17, 1964),
659:978-0-333-08637-7
573:978-94-010-5542-0
501:978-3-642-14030-3
430:Rushbrooke, G. S.
383:fairy chess piece
370:
369:
301:first-order logic
236:Hamiltonian cycle
212:Hamiltonian cycle
172:cognitive science
135:Solomon W. Golomb
131:Critical Thinking
71:impossible puzzle
2196:
2154:Gomory's Theorem
2141:
2140:
2100:de Bruijn, N. G.
2096:
2090:
2089:
2088:
2066:
2060:
2059:
2022:
2016:
2015:
1988:
1986:
1985:
1980:
1960:
1954:
1953:
1952:
1951:
1925:
1919:
1918:
1917:
1916:
1910:
1879:
1870:
1864:
1863:
1823:
1817:
1816:
1785:Acta Informatica
1779:
1773:
1772:
1743:
1737:
1736:
1735:
1734:
1728:
1695:
1683:
1677:
1676:
1667:
1658:(1–3): 513–525,
1645:
1639:
1638:
1637:
1636:
1598:
1592:
1591:
1586:
1585:
1547:
1541:
1540:
1539:
1538:
1488:
1482:
1481:
1480:
1479:
1473:
1454:
1441:
1435:
1434:
1399:
1393:
1392:
1352:
1346:
1345:
1344:
1343:
1337:
1318:
1309:
1300:
1299:
1278:
1269:
1268:
1228:
1219:
1213:
1184:
1175:
1174:
1173:
1172:
1149:
1143:
1142:
1131:
1122:
1121:
1120:
1119:
1094:(255): 289–312,
1079:
1073:
1072:
1043:
1037:
1036:
1011:
1005:
1004:
943:
937:
936:
927:
904:
898:
897:
889:(2–3): 123–138,
878:
872:
871:
838:
832:
831:
802:
793:
792:
791:
790:
769:
760:
754:
722:
690:
681:
680:
669:
663:
662:
642:
636:
635:
595:
589:
576:
551:
542:
541:
530:
521:
520:
485:
457:
451:
450:
422:
407:
403:
364:
363:
357:
356:
351:
350:
343:
337:Related problems
319:proof assistants
228:Gomory's theorem
2204:
2203:
2199:
2198:
2197:
2195:
2194:
2193:
2164:
2163:
2150:
2145:
2144:
2122:10.2307/2316785
2097:
2093:
2067:
2063:
2023:
2019:
1968:
1965:
1964:
1961:
1957:
1949:
1947:
1926:
1922:
1914:
1912:
1908:
1877:
1871:
1867:
1853:
1824:
1820:
1780:
1776:
1744:
1740:
1732:
1730:
1726:
1693:
1684:
1680:
1646:
1642:
1634:
1632:
1599:
1595:
1583:
1581:
1574:
1548:
1544:
1536:
1534:
1489:
1485:
1477:
1475:
1471:
1452:
1442:
1438:
1400:
1396:
1374:10.2307/2324578
1353:
1349:
1341:
1339:
1335:
1316:
1310:
1303:
1297:
1279:
1272:
1229:
1222:
1203:10.2307/4146865
1185:
1178:
1170:
1168:
1150:
1146:
1132:
1125:
1117:
1115:
1080:
1076:
1044:
1040:
1034:
1012:
1008:
944:
940:
905:
901:
879:
875:
839:
835:
829:
803:
796:
788:
786:
770:
763:
755:. Reprinted in
726:Gardner, Martin
694:Gardner, Martin
691:
684:
670:
666:
660:
643:
639:
611:(10): 675–682,
596:
592:
586:Wayback Machine
574:
552:
545:
531:
524:
502:
458:
454:
423:
419:
414:
405:
401:
375:
374:
373:
366:
365:
358:
348:
339:
297:automated proof
280:, and applying
269:bipartite graph
257:polynomial time
249:
232:Ralph E. Gomory
200:Shmuel Winograd
188:
112:Ralph H. Fowler
96:
17:
12:
11:
5:
2202:
2192:
2191:
2186:
2181:
2176:
2174:Tiling puzzles
2162:
2161:
2149:
2148:External links
2146:
2143:
2142:
2091:
2079:(8): 505–514,
2061:
2035:(4): 276–284,
2017:
1999:(4): 573–598,
1978:
1975:
1972:
1955:
1920:
1888:(3): 475–485,
1865:
1851:
1818:
1792:(3): 253–275,
1774:
1738:
1678:
1640:
1593:
1572:
1542:
1505:(1–2): 37–65,
1483:
1436:
1410:(3): 241–250,
1394:
1368:(8): 757–773,
1347:
1301:
1295:
1270:
1220:
1197:(2): 115–120,
1176:
1153:McCarthy, John
1144:
1135:Honsberger, R.
1123:
1074:
1056:(3): 295–310,
1052:, Series III,
1038:
1032:
1006:
938:
899:
873:
855:(3): 374–419,
833:
827:
794:
773:McCarthy, John
761:
738:(3): 160–168,
706:(2): 152–158,
682:
664:
658:
637:
590:
572:
543:
522:
500:
452:
416:
415:
413:
410:
371:
368:
367:
359:
352:
346:
341:
340:
338:
335:
248:
245:
187:
184:
147:Martin Gardner
95:
92:
73:: there is no
15:
9:
6:
4:
3:
2:
2201:
2190:
2187:
2185:
2182:
2180:
2179:Logic puzzles
2177:
2175:
2172:
2171:
2169:
2159:
2155:
2152:
2151:
2139:
2135:
2131:
2127:
2123:
2119:
2115:
2111:
2110:
2105:
2101:
2095:
2087:
2082:
2078:
2074:
2073:
2065:
2058:
2054:
2050:
2046:
2042:
2038:
2034:
2030:
2029:
2021:
2014:
2010:
2006:
2002:
1998:
1994:
1993:
1976:
1973:
1970:
1959:
1945:
1941:
1937:
1933:
1932:
1924:
1907:
1903:
1899:
1895:
1891:
1887:
1883:
1876:
1869:
1862:
1858:
1854:
1848:
1844:
1840:
1836:
1832:
1828:
1822:
1815:
1811:
1807:
1803:
1799:
1795:
1791:
1787:
1786:
1778:
1771:
1767:
1763:
1759:
1755:
1751:
1750:
1742:
1725:
1721:
1717:
1713:
1709:
1705:
1701:
1700:
1692:
1688:
1682:
1675:
1671:
1666:
1661:
1657:
1653:
1652:
1644:
1630:
1626:
1622:
1618:
1614:
1610:
1609:
1604:
1597:
1590:
1579:
1575:
1569:
1565:
1561:
1557:
1553:
1546:
1532:
1528:
1524:
1520:
1516:
1512:
1508:
1504:
1500:
1499:
1494:
1487:
1470:
1466:
1462:
1458:
1451:
1447:
1440:
1433:
1429:
1425:
1421:
1417:
1413:
1409:
1405:
1398:
1391:
1387:
1383:
1379:
1375:
1371:
1367:
1363:
1362:
1357:
1351:
1334:
1330:
1326:
1322:
1315:
1308:
1306:
1298:
1292:
1288:
1284:
1277:
1275:
1267:
1263:
1259:
1255:
1251:
1247:
1243:
1239:
1238:
1233:
1227:
1225:
1217:
1212:
1208:
1204:
1200:
1196:
1192:
1191:
1183:
1181:
1166:
1162:
1158:
1154:
1148:
1140:
1136:
1130:
1128:
1113:
1109:
1105:
1101:
1097:
1093:
1089:
1085:
1078:
1071:
1067:
1063:
1059:
1055:
1051:
1050:
1042:
1035:
1029:
1025:
1021:
1017:
1010:
1003:
999:
995:
991:
987:
983:
979:
975:
971:
967:
963:
959:
955:
951:
950:
942:
935:
931:
926:
921:
918:(8): e12771,
917:
913:
912:
903:
896:
892:
888:
884:
877:
870:
866:
862:
858:
854:
850:
849:
844:
837:
830:
824:
820:
816:
812:
808:
801:
799:
784:
780:
779:
774:
768:
766:
758:
753:
749:
745:
741:
737:
733:
732:
727:
721:
717:
713:
709:
705:
701:
700:
695:
689:
687:
678:
674:
673:Berge, Claude
668:
661:
655:
651:
647:
646:Gamow, George
641:
634:
630:
626:
622:
618:
614:
610:
606:
605:
600:
599:Golomb, S. W.
594:
587:
583:
580:
575:
569:
565:
561:
557:
550:
548:
539:
535:
529:
527:
519:
515:
511:
507:
503:
497:
493:
489:
484:
479:
475:
471:
470:Sahni, Sartaj
467:
463:
462:Ruskey, Frank
456:
449:
445:
441:
437:
436:
431:
427:
426:Fowler, R. H.
421:
417:
409:
399:
395:
391:
389:
384:
380:
344:
334:
332:
328:
324:
320:
315:
311:
307:
302:
298:
294:
293:John McCarthy
289:
287:
283:
279:
275:
270:
266:
262:
258:
254:
244:
241:
237:
233:
229:
220:
213:
208:
204:
201:
196:
194:
193:domino tiling
183:
181:
177:
173:
169:
168:John McCarthy
165:
160:
158:
154:
153:
148:
144:
140:
136:
132:
128:
123:
121:
117:
113:
109:
105:
102:of grids and
101:
100:domino tiling
91:
89:
85:
81:
76:
75:domino tiling
72:
66:
64:
60:
56:
50:
48:
44:
43:tiling puzzle
40:
31:
23:
19:
2116:(1): 37–40,
2113:
2107:
2094:
2076:
2070:
2064:
2032:
2026:
2020:
1996:
1990:
1958:
1948:, retrieved
1930:
1923:
1913:, retrieved
1885:
1881:
1868:
1834:
1821:
1789:
1783:
1777:
1756:(1): 41–78,
1753:
1747:
1741:
1731:, retrieved
1703:
1697:
1681:
1655:
1649:
1643:
1633:, retrieved
1607:
1596:
1588:
1582:, retrieved
1555:
1545:
1535:, retrieved
1502:
1496:
1486:
1476:, retrieved
1465:10138/333647
1456:
1439:
1407:
1403:
1397:
1365:
1359:
1350:
1340:, retrieved
1320:
1282:
1244:(2): 40–46,
1241:
1235:
1194:
1188:
1169:, retrieved
1160:
1147:
1138:
1116:, retrieved
1091:
1087:
1077:
1053:
1047:
1041:
1015:
1009:
953:
947:
941:
915:
909:
902:
886:
882:
876:
852:
846:
836:
810:
787:, retrieved
777:
756:
735:
729:
703:
697:
676:
667:
649:
640:
608:
602:
593:
555:
537:
473:
455:
439:
433:
420:
392:
376:
327:Mizar system
290:
261:group theory
250:
227:
225:
197:
189:
161:
150:
145:(1958), and
143:Claude Berge
139:George Gamow
130:
129:in his book
124:
97:
68:
59:checkerboard
52:
38:
36:
18:
1706:(1): 3–27,
650:Puzzle-Math
579:pp. 271–274
466:Thai, My T.
253:polyominoes
104:polyominoes
2168:Categories
2086:1706.09389
1950:2022-07-18
1915:2022-07-18
1733:2022-07-19
1635:2022-07-18
1584:2022-07-18
1537:2022-07-19
1478:2022-07-18
1342:2022-07-18
1323:(1): 4–9,
1232:Propp, Jim
1171:2007-04-27
1118:2022-07-19
789:2022-07-18
534:Black, Max
412:References
306:resolution
286:relaxation
240:grid graph
159:" (1957).
122:flooring.
86:, and the
84:creativity
55:chessboard
2057:125950546
1974:×
1266:236397105
483:1103.3309
406:1 × 2 × 4
404:box with
402:6 × 6 × 6
291:In 1964,
127:Max Black
69:It is an
47:Max Black
45:posed by
2102:(1969),
2049:27643123
1944:archived
1906:archived
1861:92989148
1833:(eds.),
1724:archived
1689:(2004),
1629:archived
1625:18849777
1578:archived
1531:archived
1469:archived
1333:archived
1165:archived
1155:(1999),
1112:archived
1002:18225791
994:16188609
978:30039731
934:31446653
869:54334455
783:archived
752:24940785
720:24941903
675:(1958),
582:Archived
536:(1946),
472:(eds.),
442:: 1272,
323:Isabelle
186:Solution
155:column "
137:(1954),
63:dominoes
2138:0234841
2130:2316785
2013:1406233
1902:1828741
1814:2459540
1806:0806206
1770:0587851
1720:2070797
1674:2020358
1527:5727281
1519:1750258
1432:6753523
1424:1969128
1390:1072815
1382:2324578
1329:3323392
1258:4278473
1211:4146865
1108:4396339
1070:3404036
986:2197653
958:Bibcode
633:0067055
625:2307321
518:6603662
510:2720105
398:cuboids
388:Numbrix
238:of the
149:in his
94:History
2136:
2128:
2055:
2047:
2011:
1900:
1859:
1849:
1812:
1804:
1768:
1718:
1672:
1623:
1570:
1525:
1517:
1430:
1422:
1388:
1380:
1327:
1293:
1264:
1256:
1209:
1106:
1068:
1030:
1000:
992:
984:
976:
932:
867:
825:
750:
718:
656:
631:
623:
570:
516:
508:
498:
329:, and
325:, the
120:tatami
2126:JSTOR
2081:arXiv
2053:S2CID
2045:JSTOR
1909:(PDF)
1878:(PDF)
1857:S2CID
1810:S2CID
1727:(PDF)
1694:(PDF)
1621:S2CID
1523:S2CID
1472:(PDF)
1453:(PDF)
1428:S2CID
1378:JSTOR
1336:(PDF)
1317:(PDF)
1287:12–14
1262:S2CID
1207:JSTOR
998:S2CID
974:JSTOR
865:S2CID
748:JSTOR
716:JSTOR
621:JSTOR
514:S2CID
478:arXiv
379:wazir
331:Nqthm
284:to a
41:is a
1847:ISBN
1568:ISBN
1291:ISBN
1028:ISBN
990:PMID
930:PMID
823:ISBN
654:ISBN
568:ISBN
496:ISBN
114:and
57:(or
37:The
2118:doi
2037:doi
2001:doi
1936:doi
1890:doi
1839:doi
1794:doi
1758:doi
1708:doi
1660:doi
1656:310
1613:doi
1560:doi
1507:doi
1461:hdl
1412:doi
1370:doi
1246:doi
1199:doi
1096:doi
1058:doi
1020:doi
966:doi
954:363
920:doi
891:doi
857:doi
815:doi
740:doi
736:196
708:doi
704:196
613:doi
560:doi
488:doi
444:doi
2170::
2134:MR
2132:,
2124:,
2114:76
2112:,
2106:,
2077:14
2075:,
2051:,
2043:,
2033:81
2031:,
2009:MR
2007:,
1995:,
1942:,
1904:,
1898:MR
1896:,
1884:,
1880:,
1855:,
1845:,
1808:,
1802:MR
1800:,
1790:22
1788:,
1766:MR
1764:,
1754:14
1752:,
1722:,
1716:MR
1714:,
1704:69
1702:,
1696:,
1670:MR
1668:,
1654:,
1627:,
1619:,
1605:,
1587:,
1576:,
1566:,
1529:,
1521:,
1515:MR
1513:,
1503:24
1501:,
1495:,
1467:,
1426:,
1420:MR
1418:,
1408:37
1406:,
1386:MR
1384:,
1376:,
1366:97
1364:,
1331:,
1325:MR
1319:,
1304:^
1289:,
1273:^
1260:,
1254:MR
1252:,
1242:43
1240:,
1223:^
1205:,
1195:35
1193:,
1179:^
1163:,
1159:,
1126:^
1110:,
1104:MR
1102:,
1092:64
1090:,
1086:,
1066:MR
1064:,
1054:23
1026:,
996:,
988:,
982:MR
980:,
972:,
964:,
952:,
928:,
916:43
914:,
885:,
863:,
853:22
851:,
821:,
797:^
764:^
746:,
734:,
714:,
702:,
685:^
629:MR
627:,
619:,
609:61
607:,
566:,
546:^
525:^
512:,
506:MR
504:,
494:,
486:,
468:;
440:33
438:,
428:;
333:.
288:.
182:.
90:.
82:,
2160:.
2120::
2083::
2039::
2003::
1997:6
1977:n
1971:n
1938::
1892::
1886:9
1841::
1796::
1760::
1710::
1662::
1615::
1562::
1509::
1463::
1414::
1372::
1248::
1218:.
1201::
1098::
1060::
1022::
968::
960::
922::
893::
887:7
859::
817::
742::
710::
615::
588:.
562::
490::
480::
446::
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.