Evolve a Solution to the "Nine Dots Puzzle"
by Ted Kaehler
The Nine Dots Puzzle
This is a wonderful puzzle that everyone should have a chance to solve by
themselves. The solution has an "ah ha" that is thrilling. As a teenager, this author has a vivid memory of being challenged to solve the Nine Dots Puzzle at a noisy
afterschool gathering of "smart kids".
The statement is simple: Draw nine dots in three rows of three, as shown here.
Cover all nine dots by drawing four straight lines without lifting your pencil from the paper.
Assume that the dots are
tiny points that do not have finite area. Go ahead and try the puzzle on paper
now.
The solution of the nine dots problem has a little trick in it. If you get
stuck in one mode of thinking, and don't realize that there is another way, and
you can't solve the puzzle. For this reason, the nine dots puzzle is a
prominent example in several books about creative thinking.
One such book is Lateral Thinking: Creativity Step by Step by Edward de
Bono (Harper & Row, 1970, pages 95-96). Solving the nine dots problem requires
one to challange one's assumptions about what form the solution can take. "At
first it seems easy and various attempts are made to link up the dots. Then it
is found that one always needs more than four [lines]."
James L. Adams uses the same problem in Conceptual Blockbusting, A Guide to
Better Ideas (Addison-Wesley, 1974, pages 24-33). "The overtly strict
limits are a block in the mind of the solver. The widespread nature of this
block is what makes this puzzle classic." People in the audiences of Adams'
talks started submitting outlandish solutions that truly broke out of their
conceptual blocks. These include:
- "Lay the paper on the surface of the Earth. Circumnavigate the globe
twice plus a few inches, displacing a little each time so as to pass through the next
row on each circuit."
- Draw parallel lines through each row of dots. Extend two parallel
lines until they meet in a very narrow corner far away.
- A ten year old girl wrote in to suggest using a very wide pen that covers
all nine dots with one stroke.
We will forgo these "extremely creative" solutions to see if we can get
evolution to solve this puzzle in the normal way -- a way that is known to be
difficult for humans. We
simply want four line segments that cover all nine dots and that can be
drawn without lifting one's pencil from the page.
Here are four segments that are attached. They were drawn without lifting the pen from the paper. Unfortunately, the dot in the center is not covered. So, this is not a solution.
Let's write a program to discover a legitimate solution via artificial evolution.
Encoding the Problem
In order to get an evolution program to solve the problem, we must "represent
the problem" inside the computer.
Let's generalize a little to an arbitrary collection of dots, not lined up in a grid.
A potential solution will be an array of points in the order they are traversed by the pen. Here are the coordinates of the dots:
(0,2) (1,2) (2,2)
(0,1) (1,1) (2,1)
(0,0) (1,0) (2,0)
In Javascript an array with those points would print out as:
[[0,2], [1,2], [2,2],
[0,1], [1,1], [2,1],
[0,0], [1,0], [2,0]]
A potential solution consists of those same dots, but in a different order. We
want them to be in the order that lets four straight lines cross all
nine dots.
Let's add some markers that show the three places where the line turns. Here is the way we will represent this failed solution:
[[0,2], [1,2], [2,2], "turn",
[2,1], [2,0], "turn",
[1,0], [0,0], "turn",
[0,1], [1,1]]
You can see that the last point in the list, [1, 1], is the middle dot. It is in the fourth line segment, but it is not co-linear. This is an incorrect solution.
Giving a Gemone a Score
The array above is the genome of a trial solution to the nine dots puzzle.
We will evolve this genome until it scores very well in the areas that
make a legal solution.
In order for an evolution algorithm to work, it is very important to be able to represent solutions that are incorrect. A progression of bad solutions will lead to a much better solution. For this to happen, we must allow our data structures to represent bad solutions.
A program will produce a score for each genome. There are several ways a solution can be flawed. Our program will need to notice each of these.
We will need to detect when two line segments are parallel. These two successive segments are parallel, and deserve a bad score.
[[0,2], [1,2], [2,2], "turn", [2,1], [1,1], [0,1]
In the same way, a "T" intersection is not allowed. The turning point is actually in the middle of the first line segment.
[[0,2], [1,2], [2,2], "turn", [1,1], [1,0]]
Another way a solution can be incorrect is for segments 1 and 3 to attach to the same end of segment 2. Our list of points has an order. We need to know where the next turning point is on a segment. For full credit, the next turning point must be on the same end of the previous segment as its last point.
[[0,0], [0,1], "turn", [0,2], [1,2], [2,2], "turn", [1,1], [2,0]]
To detect all of these cases, we need to know the point of intersection of two line segments. In the array, we will replace 'turn' with an object that can compute and hold the intersection point.
The next page has the code for finding the point of intersection of two lines. Of course, we'll find it by artificial evolution.
Next: Search for the Intersection of Two Lines