Heuristics
When you get right down to it, solving the knights tour is simply a search of really large tree. The biggest problem is that if you take a wrong path then you end up wasting a large amount of time before you realize your mistake and come back track back up to where a viable solution can exist. The obvious solution to this is not to make bad mistakes, but how do you determine if a choice is a good choice or not? Human brains partially solve this problem by employing what is known as heuristics. The idea here is instead of doing complicated calculations the brain will look for shortcuts that usually, though not always, lead to the correct solution. With NP problems heuristics can be a very good way of solving the problems in a reasonable amount of time if you can find an appropriate heuristic.
Creating a heuristic is not a simple task. Usually several different techniques are tried to find out if any of them work with smaller versions of the problem set. The technique can then be applied to larger problems to see if they still work. Often we will start by looking at several versions of the problem and seeing if there's any pattern that can be found. The easiest way of finding a heuristic is to look at what other people have discovered and using their heuristic, but that requires an existing heuristic to already exist. Knight's tour is very popular with mathematicians so several heuristics have been devloped.
For Knights tour the Warnsdorff's heuristic is the heuristic that dominates. This is a quite simple heuristic. The idea is that for each potential move you look at the number of moves that tile will have once you have moved there and selecting the tile that has the least moves available. As you can see by the figure below, each of the tiles that we can move to has a certain number of moves attached to it, but there is also a tie. There are several approaches that can be taken for dealing with ties, so I went with a clockwise order of searching tiles and taking the clock position as the tie-breaker.
One of the things that continually came up when researching this heuristic was that when there was a tie that would quite often be where the problem with the solution was. This would mean that tide tiles would be a good candidate for a faster backtracking method. For this reason I updated the reset function to also include an indication of whether there was a tie at particular decision tree node.
reset() { for (let i = 0; i < 64; ++i) { this.game.tiles[i].step = 0;
this.game.tiles[i].tiebreaker = false; } }
countTargetMoves(target, source) {
if ((target < 0) || (target >= 64)) return -1; // NOTE invalid is -1 not zero as last move will be 0 moves!!!
if ( ! this.game.tiles[target].checkIfAllowedMove(target, source) ) return -1;
if (this.game.tiles[target].moveNumber !== KT.NO_MOVE) return -1;
let moveCount = 0; for (let t = 0; t < KT.knightTileOffsets.length; ++t) { let knight = target + KT.knightTileOffsets[t]; if ((knight === source) || (knight < 0) || (knight >= 64)) continue;
let knightXAdjust = Math.abs( (knight % 8) - (target % 8) );
let knightYAdjust = Math.abs( Math.floor(knight / 8) - Math.floor(target / 8) ); if ( ((knightXAdjust+knightYAdjust) === 3) &&
(this.game.tiles[knight].moveNumber === KT.NO_MOVE) )
++moveCount; } return moveCount }
fastBacktrack() {
let curTileIndex = this.game.lastKnightTile;
if (curTileIndex === this.game.firstKnightTile) return;
let curTile = this.game.tiles[curTileIndex];
this.game.undoMove();
curTile.step = 0;
curTile.tiebreaker = false;
if ( ! this.game.tiles[this.game.lastKnightTile].tiebreaker) this.fastBacktrack();
}
The next move method seems a lot more complicated than it
really is. The big problem that we have is that step is no longer linear as
steps may be taken in totally different orders. To get around this problem, we
are treating each bit of the step variable as one of the paths that we can
take. If the bit is set then we know that path is either not available or has
been tried already. To loop over the bits, we simply create a mask variable
which we set to 1 to indicate the first bit. The left shift operator, which is
represented using <<, is used to shift that one to the appropriate bit position.
If the value of step is 255 then we know that all these steps have been tried
and can do a backtrack. If moves are still available we simply loop over all
the bits and find the lowest count from the moves that are remaining. The
lowest move is then the move that we make. As it is simple enough to also do
forward checking, we will call the is game still winnable method to do a
forward checking step even though this is not required as part of the
heuristic.
nextMove() {
let curTile = this.game.lastKnightTile;
let step = this.game.tiles[curTile].step;
let tiebreaker = this.game.tiles[curTile].tiebreaker;
if (step === 255) {
// this.game.undoMove();
// step = 0;
return this.fastBacktrack();
} else {
let mask = 1;
let index = 0;
let lowest = -1;
let lowestCount = 9;
let lowestMask = 0;
while (mask < 256) {
if ((step & mask) === 0) {
let target = curTile + KT.knightTileOffsets[index];
let targetMoves = this.countTargetMoves(target, curTile);
// console.log(`target
${target} has ${targetMoves}`);
if (targetMoves < 0)
step |= mask;
else if (targetMoves < lowestCount) {
lowest = target;
lowestCount = targetMoves;
lowestMask = mask;
} else if (targetMoves === lowestCount) {
tiebreaker = true;
}
}
mask <<= 1;
++index;
}
if (lowestMask > 0) {
step |= lowestMask;
this.game.addKnight(lowest);
if ( ! this.game.isGameStillWinnable() ) {
this.game.undoMove();
// console.log("Early
backtracking!");
}
} else
console.log("No move found???")
}
this.game.tiles[curTile].step = step;
this.game.tiles[curTile].tiebreaker = tiebreaker;
}
Running with this Heuristic proved to be very efficient. as
it turns out, the heuristic solver is able to find the solution in 63 steps for
all of the possible starting locations. With the performance we are getting using this heuristic we are
done, so why is there another solver in the game? My exploration of Knight’s Tour
would not be complete without looking at circuits and larger boards.
