As you can probably tell from this recent post and this recent post, I've spent quite a bit of time thinking about the Knight's Tour lately.

These thoughts have reminded of a different type of Knight's Tour puzzle. This unusual variation involves moving the knight around a calendar.

It was 4 years ago, during September or October, that I was looking for blog post inspirations and ran across a thread on the XKCD forums, titled “Knight's Tour revamped”, which suggested playing the Knight's Tour on a calendar.

There was an added challenge, however: With your starting square being considered as move #1, how many dates could you land on that were the same as the move number? For example, if move #1 started on the 1st of the month, both the move number and the date would be 1.

As you can see in the original thread, the original poster used a July 2010 calendar and managed to find a complete Knight's Tour on which the 2nd, 6th, 11th, and 23rd moves landed on the dates of the 2nd, 6th, 11th, and 23rd respectively. Not surprisingly, it was Jaap of Jaap's Puzzle Page who found an 8-match solution.

I filed this in the back of my mind, but never really did anything until I ran across the Solving the Knight’s Tour on and off the Chess Board post which I mentioned last week. I liked the basic idea of being able to input a shape, and have the computer work out the tour, and especially the idea of using it to work out the XKCD forum's calendar challenge.

With a little knowledge of Java and graph theory under my belt, I managed to work out a program to solve it. For my fellow Java programmers, here's the main portion of my program, and here's the KnightsTour class I wrote to support it. Most of the hard work is done by lines 590 to 749. Those and lines 20 to 23 can removed if you're interested more in the general Knight's Tour than the particulars of the calendar challenge.

One of the first things I did, not surprisingly, was to find out how many day-to-move matches I could find in this month's calendar. I also found 8, all of which are highlighted below in red:



Yes, I've gone through every possible calendar, starting on every possible date, and learned quite a few interesting things in the process:

• Due to the fact that the number of days in a week (7) is odd, and the fact that the knight always moves an odd number of spaces (3), this means that a Knight on a calendar will always move from an odd date to an even date, and vice versa (just like what your teacher taught you about adding even and odd numbers). This, in turn, means that it's impossible to get ANY date matches if move #1 begins on an even-numbered date, as all the odd moves will land on even dates, and vice-versa.

• The above fact also means that if you start on an even date in a month with an odd number of days (29 or 31), you won't be able to complete a Knight's Tour.

• Yes, Jaap's 8-match path is the best one possible for July 2010 in particular. It also happens to be the only way to get 8 date-to-move matches in a Knight's Tour of a 31-day month beginning on a Thursday.

• Given any random month and year, you can always find a complete Knight's Tour and at least 6 date-to-move matches. Surprisingly, these minimum matches aren't found in the shortest months, as you may expect. With 30- and 31-day months starting on a Saturday, as well as 31-day months beginning on a Friday, 6 is the highest number of date-to-move matches you'll be able to find.

• There are months with 9 date-to-move matches, but none with more than that. 9 date-to-move matches can be found in a 29-, 30-, or 31-day month starting on a Tuesday or a Wednesday. In a 29-day month starting on a Thursday, or a 31-day month starting on a Monday, you can also find 9 date-to-move matches. You can often find more than 1 way to get to these matches, as well.

As it happens, next month (October 2014) is a 31-day month starting on a Wednesday, and here's one of the 3 possible ways to get 9 date-to-move matches:



I chose this one simply for the elegance of the column containing 16-23-30 and the diagonal containing 12-20-28. I also find it interesting that so many powers of 2 have date-to-move matches (2-4-8-16).

For the more math-inclined geeks, I'll wind this post up with all the maximum number of matches I've found, including the dates on which they start:

28-day months, starting on:
Sunday:    7 matches, beginning from the 1st or 23rd
Monday:    7 matches, beginning from the 1st or 21st
Tuesday:   8 matches, beginning from the 25th
Wedneday:  8 matches, beginning from the 1st
Thursday:  8 matches, beginning from the 1st or 5th
Friday:    8 matches, beginning from the 1st or 15th
Saturday:  7 matches, beginning from the 23rd or 25th

29-day months, starting on:
Sunday:    7 matches, beginning from the 1st
Monday:    7 matches, beginning from the 1st or 27th
Tuesday:   9 matches, beginning from the 25th
Wedneday:  9 matches, beginning from the 1st or 11th
Thursday:  9 matches, beginning from the 1st
Friday:    7 matches, beginning from the 1st, 5th, 27th, or 29th
Saturday:  7 matches, beginning from the 1st

30-day months, starting on:
Sunday:    7 matches, beginning from the 7th or 23rd
Monday:    8 matches, beginning from the 27th
Tuesday:   9 matches, beginning from the 25th
Wedneday:  9 matches, beginning from the 11th
Thursday:  8 matches, beginning from the 1st
Friday:    7 matches, beginning from the 1st or 7th
Saturday:  6 matches, beginning from the 1st or 25th

31-day months, starting on:
Sunday:    8 matches, beginning from the 23rd
Monday:    9 matches, beginning from the 7th or 31st
Tuesday:   9 matches, beginning from the 1st, 23rd, or 25th
Wedneday:  9 matches, beginning from the 7th
Thursday:  8 matches, beginning from the 5th
Friday:    6 matches, beginning from the 1st, 5th, 7th, or 31st
Saturday:  6 matches, beginning from the 1st, 23rd, 29th, or 31st