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]
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);
}
}
