﻿ The Canterbury Puzzles: The Pardoner's Puzzle

### The Canterbury Puzzles: The Pardoner's Puzzle

 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 mini-store 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 Pardoner’s Puzzle

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 sixty-four 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?

### Solving

 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 set-off, 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:
1. The town has not yet been visited.
2. That it’s possible to move that way (not at an edge/corner, nor at the restricted link on the bottom).
3. That if we need to change direction we don’t exceed the 15 lines limit.
 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).

### Solutions

 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:

### Different Strokes

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 non-passable link remains in the same location).

The solutions are symmetric and mirrored in the vertical plane, reflected either side of the non-passable 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:

 42 3 10 0 0 10 3 42 0 50 9 20 20 9 50 0 0 0 34 12 12 34 0 0 0 0 0 10 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 18 18 0 0 18 18 0 22 4 4 22 22 4 4 22

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.

# The Canterbury Tales

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.