The Knight of Hamilton

Preface: A game and its rules

Don't tell my dad I gamble for money

Chapter 1: An impatient knight

A long time ago, in the old country of Hamilton, we find a brave young man riding a horse. Conflicted between the thrill of becoming an independent man and the distress of being sent away by his family, he confidently traverses the various terrains towards the royal palace.

As the sun went down, our protagonist decided to take shelter in a small cabin. Although the cabin was made of simple wooden logs, the ingenious structure suggested an owner that is smarter than most of its kind. The entrance was a small space between two life size, wooden statues of a king and queen as found on a chessboard. Inside, the floor was made of black and white tiles. One of the walls had a poem on it: If shadow and light is a line you do not believe in, add up down to left right and see if it is even.

As part of the payment for the overnight stay, the knight promised the isolated cabin owner to humor him with his life story. Next to the fireplace, accompanied by a pot of strong black coffee, the knight began: "As all boys in my family I am to leave my home at the age of 18, not to return until I have made my own fortune. This is the fate that my father and his fathers before him have suffered and been molded by." "And how will you, suffering young man, make your fortune?" the cabin owner asked. The knight proudly raised his chin and announced: "I will challenge the prince to a Knight's Tour. It is widely known that the winner is greatly rewarded." The cabin owner made a concerned face and asked: "Does the prize constitute an object on the first cell of chessboard, double on the second and so forth?" Slightly rattled by the very specific question the knight refuted that price would be a constant sum of money.

As the conversation progresses the knight became more and more insecure. It was only now, when forced to formulate his ideas into words and sentences that he realized how unprepared he was. The cabin owner noticed his realization, took pity in his situation, and decided to help him. "Long ago, I was a student of pure mathematics and worked on the Knight's Tour problem for very long." He compassionately hands the knight a document.. "It is very technical so please take your time to study it carefully."

But the words of the cabin owner would fall on deaf ears as the knight quickly browsed through all the pages. Back in his room, under the light of a dying candle, he read the following fact: for an 8x8 chessboard there are 26,534,728,821,064 ways to complete a tour. "What an incomprehensible gargantuan number!" the knight thought to himself. "I will go to the prince and challenge him, with so many solutions it is only a matter of chance until my guess beats his, skill does not defeat probability!"

The cabin owner found himself being not at all surprised as he stumbled upon an empty bed that morning. The same bed the knight, contrary to most other days, was not thinking about as he galloped his horse onto the palace grounds. He tied his horse to the pole next to a small fountain; the animal gratefully indulged. At the main gate a bishop was reading a small bible in the shade. The knight politely asked him where he may find the Prince of Hamilton. "God does not play dice, and man should not either." the bishop answered disapprovingly, as he pointed diagonally towards the field next to the royal garden.

The prince was lying on his back, looking at the clouds. His head swiftly lifted up as he heard the knight's footsteps approaching. Both of them knew why they were there.

Our Knight would later vividly recall the humiliating situation that took place in the garden. He and the prince started on opposite corners of a 6x6 chessboard, a board size normally reserved for children. Regardless, our knight simply hopped in any random direction, constantly finding himself stuck on a cell without having visited all of them. In his distress he did not notice that the prince, somewhat similarly, is not completing the tour without stopping sometimes, but he then retraces a few steps before proceeding instead of starting all over again. With tears of shame and anger burning behind his eyes, the knight returned to the cabin.

import random

def tryRandom() -> int:
    w=6
    h=6
    # Create an empty board
    board = [0] * (w * h)
    (px, py) = (0,0)
    move_count = 0
    while True:
        move_count += 1
        board[px + w * py] = move_count
        # Filter moves that do not exit
        # the board and go to a non visited cell 
        validMoves = []
        for (dx, dy) in getMoves():
            nx = px + dx
            ny = py + dy
            if nx >= 0 and \
               nx <  w and \
               ny >= 0 and \ 
               ny <  h and \
               board[nx + w * ny] == 0:
                validMoves.append((nx, ny))

        # No more valid moves, stop
        if len(validMoves) == 0:
            return move_count

        # Do one of the possible moves at random
        (px, py) = random.choice(validMoves)

def getMoves():
    return [(2, 1), (2, -1), (-2, 1), (-2, -1),
            (1, 2), (1, -2), (-1, 2), (-1, -2)]

full source

Chapter 2: We must go deeper

The cabin owner, although truly feeling compassion towards the knight, also felt content with knowing the knight would be around for a while. The next day he took the knight out for a walk in the nearby forest. He pointed at the trees and with a soft voice started to describe how the each branch itself looks like a three, albeit smaller. Symptomatic of overcoming his latest brush with defeat, the knight started to climb up in one of the trees. Although not fully realizing the meaning behind the cabin owner's words, he appreciated the insight and felt it ought to be meaningful someday.

That evening, the cabin owner showed the knight a different puzzle, a maze to be precise. "Neither my mind nor my writing hand has the endurance to work out such a large maze!" the knight screamed. With a grin the cabin owner answered: "Good, now that we have established that, we can think of a way to do this better." The cabin owner reached in a cabinet and took out a robust laptop with a mechanical keyboard. "Perhaps we can just focus on a way to think about how to solve it and leave the actual calculations to the computer," the cabin owner proposed.

After hours of puzzling the knight was now completely familiar with the concept of 'Depth First Search'. "It is just like the trees in the forest!" the knight yelled euphorically. Inside the knights head the cogs started turning.. "Well if you have a chessboard, each cell marked with the order of visiting it, or a 0 if it has never been visited, than we can consider each possible move a sub tree of that 'node'! My fortune must be somewhere at the top of the three, like a golden leaf! The prince did not say anything about using computers, I can simply program this out and let the computer find the solution!"

def printBoard(board, w, h):
    for y in range(h):
        for x in range(w):
            print(f"{board[x + w * y]}\t", end='')
        print()


def isValid(board, w, h, pos):
    (x, y) = pos
    return x >= 0 and \
           x <  w and \
           y >= 0 and \
           y <  h and \
           board[x + w * y] == 0

def getMoves():
    return [(2, 1), (2, -1), (-2, 1), (-2, -1),
            (1, 2), (1, -2), (-1, 2), (-1, -2)]


def getSuccessors(board, w, h, pos, count):
    (px, py) = pos
    for (dx, dy) in getMoves():
        nx = px + dx
        ny = py + dy
        if isValid(board, w, h, (nx, ny)):
            new_board = board.copy()
            new_board[nx + w * ny] = count+1
            yield (new_board, (nx, ny), count+1)

def findSolution(w, h, show=True):
    init_board = [0] * (w*h)
    init_board[0] = 1
    stack = [(init_board, (0,0), 1)]
    while len(stack) > 0:
        (board, pos, count) = stack.pop()
        # Check if the tour has been completed
        if count == w*h:
            if show:
                printBoard(board, w, h)
            return
        # Add all possible successors 
        # to the top of the stack
        for succ in getSuccessors(board, w, h, pos, count):
            stack.append(succ)
    print("Solution does not exist")

6x6 solution:
1    12    31    34    19    36
30   5     18    11    28    33
13   2     29    32    35    20
6    23    4     17    10    27
3    14    25    8     21    16
24   7     22    15    26    9

Without damaging his ego the knight was now able to see that victory was not yet in sight. The cabin owner had taught him to call the devil by his name 'exponential complexity'. Not only did he remember that the prince was able to solve the 6 by 6 board much faster than 39 seconds, he also knew that the 6 by 6 board was merely a warm up. However, following the exponential curve it would seem that solving the tour on boards larger than that would take minutes and quickly hours or days. As the sun set completely, the golden glow that seemed to radiate from the leaves, fades leaving a colorless soon to be compost.

Chapter 3: Taking a step back

At a loss for thinking of a better algorithm, the knight focused on optimizing the current one. He noticed how having to copy every board state to generate a successor was a non trivial operation compared to the rest. Furthermore, having to hold the stack in memory did feel a little redundant.

Deep in the cellar of the cabin, a place filled with books and dust, the knight found a document on Backtracking. At first glance it appeared to be analogous to depth first search, but there were some benefits. First of all, there was no need to pop and push to a stack^(*1). Secondly, no copy of the board was needed, at every level of recursion the same board could be mutated in place.

The knight spent the rest of the week sweating away implementing the Knight's Tour solver using a backtracking approach. When it was finally ready, he couldn't wait to try out his new solution and ran it for a 6x6 board: 5.36 seconds! His heart started racing and a feeling of euphoria as he remembered the prince having to think a bit more than 5.36 seconds. Just to make sure he also plugged in 7x7: 0.34 seconds! Phenomenal! "If the devil is exponential, then god must be inverse exponential," the knight triumphantly thought to himself.

His memory seemed to have served him correctly. The prince gave a small bow as he managed to beat him on the 6x6. "My congratulations my good man, but you know that to win the fortune you must beat me on not only 6x6 board, several larger ones as well," said the prince. The knight confidently followed the prince to another part of the garden where a 6x7 board was located. "Let's take it one step further," said the prince invitingly. With the memory of the incredible speed in which he was able to solve a 7x7 he was already daydreaming of the surprised look the prince will have after beating him.

Frustratingly, the truth could not be further removed from his dreams, as even after 10 minutes, when the prince had long completed his tour, the knight was still backtracking. Feeling more flabbergasted than sad, he congratulated the prince and took of again to the old familiar cabin.

def printBoard(board, w, h):
    for y in range(h):
        for x in range(w):
            print(f"{board[x + w * y]}\t", end='')
        print()


def isValid(board, w, h, pos):
    (x, y) = pos
    return x >= 0 and \
           x <  w and \
           y >= 0 and \
           y <  h and \
           board[x + w * y] == 0 \

def getMoves():
    return [(2, 1), (2, -1), (-2, 1), (-2, -1),
            (1, 2), (1, -2), (-1, 2), (-1, -2)]

def backtrack(board, w, h, x, y, move_c, show=True):
    if move_c == w * h:
        if show:
            printBoard(board, w, h)
        return True
    
    for (dx, dy) in getMoves():
        nx = x + dx;
        ny = y + dy;
        if not isValid(board, w, h, (nx, ny)):
            continue
        move_c += 1
        board[nx + w * ny] = move_c
        if backtrack(board, w, h, nx, ny, move_c, show):
            return True
        move_c-=1
        board[nx + w * ny] = 0

    return False

def findSolution(w, h, show=True):
    board = [0] * (w*h)
    board[0] = 1
    backtrack(board, w, h, 0, 0, 1, show)

Chapter 4: Depression, Despair, and Death

The knight was unable to hold back a few tears as he attended the funeral of the cabin owner. He was the only soul there, a fact only contributing to the tragedy. It had taken the knight multiple days to carve out the text in the gravestone. He found it only appropriate to make the cabin owner's most famous words were to ring into eternity:

"If a work of fiction burns in a fire then the story dies with its writer. If a work of science burns in a fire, only the name of the author changes."

The knight's soft sobbing changed to laughter because he only just now realised the irony of feeling resentment towards the cabin owner for not ever revealing the solution of that cursed cursed game.

Chapter 5: Sciens ex machina

His head was covered in sweat. The sheets were largely on the ground. The knight was heaving a nightmare^(*2). "No more ideas, oh brave knight," said the demon mockingly with a deep voice. "Your parents must be celebrating, they knew you would never be smart enough to make a fortune." The knight was paralyzed, it felt like the gravity dial was turned way up. Then something grabbed him by the hand and flew with him in the air.

After an incomprehensible flight path, he was gracefully laid down in a soft green patch of grass. The creature that had brought him there landed next to him. "What were you thinking, wandering so far from the human world," the creature began. "Have your parents never told you to first look for answers close by? If you run all the way around the world you might not find the gold buried in your backyard. It's all about heuristics really..."

The knight woke up feeling like his head was hit with a brick. That feeling would persist until well after sunset when it suddenly started to retreat. Like ebb and flow the headache replaced itself with an unprecedented clarity and one word from all the books in the cabin's cellar echoed in his skull: "Warndorff, Warndorff, Warndorff..."

In the weeks following the cabin owner's death, the knight had spent most of his time on taking care of the cabin and rarely thought of the Knight's Tour. When he did try to gain more knowledge by scrolling through the old books, he was often distracted by his persisting grief. Yet that evening, having reflected all day on his dream it all seemed to come together. Every word he read but forget came surging back into his conciousness. "Warndorff.. Warndorff.. Warndorff's method!," his memory screamed. It was all so clear now. Backtracking is not that bad of an idea at all but it matters which path you choose. That's why the results varied so much, sometimes he was just lucky choosing the right move. Backtracking is of course based on the fact that you do not know the correct path upfront but that doesn't mean that you cannot make an educated guess. It's like the winged creature from his dream suggested, if go far from home to find adventure you will miss the small adventures close by forever. Just like the cells on the chessboard, if you do not visit the cells that are almost boxed in you may never see them again! You first got to choose the nearly closed doors before exploring new ones. That's the heuristic! Choose a move that has the least follow up moves first!

import sys
# Allow for more recursion
sys.setrecursionlimit(100000)

def printBoard(board, w, h):
    for y in range(h):
        for x in range(w):
            print(f"{board[x + w * y]}\t", end='')
        print()


def isValid(board, w, h, pos):
    (x, y) = pos
    return x >= 0 and \
           x <  w and \
           y >= 0 and \
           y <  h and \
           board[x + w * y] == 0 \

def getMoves():
    return [(2, 1), (2, -1), (-2, 1), (-2, -1),
            (1, 2), (1, -2), (-1, 2), (-1, -2)]


def countMoves(board, w, h, x, y):
    "Count the number of valid moves from a given position"
    count=0
    for (dx, dy) in getMoves():
        if isValid(board, w, h, (x+dx, y+dy)):
            count += 1
    return count

def getMovesHeuristic(board, w, h, x, y):
    """
    Note that to calculate the heuristic, we already need
    to find the new absolute position, so be might as 
    well give that back instead of doing it again later.
    """
    choices = []
    # Determine all valid moves add annotate them
    # with the heuristic, i.e. the number of follow
    # up moves.
    for (dx, dy) in getMoves():
        nx = x + dx
        ny = y + dy
        if isValid(board, w, h, (nx, ny)):
            choices.append(
                ((nx, ny), countMoves(board, w, h, nx, ny)))
    # sort the position by their heuristic
    choices.sort(key=lambda x: x[1])
    # strip the heuristic and the return
    # the result
    return [m for (m, _) in choices]

def backtrack(board, w, h, x, y, move_c, show=True):
    if move_c == w * h:
        if show:
            printBoard(board, w, h)
        return True
    
    for (nx, ny) in getMovesHeuristic(board, w, h, x, y):
        # No need to check the move, the heuristic
        # function has already done that for us.
        move_c += 1
        board[nx + w * ny] = move_c
        if backtrack(board, w, h, nx, ny, move_c, show):
            return True
        move_c-=1
        board[nx + w * ny] = 0

    return False

def findSolution(w, h, show=True):
    board = [0] * (w*h)
    board[0] = 1
    if not backtrack(board, w, h, 0, 0, 1, show):
        print("No solution")

Epilogue

Notes

The full source, including benchmarking can be found over on Github