Making Knight's Tour Part 4 of 4

 Part 4 of 4: Hamiltonian paths and circuits

When it comes to math, I do wish that I had done more math courses. I do not consider myself a math expert, though I use it all the time and feel it is important to at least understand the concepts. When it comes to Knight’s Tour, graph theory is the mathematical topic of choice for understanding what is going on. A graph is simply a set of vertices (often called nodes by programmers) connected by edges. The game can be represented as a graph with each tile of the board being a vertex and the paths that the knight can take being the edges. The image below shows this.

When travelling through the nodes, the sequence of vertices visited is a walk. If the vertices of the walk are all distinct then you have a path. There is a special path which is made up of all vertices in the graph known as a Hamiltonian path. When you think about it, any solution to the game is a Hamiltonian path.

There is another concept in graph theory called a circuit. The idea here is that you have a path but the last vertex of the path connects to the first vertex of the path to form a cycle. Taken to the extreme, if the circuit visits every vertex once (except the starting vertex) then you have a Hamiltonian circuit. In Knight’s Tour, if the last node in a solution is an L move away from the starting location, then you have a Hamiltonian Circuit. This is a very special solution to the puzzle as you have effectively found two solutions for each tile (going in either direction is fine). Finding a Hamiltonian Circuit is not difficult as you only need to add a constraint to the solver such that it can only take the L leading to the starting location if it is the last move. This will take a very long time as there are many valid solutions that will fail. Once you have found a Hamiltonian circuit, however, creating a solver that will use it is trivial.

Once you know the path, you can simply store that as an array of next tiles.

"hamiltonian": [10,11, 8,18,19,20,12,22,

                25, 3, 4, 5, 2, 7,31,21,

                 1, 0,28,29,14, 6,39,13,

                 9,40,43,42,34,35,15,46,

                17,16,44,45,26,47,23,54,

                57,24,36,37,27,30,63,62,

                33,32,56,61,58,59,60,38,

                41,51,48,49,50,55,52,53]

The solver can then simply look up the next move in the circuit.

class KTHamiltonianSolver extends KTSolver {

    constructor(game) {

        super(game);

    }



    reset() {

        this.game.restartGame();

    }



    nextMove() {

        let curTile = this.game.lastKnightTile;

        let target = KT.hamiltonian[curTile];

        this.game.addKnight(target);

    }



}

This may seem like cheating, and it sort of is, but using a precalculated solution is actually particularly useful for solving larger puzzles. Larger puzzles can be broken down into several smaller puzzles. If you have solutions that start at one edge and another edge, you can chain the puzzles together to solve larger puzzles without incurring the exponential growth that trying to solve the complete puzzle would incur. This is known as divide and conquer.

So, how do the different solvers compare? The table below shows how all four solvers did for each of the possible starting locations. Note that I only went to 10 billion steps. I also used a C++ version of the solvers so they ran much faster.