List of impossible puzzles

Last updated

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

• 15 puzzle – Slide fifteen numbered tiles into numerical order. Impossible for half of the starting positions.
• Five room puzzle – Cross each wall of a diagram exactly once with a continuous line.
• MU puzzle – Transform the string MI to MU according to a set of rules.
• Mutilated chessboard problem – Place 31 dominoes of size 2×1 on a chessboard with two opposite corners removed.
• Coloring the edges of the Petersen graph with three colors
• Seven Bridges of Königsberg – Walk through a city while crossing each of seven bridges exactly once.
• Three cups problem – Turn three cups right-side up after starting with one wrong and turning two at a time.
• Three utilities problem – Connect three cottages to gas, water, and electricity without crossing lines.
• 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.

Related Research Articles The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other; thus, a solution requires that no two queens share the same row, column, or diagonal. The eight queens puzzle is an example of the more general n queens problem of placing n non-attacking queens on an n×n chessboard, for which solutions exist for all natural numbers n with the exception of n = 2 and n = 3. In mathematics, topology is concerned with the properties of a geometric object that are preserved under continuous deformations, such as stretching, twisting, crumpling, and bending; that is, without closing holes, opening holes, tearing, gluing, or passing through itself. A knight's tour is a sequence of moves of a knight on a chessboard such that the knight visits every square exactly once. If the knight ends on a square that is one knight's move from the beginning square, the tour is closed; otherwise, it is open. A chessboard is the type of gameboard used for the game of chess, on which the chess pawns and pieces are placed. A chessboard is usually square in shape, with an alternating pattern of squares in two colours. Though usually played on a surface, a tangible board is not a requirement to play the game. Traditionally wooden boards are made of unstained light and dark brown woods. To reduce cost, many boards are made with veneers of more expensive woods glued to an inner piece of plywood or chipboard. A variety of colours combinations are used for plastic, vinyl, and silicone boards. Common dark-light combinations are black and white, as well as brown, green or blue with buff or cream. Materials vary widely; while wooden boards are generally used in high-level games; vinyl, plastic, and cardboard are common for less important tournaments and matches and for home use. Decorative glass and marble boards are rarely permitted for games conducted by national or international chess federations. When they are permitted, they must meet various criteria The classical mathematical puzzle known as the three utilities problem; the three cottages problem or sometimes water, gas and electricity can be stated as follows:

Suppose there are three cottages on a plane and each needs to be connected to the water, gas, and electricity companies. Without using a third dimension or sending any of the connections through another company or cottage, is there a way to make all nine connections without any of the lines crossing each other?

A puzzle is a game, problem, or toy that tests a person's ingenuity or knowledge. In a puzzle, the solver is expected to put pieces together in a logical way, in order to arrive at the correct or fun solution of the puzzle. There are different genres of puzzles, such as crossword puzzles, word-search puzzles, number puzzles, relational puzzles, and logic puzzles. The Seven Bridges of Königsberg is a historically notable problem in mathematics. Its negative resolution by Leonhard Euler in 1736 laid the foundations of graph theory and prefigured the idea of topology. In the mathematical field of graph theory, a Hamiltonian path is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle is a Hamiltonian path that is a cycle. Determining whether such paths and cycles exist in graphs is the Hamiltonian path problem, which is NP-complete. Mathematical puzzles make up an integral part of recreational mathematics. They have specific rules, but they do not usually involve competition between two or more players. Instead, to solve such a puzzle, the solver must find a solution that satisfies the given conditions. Mathematical puzzles require mathematics to solve them. Logic puzzles are a common type of mathematical puzzle. The 15 puzzle is a sliding puzzle having 15 square tiles numbered 1–15 in a frame that is 4 tiles high and 4 tiles wide, leaving one unoccupied tile position. Tiles in the same row or column of the open position can be moved by sliding them horizontally or vertically, respectively. The goal of the puzzle is to place the tiles in numerical order. Kakuro or Kakkuro or Kakoro is a kind of logic puzzle that is often referred to as a mathematical transliteration of the crossword. Kakuro puzzles are regular features in many math-and-logic puzzle publications across the world. In 1966, Canadian Jacob E. Funk, an employee of Dell Magazines, came up with the original English name Cross Sums and other names such as Cross Addition have also been used, but the Japanese name Kakuro, abbreviation of Japanese kasan kurosu, seems to have gained general acceptance and the puzzles appear to be titled this way now in most publications. The popularity of Kakuro in Japan is immense, second only to Sudoku among Nikoli's famed logic-puzzle offerings. In mathematics, an invariant is a property of a mathematical object which remains unchanged after operations or transformations of a certain type are applied to the objects. The particular class of objects and type of transformations are usually indicated by the context in which the term is used. For example, the area of a triangle is an invariant with respect to isometries of the Euclidean plane. The phrases "invariant under" and "invariant to" a transformation are both used. More generally, an invariant with respect to an equivalence relation is a property that is constant on each equivalence class.

Induction puzzles are logic puzzles, which are examples of multi-agent reasoning, where the solution evolves along with the principle of induction.

The MU puzzle is a puzzle stated by Douglas Hofstadter and found in Gödel, Escher, Bach involving a simple formal system called "MIU". Hofstadter's motivation is to contrast reasoning within a formal system against reasoning about the formal system itself. MIU is an example of a Post canonical system and can be reformulated as a string rewriting system. This classical, popular puzzle involves a large rectangle divided into five "rooms". The objective of the puzzle is to cross each "wall" of the diagram with a continuous line only once.

In mathematics, a combinatorial explosion is the rapid growth of the complexity of a problem due to how the combinatorics of the problem is affected by the input, constraints, and bounds of the problem. Combinatorial explosion is sometimes used to justify the intractability of certain problems. Examples of such problems include certain mathematical functions, the analysis of some puzzles and games, and some pathological examples which can be modelled as the Ackermann function. The three cups problem, also known as the three cup challenge and other variants, is a mathematical puzzle that, in its most common form, cannot be solved. The mutilated chessboard problem is a tiling puzzle proposed by philosopher Max Black in his book Critical Thinking (1946). It was later discussed by Solomon W. Golomb (1954), Gamow & Stern (1958) and by Martin Gardner in his Scientific American column "Mathematical Games". The problem is as follows:

Suppose a standard 8×8 chessboard 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?

The bridge and torch problem is a logic puzzle that deals with four people, a bridge and a torch. It is in the category of river crossing puzzles, where a number of objects must move across a river, with some constraints. The 36 Cube is a three-dimensional sudoku puzzle created by ThinkFun. The puzzle consists of a gray base that resembles a city skyline, plus 36 colored towers. The towers come in six different colors and six different heights. The goal of the puzzle is to place all the towers onto the base so as to form a level cube with each of the six colors appearing once, and only once, in each row and column. The 36 cube was invented by Dr. Derrick Niederman, a PhD. at MIT. He came up with the idea while writing a book on whole numbers, after unearthing an 18th-century mathematical hypothesis. This supposition, the 36 officer problem, requires placing six regiments of six differently ranked officers in a 6-x-6 square without having any rank or regiment in the same column. Such an arrangement would form a Graeco-Latin square. Euler conjectured there was no solution to this problem. Although Euler was correct, his conjecture was not settled until Gaston Tarry came up with an exhaustive proof in 1901.