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.

“He turned thousands of children into mathematicians, and thousands of mathematicians into children.”

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?

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:

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.

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:

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.