When I was growing up, I loved math puzzle and problem books. One of the earliest of these books I remember owning was entitled 536 Puzzles and Curious Problems by Henry Ernest Dudeney. Next, I stumbled into the work of Boris Kordemsky and then discovered Martin Gardner. The writings of Gardner changed my life and molded my personality. My blog is an homage to his work. If you like reading this blog, and you’ve yet to read any of Gardner’s works, I strongly recommend you invest in a few of his creations. Amazon has a helpful ministore where you can browse his books. (Don’t blame me if you end up going back and purchasing more and more). 
My favorite quote about Martin Gardner is that “He turned thousands of children into mathematicians, and thousands of mathematicians into children”. Click the link on the right to find a selection of his works. 
Martin Gardner (1914 – 2010) 
“He turned thousands of children into mathematicians, and thousands of mathematicians into children.” 
The subject of today’s article is a puzzle originally published by Henry Ernest Dudeney in 1907 from his book The Canterbury Puzzles. The Canterbury Puzzles is a compilation created by Dudeney in deference to the famous poetic work by Geoffery Chaucer, The Canterbury Tales.
The puzzle is pretty simple, if a little contrived. There are a sixtyfour towns arranged in a square grid layout with roads connecting (almost) each of the nearest neighbors; The only aberrations are the two locations in the middle of the bottom row which are not directly connected. You start at the town shaded on the map. You can travel from your current location to any of the connected towns (providing you have not already visited that town), and the aim is to visit all of the towns in a pilgrimage. Whilst your starting location is fixed and defined, the end of the pilgrimage is not important. The only requirement (other than only visiting each town once), is that you can only change direction 15 times. 
Paraphrasing this – Is it possible to start at the shaded location and trace a path that connects all the squares with no more than 15 straight lines, without taking you pencil off the paper? To the right is an example, but here this uses 17 lines. Can you do it in 15?
Can you connect all the towns using just fifteen lines? 
This is one of those problems that’s pretty easy to solve using recursion. Setting off from the starting location, it’s possible to go North, East, South or West. Whichever way we go initially, we increment the count of the number of straight lines used (When we setoff, any direction is the start of a new line). Then from each of these new locations, it’s possible to go North, East, South or West again but, we’re not allowed to revisit any town, so each time we are considering moving we need to check that: 
From every square we check the four possible cardinal moves according to the criterion above. If a move is possible we recurse in. Each move, we pass the state of the board (the towns already visited), the direction we travelled, and the running count of the number of lines to get to this stage (incrementing the number of lines drawn if the direction moved is not the same as the previous direction travelled). We carry on recursing in until we have visited all the towns (success), or there are no more moves (fail: we painted ourselves into a corner or dead end), or if the move would take the line count over 15 lines (fail: we can stop immediately, as the line count will only get larger and there can be no solution downstream of this point). 
I wrote a few lines of code to generate all the solutions using the recursive solution described above. There are 18 distinct solutions to this puzzle, and each of them ends at one of two locations (either the SW corner, or the town immediately to the left of the starting town). The original printing of the book only described one solution. It is shown on the left, hand drawn by Dudeney, with his initials "HED" on the lower left. 
Here are all the solutions:
What if we moved the location of the start town? Depending on where the pilgrimage starts there are a different number of solutions. Some starting locations have no possible solutions, others have many. Here is a matrix of the number of solutions based on the starting town. (The nonpassable link remains in the same location). The solutions are symmetric and mirrored in the vertical plane, reflected either side of the nonpassable link. All the solutions are rendered below (to save space, I’ve only rendered for solutions on the left of the mirror line), to see a solution which starts on the right, simply mirror the image over. No matter which town is the starting location it is not possible to complete the pilgrimage in less than fifteen straight lines. 
Number of solutions based on starting town:

Here's a legend for the solutions rendered below:
0  1  2  3  4  5  6  7 
8  9  10  11  12  13  14  15 
16  17  18  19  20  21  22  23 
24  25  26  27  28  29  30  31 
32  33  34  35  36  37  38  39 
40  41  42  43  44  45  46  47 
48  49  50  51  52  53  54  55 
56  57  58  59  60  61  62  63 
42 solutions.
3 solutions.
10 solutions.
0 solutions.
0 solutions.
50 solutions.
9 solutions.
20 solutions.
0 solutions.
0 solutions.
34 solutions.
12 solutions.
0 solutions.
0 solutions.
0 solutions.
10 solutions.
0 solutions.
0 solutions.
0 solutions.
0 solutions.
0 solutions.
0 solutions.
0 solutions.
0 solutions.
0 solutions.
18 solutions.
18 solutions.
0 solutions.
22 solutions.
4 solutions.
4 solutions.
22 solutions.
As mentioned earlier, The Canterbury Puzzles anthology is loosely based on Chaucer's work, The Canterbury Tales. In Chaucer's work there is a similarly named story called The Pardoner's Tale. This story has the moral that "Greed is the root of all evil" (Radix malorum est cupiditas).
In Chaucer's story, three young men set off to kill Death, and encounter an old man who says that they will find him under a nearby tree. When they arrive they discover a hoard of treasure and decide to stay with it overnight to carry it away the following morning.
Radix malorum est cupiditas
The three tired men draw straws to see who should fetch wine and food while the other two wait under the tree. The youngest of them draws the short straw and departs. Whilst he is away, the remaining two plot to overpower and stab him upon his return. The one who leaves for town also greedily plots to kill the other two and purchases rat poison; using it to lace the wine. When he returns with the food and drink, the other two kill him and then consume the poisoned wine, dying slow and painful deaths.
Those familiar with the last book in the Harry Potter series (The Deathly Hollows) may see a parallel with "The tale of the Three Brothers". J.K. Rowling confirmed, in an interview, that some inspiration for her story came from The Pardoner's tale. 
You can find a complete list of all the articles here.^{} Click here to receive email alerts on new articles.