The Knight Errant Puzzle
The Ultimate Book of Number Puzzles by Kenneth Kelsey contains various puzzles which relate to magic and semimagic squares.
On page 48, there is a puzzle which combines a semimagic square (a square grid of numbers in which the numbers in each row and column are equal, but not the diagonals) with a knight's tour (a path taken by a chess knight which visits every square exactly once).
Putting to one side the story of the promised fame and fortune and Bandar's curiously specific spellcasting, let's reduce the problem to its mathematical essentials:
Given an 8x8 chess board, the task is to find a knight's tour which satisfies the following conditions:
- The knight numbers the squares as they are visited. The starting square is numbered "1", the next square "2", and so on until the last square which is numbered "64".
- The resulting square must be a semimagic square: the sum of the numbers in each of the eight rows, and in each of the eight columns, must equal 260.
- Each of the completed square's four 4x4 quadrants must itself be a semimagic square. Equivalently, the sum midway along each row, and midway down each column, must equal 130.
- The tour must start on the leftmost column of the board and finish on the rightmost column. This requirement is not explicitly stated in the book but it is implied by how the puzzle is framed and is fulfilled by all four solutions given in the book.
We'll call a solution a "nested semimagic knight's tour" — that is, a semimagic knight's tour with the additional requirement that each of the four 4x4 quadrants of the square is itself a semimagic square.
Kelsey writes "I have been unable to work out more than four variations of this interesting knight's move square — ignoring rotations and reflections." He presents incomplete representations of these four solutions as puzzles, inviting the reader to complete them.
Here are the four solutions presented in the book.
I wrote a program to find any more nested semimagic knight's tours, ignoring rotations and reflections.
The source is available as a GitHub repository.
This program finds the four solutions published by Kelsey above and the additional four presented below.
Solutions #5 and #6 are identical except for the positions of steps 9, 10, 39 and 40 in the top-right quadrant. Solutions #7 and #8 differ only in the positions of steps 25, 26, 55 and 56.
Incidentally, although none of the eight solutions is a simple rotation or reflection of any other, they are all "paired" in another way: solutions #1 and #2, for example, are the same solution, but with the board horizontally reflected and the path reversed. Solutions #3 and #4, #5 and #7, and #6 and #8 are related in the same way.
The program completes the search in around 6–7 minutes when run in 12 concurrent threads on my computer (3.7 GHz 6-core AMD CPU).
The program uses a depth-first search to find all possible paths from a given starting square. If the knight discovers it has no legal moves from the current position, it backtracks and tries the next available move from its previous position.
It would be impractical to enumerate all possible knight's tours on an 8x8 grid (over 19 quadrillion of them!) and then check the other conditions. So, to cut down the vast search space and eliminate paths that can never lead to a solution, we abandon a path if we can prove that it cannot possibly lead to a valid solution.
Recall that the tour must start in the leftmost column. We need only search for solutions starting in the topmost four squares of the leftmost column, because any solutions starting in the lower four squares will simply be reflections of those. This follows from the vertical symmetry of the puzzle.
If we visit all the permissible ending squares (the squares in the rightmost column) before we complete the tour, then this path cannot yield a valid solution so we backtrack.
Number of unvisited squares reachable from each square
While we build the path, for each square we keep track of the number of other unvisited squares which are a knight's move away. Before making each move, we check the following conditions to see if it's worth continuing.
If we reach a position where any square has zero unvisited knight-adjacent squares and we can't visit that square on the next move, we know we can't complete the tour from this position so there's no point continuing this path.
Similarly, if the number of squares which have only one unvisited knight-adjacent square is greater than 1 (greater than 2 if we're visiting such a square on the next move) then we can't complete the tour, because we can't possibly visit all such squares without passing through another square twice.
If any square we can move to, other than a permissible ending square, has only one unvisited knight-adjacent square, we must visit it next. If we don't, then either we will never visit it, or when we do visit it we won't be able to move anywhere else afterwards. If this rule requires us to visit multiple squares "next", this is obviously impossible so we backtrack.
Each half-row and half-column sums to 130
In each 4x4 quadrant, the numbers in each row and column must sum to 130. This means there are 32 "lines" of four squares whose contents must sum to that total: four across and four down in each of the board's four 4x4 quadrants. We use this requirement to narrow down the search further.
Every square is on exactly two such lines: one horizontal and one vertical.
We keep track of the running total in each of these lines while we build a path, and the number of squares filled in each line.
- If the knight moves to a square which completes a line, we check that the new sum on that line equals 130. If not, we can't move here and we backtrack.
- If the knight moves to a square and the number filled in is the
third on a line, leaving one more space, we work out the number
that must go in that space (130 minus the line's current sum).
If that number isn't a valid step number (i.e. not between 1
and 64) or it's already been placed, we backtrack. Otherwise,
we pencil that number in to that square as a note to ourselves
when we get deeper into this path.
- If this causes the other line which shares this square to have an invalid sum, we backtrack.
- Otherwise, later on, when it's time to make the step corresponding to this number we pencilled in, we must step to that square. If that isn't a legal move then we backtrack.
- Finally, when we backtrack the move that pencilled in this number, we unpencil it.
- If a move leaves a line with exactly two empty squares, the sum of the two numbers already on that line must be between 8 and 122 inclusive or we know this path cannot yield a valid solution. The proof of this is in the source code, and it relies on the requirement that step 1 and step 64 are on opposite sides of the board.
What if the tours could start and end anywhere?
We could try relaxing the requirement that the knight's path must start and end on opposite sides of the board. This wasn't explicitly stated in the original puzzle, after all.
If we remove this requirement, the program takes considerably longer to run (around five times as long as on the original problem above), because we are now deprived of the assumptions on which many of its optimisations are made. For example, we can no longer assume that two numbers on the same line of four must sum to between 8 and 122. It must also check all the starting squares in one half of one quadrant and on its leading diagonal, rather than only the top four squares of the leftmost column.
It turns out that removing this requirement yields no new solutions.
With these modified requirements, the program does produce a total of 12 tours, but four of these are the four solutions which start in the top-left corner, reflected across the top-left-to-bottom-right diagonal. Ignoring all rotations and reflections, the total number of solutions is still eight.