Thursday, June 23, 2011

An explanation on the 5 Room House Puzzle

This old popular puzzle, called “Five Room House puzzle” (also known as “Walls and Lines puzzle”, or “Cross the Network puzzle”), is canonically represented as a rectangular diagram divided into five rooms, as shown opposite. The object of the puzzle is to draw a continuous path through the walls of all 5 rooms, without going through any wall twice, and without crossing any path. The path can, of course, end in any room, not necessarily in the room from where it started. Some puzzle diagrams represent the rooms with openings supposed to be doors. In this instance, the challenge is to visit every room of the apartment by walking through every door exactly once.


Requirements for solvability

Whether starting and ending in the same room, or starting in one room and ending in another one, every other room of the diagram/apartment must have an even number of doors... That is, pair(s) of ‘in’ and ‘out’ doors (as doors CANNOT be used TWICE, we have then to use an even number of doors as we ENTER and LEAVE those rooms).



Let’s suppose we start in a room with an odd number of doors, then it is possible to visit all the 5 rooms of the apartment if and ONLY if another room has an odd number of doors - representing the departure and the arrival points of the continuous path - , and all the other rooms have an even number of doors. In a few words, for this topological puzzle to be solvable, there may NOT be more than TWO rooms with an odd number of doors. Since the puzzle has THREE rooms with an odd number of openings/doors, it is mathematically impossible to complete a circuit crossing.

Analogously, a continuous line that enters and leaves one of the rooms crosses two walls. Since the THREE contiguous larger rooms each have an odd number of walls to be crossed, it follows that an END of a line must be inside each of them if all the 16 walls are crossed. But a unicursal line has only TWO ends,this contradiction makes the 5 Room House puzzle unsolvable.

However, if we close a door or add an extra room to the puzzle (see fig. a andb below), then it becomes solvable. Now, you can easily draw one continuous line that passes through every opening exactly once... Try it! (the five-room variant on the left (fig. a) is just a little harder to solve, because you have to figure out where to start)


The Five Room House is actually a classic example of an impossible puzzle — one that bears no positive solution. In this particular case, the solution consists in finding that the problem has no solution!

Graph theory
The insolubility of the 5 Room House problem can be proved using a graph theory approach, with each room being a vertex and each wall being an edge of the graph (see image opposite). In fact, this puzzle is similar to the famous “seven bridges of Königsberg” problem thanks to which the eminent Swiss mathematician Leonhard Euler laid the foundations of graph theory.
Euler wondered whether there was a way of traversing each of the 7 bridges over the river Pregel atKönigsberg (now Kaliningrad) once and only once, starting and returning at the same point in the town. He finally realized that the problem had no solutions!

0 comments:

Post a Comment