A Puzzle Is A Problem Or Enigma That Challenges Ingenuity

A puzzle is a problem or enigma that challenges ingenuity. In a basic puzzle you piece together objects in a logical way in order to come up with the desired shape, picture or solution. Puzzles are often contrived as a form of entertainment, but they can also stem from serious mathematical or logistical problems — in such cases, their successful resolution can be a significant contribution to mathematical research. Solutions to puzzles may require recognizing patterns and creating a particular order. People with a high inductive reasoning aptitude may be better at solving these puzzles than others. Puzzles based on the process of inquiry and discovery to complete may be solved faster by those with good deduction skills.

Types of puzzles The large number of puzzles that have been created can be divided into categories, for example a maze is a type of tour puzzle. Other categories include construction puzzles, stick puzzles, tiling puzzles, transport puzzles, disentanglement puzzles, sliding puzzles, logic puzzles, word puzzles, picture puzzles, jigsaw puzzles, lock puzzles, folding puzzles, combination puzzles and mechanical puzzles.

Tour puzzle In tour puzzles the player of the puzzle makes a trip around a board (usually but not necessarily two-dimensional) using a token which represents a traveller. Sometimes (as in mazes) the player him/herself makes the trip. Sometimes the player has more than one token with which to travel. Sometimes certain objects have to be found and/or retrieved on the way. Often there is a given start and finish position for the player's token. Some tour puzzles demand that certain points on the board have to be visited on the way. Maze puzzles are often of this type.

Examples of tour puzzles

Knight's tour The Knight's Tour is a mathematical problem involving a knight on a chessboard. The knight is placed on the empty board and, moving according to the rules of chess, must visit each square exactly once.

There are a great many solutions to the problem, of which exactly 26,534,728,821,064 have the knight finishing on a square from which it attacks the starting square, on an 8x8 board. [1] Such a tour is described as directed and closed. (A directed tour is a directed graph: the direction of the tour is specified. A closed tour is one that ends on the starting square.) The number of undirected closed tours is half this number, since every tour can be traced in reverse. Otherwise the tour is open (as in the first diagram). There are 9,862 undirected closed tours on a 6x6 board, and no such tours on smaller boards [2].

Schwenk's Theorem For any m × n board with m less than or equal to n, a closed knight's tour is always possible unless one or more of these three conditions are true: 1. m and n are both odd 2. m = 1, 2, or 4; m and n are not both 1 3. m = 3 and n = 4, 6, or 8

Condition 1 It is not hard to show that when condition 1 is true a closed knight's tour is impossible.

Imagine a chessboard colored black and white in the manner that we are all familiar with (alternating). Whenever a knight moves it lands on the opposite color. If it is on white, it moves to black. If it is on black, it moves to white. Since m and n are both odd, the number of white squares and black squares are different. For example, in a 5×5 checkerboard there are 13 of one color and 12 of the other. For a knight to have a closed tour it must visit the same number of white squares and black squares. But we have just seen that odd × odd boards have a different number of white squares and black squares, therefore closed tours do not exist. Open tours may still exist.

Condition 2 Condition 2 states that when the shorter side is length 1, 2, or 4, no closed tour is possible. It is easy to see why when m = 1 or 2 that no knight's tour is possible: the knight would not be able to reach every square (with the exception of the trivial case 1x1). It can be shown that a 4 × n board cannot have a closed tour. Start by assuming that a 4 × n board has a closed knight's tour. Let us construct 2 sets of squares, A1 and B1, A1 containing one half of the squares on the board and B1 containing the other half of the squares on the board. If we color this 4 × n board with a checkerboard pattern, we can define A1 as the set of white squares and B1 as the set of black squares. As previously established, the knight must alternate between white and black (A1 and B1).

The knight must alternate between green and red.

Consider the figure on the right. Define A2 as the set of green squares and B2 as the set of red squares in the figure. There are an equal number of red squares as green squares. Note that from a square in A2 the knight must next jump to a square in B2. And since the knight must visit every square, when the knight is on a B2 square in must move to an A2 next (otherwise the knight will need to make a repeat on an A2 square as well, but this is impossible).

If we follow the knight we will find a contradiction. 1. The first square the knight goes to will be a square of A1 and A2. If it is not,

we switch A2 and B2 so that it is true. 2. The second square must be an element of the sets B1 and B2. 3. The third square must be an element of A1 and A2. 4. The fourth square must be an element of the sets B1 and B2.

5. And so on. It follows that set A1 has the same elements as set A2, and set B1 has the same elements as set B2. But this is obviously not true, as the red and green pattern shown above is not the same as a checkerboard pattern; the set of red squares is not the same as the set of black squares (or white, for that matter). So our above assumption was false and there are no closed knight's tours for and 4 × n board, for any n.

Condition 3 Condition 3 is proved case by case. Attempting to construct a closed knight's tour on a 3 by 4, 3 by 6, or 3 by 8 will lead to definite failure. 3 by n boards with n not equal to 4, 6, or 8 can be shown to be possible with a repeated pattern.

All other cases Simply proving the above three conditions does not prove the theorem; it is still required to prove that all rectangular boards that do not fall in one of the above three categories have knight's tours.

Maze A maze is a complex tour puzzle in the form of a complex branching passage through which the solver must find a route. This is different from a labyrinth, which has an actual through-route and is not designed to be difficult to navigate (despite the common uses of the word to indicate various complex, confusing structures). The pathways and walls in a maze or labyrinth are fixed (predetermined). Maze-type puzzles where the given walls and paths may change during the game are covered under the main puzzle category of tour puzzles.

Solving mazes The mathematician Leonhard Euler was one of the first to analyze plane mazes mathematically, and in doing so made the first significant contributions to the branch of mathematics known as topology. Mazes containing no loops are known as "standard", or "perfect" mazes, and are equivalent to a tree in graph theory. Thus many maze solving algorithms are closely related to graph theory. Intuitively, if one pulled and stretched out the paths in the maze in the proper way, the result could be made to resemble a tree [1]. The following algorithms are designed to be used inside the maze by a traveler with no prior knowledge of the maze. [edit]

Random mouse algorithm

This is a trivial method that can be implemented by a very unintelligent robot or perhaps a mouse. It is simply to proceed in a straight line until an obstruction is reached, and then to make a random decision about the next direction to follow. [edit]

Wall follower

Traversal using right-hand rule

The wall follower, the best-known rule for traversing mazes, is also known as either the left-hand rule or the right-hand rule. If the maze is simply connected, that is, all its walls are connected together or to the maze's outer boundary, then by keeping one hand in contact with one wall of the maze the player is guaranteed not to get lost and will reach a different exit if there is one; otherwise, he or she will return to the entrance. Another perspective into why wall following works is topological. If the walls are connected, then they may be deformed into a loop or circle, as seen in the following video[2]. Then wall following reduces to walking around a circle from start to finish. If the maze is not simply connected (i.e. if the start or endpoints are in the center of the structure or the pathways cross over and under each other), this method will not be guaranteed to help the goal to be reached.

Wall-following can be done in 3D or higher dimensional mazes if its higher dimensional passages can be projected onto the 2D plane in a deterministic manner. For example, if in a 3D maze "up" passages can be assumed to lead northwest, and "down" passages can be assumed to lead southeast, then standard wall following rules can then be applied. [edit]

Pledge algorithm

Robot in a wooden maze

Disjoint mazes can still be solved with the wall follower method, if the entrance and exit to the maze are on the outer walls of the maze. If however, the solver starts inside the maze, it might be on a section disjoint from the exit, and wall followers will continually go around their ring. The Pledge algorithm (named after Jon Pledge of Exeter) can solve this problem (see "Turtle Geometry: the computer as a medium for exploring mathematics", Abelson & diSessa, 1980). The Pledge algorithm, designed to circumvent obstacles, requires an arbitrarily chosen direction to go toward. When an obstacle is met, one hand (say the right hand) is kept along the obstacle while the angles turned are counted. When the solver is facing the original direction again, and the angular sum of the turns made is 0, the solver leaves the obstacle and continues moving in its original direction. Note that the use of "total turning" rather than just the "current direction" allows the algorithm to avoid traps shaped like an upper case "G". If one proceeds left into the trap, one gets turned around a full 360 degrees by the walls. A naive "current direction" algorithm gets into a limit cycle as it leaves the lower rightmost wall heading left and runs into the curved section on the left again. The Pledge algorithm does not leave the rightmost wall due to the total turning not being zero at that point. It follows the wall all the way around, finally leaving it heading left on the bottom outside. This algorithm allows a person with a compass to find his way from any point inside to an outer exit of any finite and fair two-dimensional maze, regardless of the initial position of the solver. However, this algorithm will not work in doing the

reverse, namely finding the way from an entrance on the outside of a maze to some end goal within it. [edit]

Tremaux's algorithm

Tremaux's algorithm is an efficient method to find the way out of a maze that requires drawing a line on the floor to mark a path, and is guaranteed to work for all mazes that have well-defined passages. On arriving at a junction, pick a direction and mark it and the direction you came from. When arriving at a marked junction pick an unmarked passage if possible. If it is not possible to pick an unmarked passage take a marked one, marking it again (you can pick the path you came from). Never pick a twice marked path, where you will never need to take any passage more than twice. If there is no exit, this method will take you back to the start. [3] Tremaux's algorithm was referenced in The Simpsons episode Stop, or My Dog Will Shoot! when Lisa proposes this method for finding the exit of a tricky corn maze.

Logic maze Logic mazes, sometimes called 'mazes with rules', are logic puzzles with all the aspects of a tour puzzle that fall outside of the scope of a typical maze. These mazes have special rules, sometimes including multiple states of the maze or navigator. Popular logic mazes include tilt mazes and other novel designs which usually increase the complexity of the maze, sometimes to the point that the maze has to be designed by a program to eliminate multiple paths. Additional examples include: 

Area-mazes or A-mazes, which the area of the tile stepped on must alternately increase and decrease with every step.



Rolling dice mazes, in which a die is rolled onto cells based on various rules.



Number mazes, in which a grid of numbers is navigated by traveling the number shown on the current square.



Multi-State mazes, in which the rules for navigation change depending on how the maze has been navigated.

Construction puzzle From Wikipedia, the free encyclopedia

In a construction puzzle you have to build (assemble) a technical contraption. This may be a static object (like a bridge) or a mechanical object (like a machine). In a wider sense a construction puzzle is any puzzle where you have to assemble a given set of pieces in a certain way. Examples for these types of construction puzzles are the stick puzzles, many tiling puzzles and also some mechanical puzzles.

Stick puzzle From Wikipedia, the free encyclopedia

Stick puzzles use sets of 'polysticks' (essentially one-dimensional objects) which have to be assembled into two- or three-dimensional configurations. Polysticks are configurations of joined or unjoined thin (ideally one-dimensional) 'sticks'. The sticks may be matchsticks, or pieces of straw, wire or similar. A special (and very old) class of stick puzzles are 'matchstick puzzles', where all parts used are sticks (usually matchsticks) rather than polysticks. Some (trick-) puzzles can only be solved when one assumes that the sticks actually have measurements in more than one dimension.

Tiling puzzle From Wikipedia, the free encyclopedia

Tiling puzzles are puzzles involving two-dimensional packing problems in which a number of flat shapes have to be assembled into a larger given shape without overlaps (and often without gaps). Some tiling puzzles ask you to dissect a given shape first and then rearrange the pieces into another shape. Other tiling puzzles ask you to dissect a given shape while fulfilling certain conditions. The two latter types of tiling puzzles are also called dissection puzzles. Tiling puzzles may be made from wood, metal, cardboard, plastic or any other sheet-material. Many tiling puzzles are now available as computer games. Tiling puzzles have a long history. Some of the oldest and most famous are jigsaw puzzles and the Tangram puzzle.

Example of a tiling puzzle that utilizes negative space.

Other examples of tiling puzzles include:

Jigsaw puzzle A jigsaw puzzle is a tiling puzzle that requires the assembly of numerous small, often oddly shaped, interlocking and tessellating pieces. Each piece has a small part of a picture on it; when complete, a jigsaw puzzle produces a complete picture. Jigsaw puzzles were originally created by painting a picture on a flat, rectangular piece of wood, and then cutting that picture into small pieces with a jigsaw, hence the name. John Spilsbury, a London mapmaker and engraver, is credited with commercialising jigsaw puzzles around 1760[1]. Most modern jigsaw puzzles are made out of cardboard, since they are easier and cheaper to mass produce. An enlarged photograph or printed reproduction of a painting or other two-dimensional artwork is glued onto the cardboard before cutting. This board is then fed into a press. The press forces a set of hardened steel blades of the desired shape through the board until it is fully cut. This procedure is similar to making shaped cookies with a cookie cutter. The forces involved, however, are tremendously greater and a typical 1000-piece puzzle will require a press which can generate upwards of 700 tons of force to push the knives of the puzzle die through the board. A puzzle die comprises a flat board, often made from plywood, which has slots cut or burned in the same shape as the knives that will be used. These knives are set into the slots and covered in a compressible material, typically foam rubber, the function of which is the ejection of the cut puzzle pieces.

Eternity puzzle From Wikipedia, the free encyclopedia

This article is about the puzzle contest. For other uses of Eternity, see Eternity (disambiguation).

The eternity puzzle was a geometric puzzle with a million-pound prize, created by Christopher Monckton, who put up half the money himself, the other half being put up by underwriters in the London insurance market. The puzzle was distributed by the Ertl Company. The puzzle consisted of filling a large almost regular dodecagon with 209 irregularly shaped smaller polygons. It was launched in June 1999, by Ertl Toys, marketed to amateur puzzle solvers and 500,000 copies were sold worldwide, with the game becoming a craze at one point. Eternity was the best-selling puzzle or game in the UK at its price-point of £35 in its launch month. It was voted Puzzle of the Year in Australia. It sold in record numbers even in Greenland. Before marketing the puzzle, Monckton had thought that the puzzle would probably be solved within 1 to 3 years. One estimate made at the time stated that the puzzle would probably take longer than the lifetime of the Universe to solve. According to Eternity's rules, possible solutions to the puzzle would be received by mail on September 21, 2000. If no correct solutions were opened, the mail for the next year would be kept until September 30, 2001, the process being repeated every year until 2003, after which no entries would be accepted.

Solution The puzzle was solved on May 15, 2000, before the first deadline by two Cambridge mathematicians, Alex Selby and Oliver Riordan, who had used an ingenious technique to vastly accelerate their solution.[1] They realised that it was trivial to fill the board almost completely, to an "end-game position" where an irregularly-shaped void had to be filled with only a few pieces, at which point the pieces left would be the "wrong shapes" to fill the remaining space. The hope of solving the end-game depended vitally on having pieces that were easy to tile together in a variety of shapes. They started a computer search to find which pieces tiled well or badly, and then used this data to alter their otherwise-standard backtracking search program to use the bad pieces first, in the hope of being left with only good pieces in the hard final part of the search. This heuristic approach paid off rapidly, with a complete solution being obtained within seven months of brute-force search on two domestic PCs. The puzzle's inventor said that the prize payout had forced him to sell his home; however, in 2006 this was revealed to be a publicity story Eternity II was launched in Summer 2007 with a prize of $2 million.

Transport puzzle In transport puzzles you move yourself and/or tokens through a given landscape. As in rearrangement puzzles, no piece is ever lost or added to the board. In contrast to rearrangement puzzles, however, transport puzzles have all tokens follow certain routes given on the board; they cannot be lifted off the board and placed on faraway positions that have no visible connection to the from-position. Hence transport puzzles often mean that the player has to move (physical) objects in a very restricted space. The player may or may not be part of the game (himself or represented by a token on a board).

River crossing puzzle River crossing puzzle From Wikipedia, the free encyclopedia

A river crossing puzzle is a type of transport puzzle in which the object is to carry items from one river bank to another. The difficulty of the puzzle may arise from restrictions on which or how many items can be transported at the same time, or from which or how many items may be safely left together.[1] The setting may vary cosmetically, for example, by replacing the river by a bridge.[1] The earliest known river-crossing problems occur in the manuscript Propositiones ad Acuendos Juvenes (English: Problems to sharpen the young), traditionally said to be written by Alcuin. The earliest copies of this manuscript date from the 9th century; it contains three river-crossing problems, including the fox, goose and bag of beans puzzle and the jealous husbands problem.[2] Well-known river-crossing puzzles include: 

The fox, goose and bag of beans puzzle, in which a farmer must transport a fox, goose and bag of beans from one side of a river to another using a boat which can only hold one item in addition to the farmer, subject to the constraints that the fox cannot be left alone with the goose, and the goose cannot be left alone with the beans.



The jealous husbands problem, in which three married couples must cross a river using a boat which can hold at most two people, subject to the constraint that no woman can be in the presence of another man unless her husband is also present.

 

The bridge and torch problem.



Four people come to a river in the night. There is a narrow bridge, but it can only hold two people at a time. Because it's night, the torch has to be used when crossing the bridge. Person A can cross the bridge in 1 minute, B in 2 minutes, C in 5 minutes, and D in 8 minutes. When two people cross the bridge together, they must move at the slower person's pace. The question is, can they all get across the bridge in 15 minutes or less?

Solution

Elapsed Time Starting Side

Action

Ending Side

0 minutes

ABCD

2 minutes

CD

A and B cross forward, taking 2 minutes A B

CD

A returns, taking 1 minute

B

BCD

3 minutes

A

11 minutes

A

C and D cross forward, taking 8 minutes

13 minutes

AB

B returns, taking 2 minutes

15 minutes



CD

A and B cross forward, taking 2 minutes A B C D

Propositio de viro et muliere ponderantibus plaustrum. In this problem, also occurring in Propositiones ad Acuendos Juvenes, a man and a woman of equal weight, together with two children, each of half their weight, wish to cross a river using a boat which can only carry the weight of one adult.[3]

These problems may be analyzed using graph-theoretic methods[4], by dynamic programming,[5] or by integer programming.[3]

Seven Bridges of Königsberg The Seven Bridges of Königsberg is a famous solved mathematics problem inspired by an actual place and situation. The city of Königsberg, Prussia (now Kaliningrad, Russia) is set on the Pregel River, and included two large islands which were connected to each other and the mainland by seven bridges. The problem is to decide whether it is possible to walk a route that crosses each bridge exactly once.

Euler's solution In 1736, Leonhard Euler proved that it was not possible. In proving the result, Euler formulated the problem in terms of graph theory, by abstracting the case of Königsberg — first, by eliminating all features except the landmasses and the bridges connecting them; second, by replacing each landmass with a dot, called a vertex or node, and each bridge with a line, called an edge or link. The resulting mathematical structure is called a graph.

→

→

The shape of a graph may be distorted in any way without changing the graph itself, so long as the links between nodes are unchanged. It does not matter whether the links are straight or curved, or whether one node is to the left or right of another. Euler realized that the problem could be solved in terms of the degrees of the nodes. The degree of a node is the number of edges touching it; in the Königsberg bridge graph, three nodes have degree 3 and one has degree 5.

Euler proved that a circuit of the desired form is possible if and only if there are exactly two or zero nodes of odd degree. Such a walk is called an Eulerian path or Euler walk. Further, if there are two nodes of odd degree, those must be the starting and ending points of an Eulerian path. Since the graph corresponding to Königsberg has four nodes of odd degree, it cannot have an Eulerian path. An alternative form of the problem asks for a path that traverses all bridges and also has the same starting and ending point. Such a walk is called an Eulerian circuit or an Euler tour. An Eulerian circuit exists if and only if there are no nodes of odd degree. It can be seen that all Eulerian circuits are also Eulerian paths. Euler's work was presented to the St. Petersburg Academy on August 26, 1735, and published as Solutio problematis ad geometriam situs pertinentis (The solution of a problem relating to the geometry of position) in the journal Commentarii academiae scientiarum Petropolitanae in 1741.

Sokoban Sokoban (倉庫番 Sōkoban?, warehouse keeper) is a transport puzzle in which the player pushes boxes around a maze, viewed from above, and tries to put them in designated locations. Only one box may be pushed at a time, not two, and boxes cannot be pulled. As the puzzle would be extremely difficult to create physically, it is usually implemented as a video game. Sokoban was created in 1980 by Hiroyuki Imabayashi, and was published in 1982 by Thinking Rabbit, a software house based in Takarazuka, Japan. Thinking Rabbit also released three sequels: Boxxle, Sokoban Perfect and Sokoban Revenge. Implementations of Sokoban have been written for numerous computer platforms, including almost all home computer and personal computer systems. Versions also exist for several hand held and video game consoles, mobile phones, graphic calculators, and Canon PowerShot digital cameras. Many other puzzle games, such as Chip's Challenge and Rocks and Diamonds, implement Sokoban-based gameplay. The roguelike computer game NetHack contains a sequence of dungeon levels deliberately designed to simulate a Sokoban game.

Fifteen puzzle The n-puzzle is known in various versions, including the 8 puzzle, the 15 puzzle, and with various names. It is a sliding puzzle that consists of a grid of numbered squares with one square missing, and the labels on the squares jumbled up. If the grid is 3×3, the puzzle is called the 8-puzzle or 9-puzzle. If the grid is 4×4, the puzzle is called the 15-puzzle or 16-puzzle. The goal of the puzzle is to unjumble the squares by only making moves which slide squares into the empty space, in turn revealing another empty space in the position of the moved piece. The n-puzzle is a classical problem for modelling algorithms involving heuristics. Commonly used heuristics for this problem include counting the number of misplaced tiles and finding the sum of the Manhattan distances between each block and its position in the goal configuration. Note that both are admissible, i.e., they never overestimate the number of moves left, which ensures optimality for certain search algorithms such as A*.

Train shunting puzzle Train shunting puzzles, also often called railway shunting puzzles or railroad switching puzzles, are a type of transport puzzle. Shunting puzzles usually consist of a specific track layout, a set of initial conditions (typically the starting place of each item of rolling stock), a defined goal (the finishing place of each rolling stock item), and rules which must be obeyed while performing the shunting operations. There are often constraints such as making the minimum number of couplings and uncouplings, or making the minimum number of junction direction changes, or completing the puzzle within a specified time limit. Other important factors may include the lengths of tracks limiting the number of vehicles which can be placed along them. Some shunting puzzles allow certain types of rolling stock to navigate a particular section of track but not other types of rolling stock, for example a locomotive might not be allowed below a low bridge whereas wagons are allowed; or a particularly heavy wagon might not be allowed across a weak bridge.

Some train shunting puzzles have been developed as add-ons for railway simulator computer programs such as Auran's Trainz and Microsoft Train Simulator.

Disentanglement puzzle A disentanglement puzzle is a type of mechanical puzzle that involves disentangling one piece or set of pieces from another piece or set of pieces. The reverse problem of reassembling the puzzle can be as hard as—or even harder than—disentanglement. There are several different kinds of disentanglement puzzle, though a single puzzle may incorporate several of these features.

[edit]

Plate-and-ring puzzles

A plate-and-ring puzzle usually consists of three pieces: 

one plate or similar displaying many holes and/or indentations



a closed or nearly closed ring or a similar item.

The plate as well as the ring are usually made from metal. The ring has to be disentangled from the plate. Plate-and-ring puzzles have a long history and are among the first puzzles ever made. [edit]

Rattler puzzles

Rare nowadays, the rattler puzzles were very much in fashion around 1900. These early puzzles were made from wood. They usually consist of many smaller pieces assembled on a main piece which may have a big handle to hold the puzzle. The movable pieces have to be arranged just right to let a first piece be separated from the rest of the assembly. In this respect rattler puzzles are closely related to the lock puzzles and puzzle locks. [edit]

Wire puzzles

A wire puzzle in unsolved form

The same puzzle in solved form

Wire puzzles consist of two or more entangled pieces of more or less stiff wire. The pieces may or may not be closed loops. The closed pieces might be simple rings or have more complex shapes. Normally the puzzle must be solved by disentangling the two pieces without bending or cutting the wires. Wire puzzles have a long history. Early examples were made from horseshoes and similar material (see also tavern puzzles). More than 7000 wire puzzles are known. The mathematician Richard Hess has collected them in a book he privately publishes ('Compendium Of Over 7000 Wire Puzzles', first edition March 1991). Many of them are his own inventions. [edit]

Wire-and-string puzzles

Wire-and-string puzzles usually consist of: 

one piece of string, ribbon or similar, which may form a closed loop or which may have other pieces like balls fixed to its end.



one or several pieces of stiff wire



sometimes additional pieces like wooden ball through which the string is threaded.

One can distinguish three subgroups of wire-and-string puzzles: 

Closed string subgroup: Here the pieces of string consist of one closed loop. Usually the string has to be disentangled from the wire.



Unclosed loose string subgroup: Here the pieces of string are not closed, and are not attached to the wire. In this case the ends of the string are fitted with a ball, cube or similar which stops the string from slipping out too easily. Usually the string has to be disentangled from the wire. Sometimes other tasks have to be completed instead, such as shifting a ring or ball from one end of the string to another end.



Unclosed fixed string subgroup: Here the pieces of string are not closed, but are somewhere on its length attached to the wire. Obviously in these puzzles the task is not to disentangle the string from the wire. One possible task may be to shift a ring or ball from one end of the string to another end.

Tower of Hanoi

The Tower of Hanoi or Towers of Hanoi is a mathematical game or puzzle. It consists of three pegs, and a number of disks of different sizes which can slide onto any peg. The puzzle starts with the disks neatly stacked in order of size on one peg, the smallest at the top, thus making a conical shape. The objective of the puzzle is to move the entire stack to another peg, obeying the following rules: 

Only one disk may be moved at a time.



Each move consists of taking the upper disk from one of the pegs and sliding it onto another peg, on top of the other disks that may already be present on that peg.



No disk may be placed on top of a smaller disk.

Origins

Flag Tower of Hanoi

The puzzle was invented by the French mathematician Édouard Lucas in 1883. There is a legend about an Indian temple which contains a large room with three time-worn posts in it surrounded by 64 golden disks. The priests of Brahma, acting out the command of an ancient prophecy, have been moving these disks, in accordance with the rules of the puzzle. According to the legend, when the last move of the puzzle is completed, the world will end. The puzzle is therefore also known as the Tower of Brahma puzzle. It is not clear whether Lucas invented this legend or was inspired by it. The Tower of Hanoi is a problem often used to teach beginning programming, in particular, as an example of a simple recursive algorithm. If the legend were true, and if the priests were able to move disks at a rate of one per second, using the smallest number of moves, it would take them 264−1 seconds or roughly 600 billion years (operation taking place is ) .[1] (In context, the universe is currently about 13.7 billion years old.) There are many variations on this legend. For instance, in some tellings, the temple is a monastery and the priests are monks. The temple or monastery may be said to be in different parts of the world — including Hanoi, Vietnam, and may

be associated with any religion. In some versions, other elements are introduced, such as the fact that the tower was created at the beginning of the world, or that the priests or monks may make only one move per day. The Flag Tower of Hanoi may have served as the inspiration for the name. [edit]

Solution

Most toy versions of the puzzle have 8 disks. The game seems impossible to many novices, yet is solvable with a simple algorithm: [edit]

Simple solution

The following solution is a simple solution for the toy puzzle. Alternate moves between the smallest piece and a non-smallest piece. When moving the smallest piece, always move it in the same direction (either to the left or to the right, but be consistent). If there is no tower in the chosen direction, move it to the opposite end. When the turn is to move the non-smallest piece, there is only one legal move. [edit]

Recursive solution

As in many mathematical puzzles, finding a solution is made easier by solving a slightly more general problem: how to move a tower of h (h=height) disks from a starting peg f (f=from) onto a destination peg t (t=to), r being the remaining third peg and assuming t ≠ f. First, observe that the problem is symmetric for permutations of the names of the pegs (symmetric group S3). If a solution is known moving from peg f to peg t, then, by renaming the pegs, the same solution can be used for every other choice of starting and destination peg. If there is only one disk (or even none at all), the problem is trivial. If h=1, then simply move the disk from peg f to peg t. If h>1, then somewhere along the sequence of moves, the largest disk must be moved from peg f to another peg, preferably to peg t. The only situation that allows this move is when all smaller h-1 disks are on peg r. Hence, first all h-1 smaller disks must go from f to r. Subsequently move the largest disk and finally move the h-1 smaller disks from peg r to peg t. The presence of the largest disk does not impede any move of the h-1 smaller disks and can temporarily be ignored. Now the problem is reduced to moving h-1 disks from one peg to another one, first from f to r and subsequently from r to t, but the same method can be used both times by renaming the pegs. The same strategy can be used to reduce the h-1 problem to h-2, h-3, and so on until only one disk is left. This is called recursion. This algorithm can be schematized as follows.

Identify the disks in order of increasing size by the natural numbers from 0 up to but not including h. Hence disk 0 is the smallest one and disk h-1 the largest one. The following is a procedure for moving a tower of h disks from a peg f onto a peg t, with r being the remaining third peg: 

Step 1: If h>1 then first use this procedure to move the h-1 smaller disks from peg f to peg r.



Step 2: Now the largest disk, i.e. disk h-1 can be moved from peg f to peg t.



Step 3: If h>1 then again use this procedure to move the h-1 smaller disks from peg r to peg t.

By means of mathematical induction, it is easily proven that the above procedure requires the minimal number of moves possible, and that the produced solution is the only one with this minimal number of moves. Using recurrence relations, the exact number of moves that this solution requires can be calculated by: 2h − 1. This result is obtained by noting that steps 1 and 3 take Th − 1 moves, and step 2 takes one move, giving Th = 2Th − 1 + 1. The algorithm can be written elegantly in various programming languages:

Non-recursive solution The list of moves for a tower being carried from one peg onto another one, as produced by the recursive algorithm has many regularities. When counting the moves starting from 1, the ordinal of the disk to be moved during move m is the number of times m can be divided by 2. Hence every odd move involves the smallest disk. It can also be observed that the smallest disk traverses the pegs f, t, r, f, t, r, etc. for odd height of the tower and traverses the pegs f, r, t, f, r, t, etc. for even height of the tower. This provides the following algorithm, which is easier, carried out by hand, than the recursive algorithm. In alternate moves: 

move the smallest disk to the peg it has not recently come from.



move another disk legally (there will be one possibility only)

For the very first move, the smallest disk goes to peg t if h is odd and to peg r if h is even. So if the number of disks is even the solution will start: 1. Move disk 0 from peg f to peg r ignoring peg t.

2. Move disk 1 from peg f to peg t ignoring peg r. 3. Move disk 0 from peg r to peg t ignoring peg f. 4. Move disk 2 from peg f to peg r ignoring peg t. 5. Move disk 0 from peg t to peg f ignoring peg r. 6. Move disk 1 from peg t to peg r ignoring peg f. 7. Move disk 0 from peg f to peg r ignoring peg t. 8. Move disk 3 from peg f to peg t ignoring peg r. 9. Move disk 0 from peg r to peg t ignoring peg f. 10.Move disk 1 from peg r to peg f ignoring peg t. 11. Move disk 0 from peg t to peg f ignoring peg r. 12.Move disk 2 from peg r to peg t ignoring peg f. 13.Move disk 0 from peg f to peg r ignoring peg t. 14.Move disk 1 from peg f to peg t ignoring peg r. 15.Move disk 0 from peg r to peg t ignoring peg f. 16.Move disk 4 from peg f to peg r ignoring peg t. etc. Also observe that: 

Disks whose ordinals have even parity move in the same sense as the smallest disk.



Disks whose ordinals have odd parity move in opposite sense.



If h is even, the remaining third peg during successive moves is t, r, f, t, r, f, etc.



If h is odd, the remaining third peg during successive moves is r, t, f, r, t, f, etc.

[edit]

Binary solutions

Disk positions may be determined more directly from the binary (base 2) representation of the move number (the initial state being move #0, with all digits 0, and the final state being #2n−1, with all digits 1), using the following rules: 

There is one binary digit (bit) for each disk



The most significant (leftmost) bit represents the largest disk. A value of 0 indicates that the largest disk is on the initial peg, while a 1 indicates that it's on the final peg.



The bitstring is read from left to right, and each bit can be used to determine the location of the corresponding disk.



A bit with the same value as the previous one means that the corresponding disk is stacked on top the previous disk on the same peg. 



(That is to say: a straight sequence of 1's or 0's means that the corresponding disks are all on the same peg).

A bit with a different value to the previous one means that the corresponding disk is one position to the left or right of the previous one. Whether it is left or right is determined by this rule: 

Assume that the initial peg is on the left and the final peg is on the right.



Also assume "wrapping" - so the right peg counts as one peg "left" of the left peg, and vice versa.



Let n be the number of greater disks that are located on the same peg as their first greater disk and add 1 if the largest disk is on the left peg. If n is even, the disk is located one peg to the left, if n is odd, the disk located one peg to the right.

For example, in an 8-disk Hanoi: 





Move #0) 

The largest disk is 0, so it is on the left (initial) peg.



All other disks are 0 as well, so they are stacked on top of it. Hence all disks are on the initial peg.

Move #2^8-1) 

The largest disk is 1, so it is on the right (final) peg.



All other disks are 1 as well, so they are stacked on top of it. Hence all disks are on the final peg and the puzzle is complete.

Move #0b11011000) 

The largest disk is 1, so it is on the right (final) peg.



Disk two is also 1, so it is stacked on top of it, on the right peg.



Disk three is 0, so it is on another peg. Since n is odd, it is one peg to the right, i.e. on the middle peg.



Disk four is 1, so it is on another peg. Since n is still odd, it is one peg to the right, i.e. on the right peg.



Disk five is also 1, so it is stacked on top of it, on the right peg.



Disk six is 0, so it is on another peg. Since n is even, the disk is one peg to the left, i.e. on the middle peg.



Disks seven and eight are also 0, so they are stacked on top of it, on the middle peg.

Logic puzzle From Wikipedia, the free encyclopedia

A logic puzzle is a puzzle deriving from the mathematics field of deduction. This branch was produced by Charles Lutwidge Dodgson, who is better known under his pseudonym Lewis Carroll, the author of Alice's Adventures in Wonderland. In his book The Game of Logic he introduced a game to solve problems such as 

some games are fun



every puzzle is a game Q: Are all puzzles fun? A: Not necessarily.

Puzzles like this, where we are given a list of premises and asked what can be deduced from them, are known as syllogisms. Of course, this example is trivial. Dodgson goes on to construct much more complex puzzles consisting of up to 8 premises. In the second half of the 20th century mathematician Raymond M. Smullyan has continued and expanded the branch of logic puzzles with books such as The Lady or the Tiger?, To Mock a Mockingbird and Alice in Puzzle-Land. He popularized the "knights and knaves" puzzles, which involve knights, who always tell the truth, and knaves, who always lie. There are also logic puzzles that are completely non-verbal in nature. Some popular forms include Sudoku and Unisol, which involves using deduction to correctly place numbers in a grid; the nonogram, also called "Paint by Numbers", which involves using deduction to correctly fill in a grid with black-and-white squares to produce a picture; and logic mazes, which involve using deduction to figure out the rules of a maze.

Sudoku

Sudoku (数独 sūdoku?) is a logic-based number placement puzzle. The objective is to fill a 9×9 grid so that each column, each row, and each of the nine 3×3 boxes (also called blocks or regions) contains the digits from 1 to 9, only one time each (that is, exclusively). The puzzle setter provides a partially completed grid. Completed Sudoku puzzles are a type of Latin square, with an additional constraint on the contents of individual regions. Leonhard Euler is sometimes incorrectly cited as the source of the puzzle, based on his work with Latin squares.[1] The modern puzzle was invented by an American architect, Howard Garns, in 1979 and published by Dell Magazines under the name "Number Place".[2] It became popular in Japan in 1986, after it was published by Nikoli and given the name Sudoku, meaning single number. [3] It became an international hit in 2005.

Nonogram Nonograms or Paint by Numbers are picture logic puzzles in which cells in a grid have to be colored or left blank according to numbers given at the side of the grid to reveal a hidden picture. In this puzzle type, the numbers measure how many unbroken lines of filled-in squares there are in any given row or column. For example, a clue of "4 8 3" would mean there are sets of four, eight, and three filled squares, in that order, with at least one blank square between successive groups. These puzzles are often black and white but can also have some colors. If they are colored, the number clues will also be colored in order to indicate the color of the squares. Two differently colored numbers may or may not have a space in between them. For example, a black four followed by a red two could mean four black spaces, some empty spaces, and two red spaces, or it could simply mean four black spaces followed immediately by two red ones. Although there are no theoretical limits on the size of a nonogram, most do not exceed 100x100. It is also not restricted to square layout.

Balance puzzle A number of logic puzzles exist that are based on the balancing of similar-looking items, often coins, to determine which one is of a different value within a limited number of uses of the balance. These differ from puzzles where items are assigned weights, in that only the relative mass of these items is relevant.

A well-known example has nine (or fewer) items, say coins, that are identical in weight save for one, which in this example we will say is lighter than the others— a counterfeit. The difference is only perceptible by using a balance, but only the coins themselves can be weighed, and it can only be used twice in total. Is it possible to isolate the counterfeit coin with only two weighings? [edit]

Solution

The solution is based on dividing into groups of three. Two groups are balanced against each other; if one is lighter it contains the counterfeit coin; if they balance perfectly, all the coins weighed are authentic, and the counterfeit is in the third group. Therefore, for the first weighing, three coins are put on each side of the balance, and the counterfeit coin is either one of the three on the lighter side, or one of the three that hasn't been weighed if the scale balances. Put one of these three coins on either side of the balance; if one is lighter it is the counterfeit, and if they are equal the counterfeit is the one not on the balance. [edit]

The Twelve-Coin Problem

A more complex version exists where there are twelve coins, eleven of which are identical and one of which is different, but it is not known whether it is heavier or lighter than the others. This time the balance may be used three times to isolate the unique coin and determine its weight relative to the others. [edit]

Solution

The procedure is less straightforward for this problem, and the second and third weighings depend on what has happened previously. 

Four coins are put on each side. There are two possibilities:

1. One side is heavier than the other. If this is the case, remove three coins from the heavier side, move three coins from the lighter side to the heavier side, and place three coins that were not weighed the first time on the lighter side. (Remember which coins are which.) There are three possibilities: 1.a) The same side that was heavier the first time is still heavier. This means that either the coin that stayed there is heavier or that the coin that stayed on the lighter side is lighter. Balancing one of these against one of the other ten coins will reveal which of these is true, thus solving the puzzle. 1.b) The side that was heavier the first time is lighter the second time. This means that one of the three coins that went from the lighter side to the heavier side is the light coin. For the third attempt, weigh two of these coins against each other: if one is lighter, it is the unique coin; if they balance, the third coin is the light one. 1.c) Both sides are even. This means the one of the three coins that was removed from the heavier side is the heavy coin. For the third attempt, weigh two of these coins against each other: if one is heavier, it is the unique coin; if they balance, the third coin is the heavy one. 2. Both sides are even. If this is the case, all eight coins are identical and can be set aside. Take the four remaining coins and place three on one side of the balance. Place 3 of the 8 identical coins on the other side. There are three possibilities: 2.a) The three remaining coins are lighter. In this case you now know that one of those three coins is the odd one out and that it is lighter. Take two of those three coins and weigh them against each other. If the balance tips then the lighter coin is the odd one out. If the two coins balance then the third coin not on the balance is the odd one out and it is lighter. 2.b) The three remaining coins are heavier. In this case you now know that one of those three coins is the odd one out and that it is heavier. Take two of those three coins and weigh them against each other. If the balance tips then the heavier coin is the odd one out. If the two coins balance then the third coin not on the balance is the odd one out and it is heavier. 2.c) The three remaining coins balance. In this case you know that the unweighed coin is the odd one out. Weigh the remaining coin against one of the other 11 coins and this will tell you whether it is heavier or lighter.

In literature

Niobe, the protagonist of Piers Anthony's novel With a Tangled Skein, must solve the twelve-coin variation of this puzzle to find her son in Hell: Satan has disguised the son to look identical to eleven other demons, and he is heavier or lighter depending on whether he is cursed to lie or able to speak truthfully. The solution in the book follows the given example 1.c.

Bulls and cows From Wikipedia, the free encyclopedia

A game of Bulls and Cows in its Internet version.

Bulls and Cows, also known as Cows and Bulls, is an old code-breaking paper and pencil game for two players, similar to Mastermind. It is a game with numbers that may date back a century or more, and a probable inspiration for Mastermind. It is played by two opponents. On a sheet of paper, the players each write a 4-digit secret number. The digits must be all different. Then, in turn, the players try to guess their opponent's number who gives the number of matches. If the matching digits are on their right positions, they are "bulls", if on different positions, they are "cows". Example: 

Secret number: 4271



Opponent's try: 1234



Answer: 1 bull and 2 cows. (The bull is "2", the cows are "4" and "1".)

The first one to reveal the other's secret number wins the game. As the "first one to try" has a logical advantage, on every game the "first" player changes. In some places, the winner of the previous game will play "second". Sometimes, if the "first" player finds the number, the "second" has one more move to make and if he also succeeds, the result is even. The secret numbers for Bulls and cows are usually 4-digit-numbers, but the game can be played with 3 to 6 digit numbers (in every case it is more difficult than with 4). The game may also be played by two teams of 2-3 players. The players of every team discuss before making their move, much like in chess. A computer program moo, was the first Bulls and Cows computer implementation, written in the late 1960s by J. M. Grochow at MIT in the PL/I computer language for the Multics operating system. Because the game has simple rules, while it is difficult and entertaining, there are many computer variants; it is often included in telephones and PDAs.

Knights and Knaves From Wikipedia, the free encyclopedia

Knights and Knaves is a type of logic puzzle devised by Raymond Smullyan. On a fictional island, all inhabitants are either knights, who always tell the truth, or knaves, who always lie. The puzzles involve a visitor to the island who meets small groups of inhabitants. Usually the aim is for the visitor to deduce the inhabitants' type from their statements, but some puzzles of this type ask for other facts to be deduced. The puzzle may also be to determine a yes/no question which the visitor can ask in order to discover what he needs to know. An early example of this type of puzzle involves three inhabitants referred to as A, B and C. The visitor asks A what type he is, but does not hear A's answer. B then says "A said that he is a knave" and C says "Don't believe B: he is lying!" To solve the puzzle, note that no inhabitant can say that he is a knave. Therefore B's statement must be untrue, so he is a knave, making C's statement true, so he is a knight. Since A's answer invariably would be "I'm a knight", it is not possible to determine whether A is a knight or knave from the information provided.

Some Examples of "Knights and Knaves" puzzles

A large class of elementary logical puzzles can be solved using the laws of Boolean algebra and logic truth tables. Familiarity with boolean algebra and its simplification process is a prerequisite to understand the following examples. In particular, to solve Question 2 you must understand that the only way that an "if X then Y" statement can be false is for X to be true and Y to be false. John and Bill are residents of the island of knights and knaves. [edit]

Question 1

John says: We are both knaves. Who is who? [edit]

Question 2

John: If Bill is a knave then I am not a knight. Bill: We are kind of different. Who is who? Solution for Question #2 Using deductive reasoning there is no possible solution for the question. Listed below are all four cases shown as not possible. Case 1: John = knight and Bill = knight Since Bill is a knight, when he says, “We are kind of different” he must be telling the truth. Obviously, he is lying as they are both knights. Case 2: John = knight and Bill = knave Since Bill is a knave he must be lying when he says, “We are kind of different.” However, they are different which means he is telling the truth. Case 3: John = knave and Bill = knave Since Bill is a knave he must be lying when he says, “We are kind of different”. Bill is lying because they are the same. However, John must also lie when he says, “If Bill is a knave, then I am not a knight.” The hypothesis of the conditional statement Bill is a knave is true and the conclusion I (John) am not a knight is also true. Therefore, John is telling the truth. Case 4: John = knave and Bill = knight Since Bill is a knight, when he says, “We are kind of different” he must be telling the truth, which he is. However, John must lie when he says, “If bill is a knave,

then I am not a knight.” The hypothesis of the conditional statement Bill is a knave is false and the conclusion I (John) am not a knight is true. This is a true statement so John is telling the truth. The only way for John to lie would be for a true hypothesis and a false conclusion. To clarify John's statement Let p = Bill is a knave q = I am a knight John's statement is then: if p -> ~q, which = ~p V ~q, which is "either Bill is a knight or I am a knave". Since this statement is clearly true, John is not lying and not fulfilling his conditions as a knave, hence the case is impossible. Since all four cases are not possible, there is no correct solution for this question. [edit]

Question 3

Logician: Are you both knights? John answers either Yes or No, but the Logician does not have enough information to solve the problem. Logician: Are you both knaves? John answers No, and then changes his mind and says Yes. The Logician can now solve the problem. Who is who? [edit]

Question 4

Here is a rendition of perhaps the most famous of this type of puzzle: John and Bill are standing at a fork in the road. You know that one of them is a knight and the other a knave, but you don't know which. You also know that one road leads to Death, and the other leads to Freedom. 

By asking one yes/no question, can you determine the road to Freedom?



By asking one yes/no question, can you determine whether John is a knight?

This version of the puzzle was further popularised by a scene in the 1980's fantasy film, Labyrinth, in which Sarah (Jennifer Connelly) finds herself faced with two doors each guarded by a two-headed knight. One door leads to the castle at the centre of the labyrinth, and one to certain doom. It also showed up in the Doctor Who episode "Pyramids of Mars" [edit]

Solution to Question 1

This is what John is saying in a more extended form: "John is a knave and Bill is a knave." If John was a knight, he would not be able to say that he was a knave since he would be lying. Therefore the statement "John is a knave" must be true. Since knaves lie, and one statement is true, the other statement must be false. Therefore the statement "Bill is a knave" must be false which leads to the conclusion that Bill is a knight. The solution is that John is a knave and Bill is a knight. [edit]

Solution to Question 1, using Boolean algebra

We can use Boolean algebra to deduce who's who as follows: Let J be true if John is a knight and let B be true if Bill is a knight. Now, either John is a knight and what he said was true, or John is not a knight and what he said was false. Translating that into Boolean algebra, we get: (because (because

) )

(by de Morgan's law) (by the law of distributivity) Therefore John is a knave and Bill is a knight. Although most people can solve this puzzle without using Boolean algebra, the example still serves as a testament of the power of Boolean algebra in solving logic puzzles. [edit]

Solution to Question 4

For finding out which way leads to freedom the following question should be asked; "Will the other man tell me your path leads to Freedom?" If the man says Yes then the path doesn't lead to Freedom, if he says No then it does. The following logic is used to solve the problem. In this instance John is the Knight. You go up to him and ask him the question. If his path does lead to freedom he will say No since the Knave would lie and say the Knight's path doesn't lead to freedom. If his path doesn't lead to freedom he will say Yes since the Knave would say the path leads to freedom. In this instance John is the Knave. You go up and ask him the question. If his path does lead to freedom he will say No since the Knight would say it does lead

to freedom. If his path doesn't lead to freedom he would say Yes since the Knight would tell you it doesn't lead to freedom. The simplest solution to finding out which one is the Knight is to ask any obvious question, such as: Is 2+2 = 4? Is a foot 12 inches? etc. The Knight would reply Yes the Knave would reply No

The Hardest Logic Puzzle Ever The Hardest Logic Puzzle Ever is a title coined by George Boolos in La Repubblica 1992 under the title L'indovinello più difficile del mondo for the following Raymond Smullyan inspired logic puzzle:

“

Three gods A, B, and C are called, in some order, True, False, and Random. True always speaks truly, False always speaks falsely, but whether Random speaks truly or falsely is a completely random matter. Your task is to determine the identities of A, B, and C by asking three yes-no questions; each question must be put to exactly one god. The gods understand English, but will answer all questions in their own language, in which the words for yes and no are 'da' and 'ja', in some order. You do not know which word means which.

”

Boolos provides the following clarifications:[1]

“



It could be that some god gets asked more than one question (and hence that some god is not asked any question at all).



What the second question is, and to which god it is put, may depend on the answer to the first question. (And of course similarly for the third question.)



Whether Random speaks truly or not should be thought of as depending on the flip of a coin hidden in his brain: if the coin comes down heads, he speaks truly; if tails, falsely.



Random will answer 'da' or 'ja' when asked any yes-no question.[2]

History Boolos credits the logician Raymond Smullyan as the originator of the puzzle and John McCarthy with adding the difficulty of not knowing what 'da' and 'ja' mean. Related puzzles can be found throughout Smullyan's writings, e.g. in What is the Name of This Book?, pp. 149-156, he describes a Haitian island where half the inhabitants are zombies (who always lie) and half are humans (who always tell the truth) and explains that "the situation is enormously complicated by the fact that although all the natives understand English perfectly, an ancient taboo of the

island forbids them ever to use non-native words in their speech. Hence whenever you ask them a yes-no question, they reply 'Bal' or 'Da' - one of which means yes and the other no. The trouble is that we do not know which of 'Bal' or 'Da' means yes and which means no". There are other related puzzles in The Riddle of Scheherazade (see especially, p. 114). More generally this puzzle is based off of Smullyan's famous Knights and Knaves puzzles (e.g. on a fictional island, all inhabitants are either knights, who always tell the truth, or knaves, who always lie. The puzzles involve a visitor to the island who must ask a number of yes/no questions in order to discover what he needs to know). A version of these puzzles was popularized by a scene in the 1980's fantasy film, Labyrinth. There are two doors with two guards. One guard lies and one guard doesn't. One door leads to the castle and the other leads to "certain death". The puzzle is to find out which door leads to the castle by asking one of the guards one question. In the movie Sarah does this by asking "Would he tell me that this door leads to the castle?". [edit]

The solution

Boolos provided his solution in the same article in which he introduced the puzzle. Boolos states that the "first move is to find a god that you can be certain is not Random, and hence is either True or False".[2] There are many different questions that will achieve this result. One strategy is to use complicated logical connectives in your questions (either biconditionals or some equivalent construction). Boolos' question was: 

Does 'da' mean yes if and only if you are True if and only if B is Random?[3]

Equivalently: 

Are an odd number of the following statements true: you are False, 'ja' means yes, B is Random?

The puzzle's solution can be simplified by using counterfactuals.[4][5] The key to this solution is that, for any yes/no question Q, asking either True or False the question 

If I asked you Q, would you say 'ja'?

results in the answer 'ja' if the truthful answer to Q is yes, and the answer 'da' if the truthful answer to Q is no. The reason this works can be seen by looking at the eight possible cases. 

Assume that 'ja' means yes and 'da' means no.

(i) True is asked and responds with 'ja'. Since he is telling the truth the truthful answer to Q is 'ja', which means yes. (ii) True is asked and responds with 'da'. Since he is telling the truth the truthful answer to Q is 'da', which means no. (iii) False is asked and responds with 'ja'. Since he is lying it follows that if you asked him Q he would instead answer 'da'. He would be lying, so the truthful answer to Q is 'ja', which means yes. (iv) False is asked and responds with 'da'. Since he is lying it follows that if you asked him Q he would in fact answer 'ja'. He would be lying, so the truthful answer to Q is 'da', which means no. 

Assume 'ja' means no and 'da' means yes.

(v) True is asked and responds with 'ja'. Since he is telling the truth the truthful answer to Q is 'da', which means yes. (vi) True is asked and responds with 'da'. Since he is telling the truth the truthful answer to Q is 'ja', which means no. (vii) False is asked and responds with 'ja'. Since he is lying it follows that if you asked him Q he would in fact answer 'ja'. He would be lying, so the truthful answer to Q 'da', which means yes. (viii) False is asked and responds with 'da'. Since he is lying it follows that if you asked him Q he would instead answer 'da'. He would be lying, so the truthful answer to Q is 'ja', which means no. Using this fact, one may proceed as follows.[6] 

Ask god B, "If I asked you 'Is A Random?', would you say 'ja'?". If B answers 'ja', then either B is Random (and is answering randomly), or B is not Random and the answer indicates that A is indeed Random. Either way, C is not Random. If B answers 'da', then either B is Random (and is answering randomly), or B is not Random and the answer indicates that A is not Random. Either way, A is not Random.



Go to the god who was identified as not being Random by the previous question (either A or C), and ask him: "If I asked you 'Are you True?', would you say 'ja'?". Since he is not Random, an answer of 'ja' indicates that he is True and an answer of 'da' indicates that he is False.



Ask the same god the question: "If I asked you 'Is B Random?', would you say 'ja'?". If the answer is 'ja' then B is Random; if the answer is 'da' then the god you have not yet spoken to is Random. The remaining god can be identified by elimination.

[edit]

Random's behaviour

Most readers of the puzzle assume that Random will provide completely random answers to any question asked of him; however, the puzzle does not actually state this. In fact, Boolos' third clarifying remark explicitly refutes this assumption. 

Whether Random speaks truly or not should be thought of as depending on the flip of a coin hidden in his brain: if the coin comes down heads, he speaks truly; if tails, falsely.

This says that Random randomly acts as a liar or a truth-teller, not that Random answers randomly. A small change to the question above yields a question which will always elicit a meaningful answer from Random. The change is as follows: 

If I asked you Q in your current mental state, would you say 'ja'?[6]

We have effectively extracted the truth-teller and liar personalities from Random and forced him to be only one of them. This completely trivializes the puzzle since we can now get truthful answers to any questions we please. 

1. Ask god A, "If I asked you 'Are you Random?' in your current mental state, would you say 'ja'?"

If A answers 'ja', then A is Random:  

2a. Ask god B, "If I asked you 'Are you True?', would you say 'ja'?"

If B answers 'ja', then B is True and C is False. If B answers 'da', then B is False and C is True. In both cases, the puzzle is solved.

If A answers 'da', then A is not Random:  

2b. Ask god A, "If I asked you 'Are you True?', would you say 'ja'?"

If A answers 'ja', then A is True. If A answers 'da', then A is False.  

3. Ask god A, "If I asked you 'Is B Random?', would you say 'ja'?"

If A answers 'ja', then B is Random, and C is the opposite of A. If A answers 'da', then C is Random, and B is the opposite of A.

We can modify Boolos' puzzle so that Random is actually random by replacing Boolos' third clarifying remark with the following. 

Whether Random says 'ja' or 'da' should be thought of as depending on the flip of a coin hidden in his brain: if the coin comes down heads, he says 'ja'; if tails, he says 'da'.

With this modification, the puzzle's solution demands the more careful godinterrogation given at the end of the The Solution section.

Exploding god-heads In A Simple Solution to the Hardest Logic Puzzle Ever,[7] the puzzle is developed further by pointing out that it is not the case that 'ja' and 'da' are the only possible answers a god can give.[4] It is also possible for a god to be unable to answer at all. For example, if the question "Are you going to answer this question with the word that means no in your language?" is put to True, he cannot answer truthfully. (The paper represents this as his head exploding, "...they are infallible gods! They have but one recourse – their heads explode")[6] Allowing the "exploding head" case gives yet another solution of the modified puzzle (modified so that Random is actually random) and introduces the possibility of solving the original puzzle (unmodified) in just two questions rather than three. In support of a two-question solution to the puzzle, the authors solve a similar simpler puzzle using just two questions. 

Three gods A, B, and C are called, in some order, Zephyr, Eurus, and Aeolus. The gods always speak truly. Your task is to determine the identities of A, B, and

C by asking three yes-no questions; each question must be put to exactly one god. The gods understand English and will answer in English.[6]

Note that this puzzle is trivially solved with three questions (just ask away!). To solve the puzzle in two questions, the following lemma is proved. Tempered Liar Lemma. If we ask A "Is it the case that {[(you are going to answer 'no' to this question) AND (B is Zephyr)] OR (B is Eurus) }?", a response of 'yes' indicates that B is Eurus, a response of 'no' indicates that B is Aeolus, and an exploding head indicates that B is Zephyr. Hence we can determine the identity of B in one question.[6]

Using this lemma it is simple to solve the puzzle in two questions. A similar trick (tempering the liar's paradox) can be used to solve the original puzzle in two questions.

Wine/water mixing problem From Wikipedia, the free encyclopedia

In the wine/water mixing problem, one starts with two containers, one holding wine and the other an equal volume of water. A cup of wine is taken from the wine container and added to the water. A cup of the wine/water mixture is then returned to the wine container, so that the volumes in the containers are again equal. The question is then posed—which of the two mixtures is purer?[1] The problem can be solved without resorting to computation. It is not necessary to state the volumes of wine and water, as long as they are equal. The volume of the cup is irrelevant, as is the degree of stirring of the wine/water mixture. Also, any number of transfers can be made, as long as the volumes of liquid in each cup are the same at the end.[2] [edit]

Solution

The mixtures should be visualized as separated into their water and wine components. Conservation of substance then implies that the volume of wine in the container holding mostly water has to be equal to the volume of water in the container holding mostly wine.[2] To help in grasping this, the wine and water may be represented by 80 red and 80 white marbles, respectively. If 20, say, red marbles are mixed in with the white marbles, and 20 marbles of any color are returned to the red container, then there will again be 80 marbles in each container. If there are now x white marbles in the red container, then there must

be x red marbles in the white container. The mixtures will therefore be of equal purity. An example is shown below. Time Step Red Marble Container 0

80 (all red)

1 2

White Marble Container 80 (all white)

20 (all red) → 60 (all red)

3 4

Action

100 (80 white, 20 red) ← 20 (16 white, 4 red)

80 (64 red, 16 white)

80 (64 white, 16 red)

Eight queens puzzle

One possible solution

The eight queens puzzle is the problem of putting eight chess queens on an 8×8 chessboard such that none of them is able to capture any other using the standard chess queen's moves. The queens must be placed in such a way that no two queens would be able to attack 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 puzzle of placing n queens on an n×n chessboard(n ≥ 4).