List of impossible puzzles

"Impossible puzzle" redirects here. For the puzzle sometimes called the Impossible Puzzle, see Sum and Product Puzzle.

This is a list of puzzles that cannot be solved. An impossible puzzle is a puzzle that cannot be resolved, either due to lack of sufficient information, or any number of logical impossibilities.

• 15 Puzzle – Slide fifteen numbered tiles into numerical order. It is impossible to solve in half of the starting positions. ^[1]
• Five room puzzle – Cross each wall of a diagram exactly once with a continuous line. ^[2]
• MU puzzle – Transform the string MI to MU according to a set of rules. ^[3]
• Mutilated chessboard problem – Place 31 dominoes of size 2×1 on a chessboard with two opposite corners removed. ^[4]
• Coloring the edges of the Petersen graph with three colors. ^[5]
• Seven Bridges of Königsberg – Walk through a city while crossing each of seven bridges exactly once. ^[6]
• Squaring the circle, the impossible problem of constructing a square with the same area as a given circle, using only a compass and straightedge. ^[7]
• Three cups problem – Turn three cups right-side up after starting with one wrong and turning two at a time. ^[8]
• Three utilities problem – Connect three cottages to gas, water, and electricity without crossing lines. ^[9]
• Thirty-six officers problem – Arrange six regiments consisting of six officers each of different ranks in a 6 × 6 square so that no rank or regiment is repeated in any row or column. ^[10]

See also

• Impossible Puzzle, or "Sum and Product Puzzle", which is not impossible
• -gry, a word puzzle
• List of undecidable problems, no algorithm can exist to answer a yes–no question about the input

References

1. Archer, Aaron F. (November 1999). "A Modern Treatment of the 15 Puzzle". The American Mathematical Monthly. 106 (9): 793–799. doi:10.1080/00029890.1999.12005124. ISSN   0002-9890.
2. Bakst, Aaron; Gardner, Martin (May 1962). "The Second Scientific American Book of Mathematical Puzzles and Diversions". The American Mathematical Monthly. 69 (5): 455. doi:10.2307/2312171. ISSN   0002-9890.
3. Hofstadter, Douglas R. (1999). Gödel, Escher, Bach: an eternal golden braid (20th anniversary ed.). New York: Basic Books. ISBN   978-0-394-75682-0.
4. Starikova, Irina; Paul, Jean; Bendegem, Van (2020). "Revisiting the mutilated chessboard or the many roles of a picture". Logique et Analyse. doi:10.13140/RG.2.2.31980.80007.
5. Holton, Derek Allan; Sheehan, J. (1993). The Petersen graph. Australian Mathematical Society lecture series. Cambridge [England]: Cambridge University Press. ISBN   978-0-521-43594-9.
6. Euler, Leonhard (1953). "Leonhard Euler and the Koenigsberg Bridges". Scientific American. 189 (1): 66–72. ISSN   0036-8733.
7. Kasner, Edward (1933). "Squaring the Circle". The Scientific Monthly. 37 (1): 67–71. ISSN   0096-3771.
8. Sanford, A. J. (1987). The mind of man: models of human understanding. New Haven: Yale University Press. ISBN   978-0-300-03960-3.
9. Kullman, David E. (November 1979). "The Utilities Problem". Mathematics Magazine. 52 (5): 299–302. doi:10.1080/0025570X.1979.11976807. ISSN   0025-570X.
10. Huczynska, Sophie (October 2006). "Powerline communication and the 36 officers problem". Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences. 364 (1849): 3199–3214. doi:10.1098/rsta.2006.1885. ISSN   1364-503X.