The Knight Errant Puzzle

Introduction

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).

Page 48 of The Ultimate Book of Number Puzzles, which describes the Knight Errant puzzle.

Page 49 of The Ultimate Book of Number Puzzles, which describes the Knight Errant puzzle and gives one partial solution.

The problem

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.

Given solutions

Here are the four solutions presented in the book.

47	2	49	32	15	34	17	64
30	51	46	3	62	19	14	35
1	48	31	50	33	16	63	18
52	29	4	45	20	61	36	13
43	6	53	28	37	12	59	22
54	27	44	5	60	21	38	11
7	42	25	56	9	40	23	58
26	55	8	41	24	57	10	39

Solution #1

1	48	31	50	33	16	63	18
30	51	46	3	62	19	14	35
47	2	49	32	15	34	17	64
52	29	4	45	20	61	36	13
43	6	53	28	37	12	59	22
54	27	44	5	60	21	38	11
7	42	25	56	9	40	23	58
26	55	8	41	24	57	10	39

Solution #2

47	2	49	32	15	34	17	64
30	51	46	3	62	19	14	35
1	48	31	50	33	16	63	18
52	29	4	45	20	61	36	13
5	44	25	56	9	40	21	60
28	53	8	41	24	57	12	37
43	6	55	26	39	10	59	22
54	27	42	7	58	23	38	11

Solution #3

1	48	31	50	33	16	63	18
30	51	46	3	62	19	14	35
47	2	49	32	15	34	17	64
52	29	4	45	20	61	36	13
5	44	25	56	9	40	21	60
28	53	8	41	24	57	12	37
43	6	55	26	39	10	59	22
54	27	42	7	58	23	38	11

Solution #4

Algorithm overview

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.

Starting square

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.

Ending square

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.

1
		2

	3
			4
	5

From step 5, we must visit the bottom-left corner square next, or we'll never be able to visit it again and leave.

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.

		49
		46
1	48	31	50
		4
				22
54	27	44	5	11
				58
				39

Within each 4x4 quadrant, the numbers in each row and each column must sum to 130.

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.

•
•	•
•	•	•
•	•	•	•

We must check for tours starting from at least these squares if we are to remove the restriction on starting and ending square. Tours starting from other squares will be rotations and/or horizontal, vertical or diagonal reflections of these.

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.