List of impossible puzzles explained

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 to 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

Notes and References

1. Archer . Aaron F. . November 1999 . A Modern Treatment of the 15 Puzzle . The American Mathematical Monthly . en . 106 . 9 . 793–799 . 10.1080/00029890.1999.12005124 . 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 . 10.2307/2312171 . 0002-9890.
3. Book: Hofstadter, Douglas R. . Gödel, Escher, Bach: an eternal golden braid . 1999 . Basic Books . 978-0-394-75682-0 . 20th anniversary . New York.
4. Starikova . Irina . Paul . Jean . Bendegem . Van . 2020 . Revisiting the mutilated chessboard or the many roles of a picture . Logique et Analyse. en . 10.13140/RG.2.2.31980.80007.
5. Book: Holton, Derek Allan . The Petersen graph . Sheehan . J. . 1993 . Cambridge University Press . 978-0-521-43594-9 . Australian Mathematical Society lecture series . Cambridge [England].
6. Euler . Leonhard . 1953 . Leonhard Euler and the Koenigsberg Bridges . Scientific American . 189 . 1 . 66–72 . 0036-8733.
7. Kasner . Edward . 1933 . Squaring the Circle . The Scientific Monthly . 37 . 1 . 67–71 . 0096-3771.
8. Book: Sanford, A. J. . The mind of man: models of human understanding . 1987 . Yale University Press . 978-0-300-03960-3 . New Haven.
9. Kullman . David E. . November 1979 . The Utilities Problem . Mathematics Magazine . en . 52 . 5 . 299–302 . 10.1080/0025570X.1979.11976807 . 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 . en . 364 . 1849 . 3199–3214 . 10.1098/rsta.2006.1885 . 1364-503X.