Part 1: A Game of Knights
Knight’s
tour is another chess-puzzle. The idea is that you are given a chess board, not
necessarily 8x8 but for this version we are using the standard chess
board. The player is given a knight at a
random starting location on the board
and using just the valid L-shaped move mechanic of the knight you must move around
the entire board touching each square of the board once without touching a
square that has already been touched. For those, like me, who are not chess
players, the image below shows the knight’s moves.
The game
has been released on Spelchan.com, with the source code being in the BlazingPorts
repository. In this series of articles I am going to just be highlighting key
parts of the game but if you want to look at the code in it’s entirety, it is
available.
While it is
possible to represent a board as a 2-dimensional array, it is also possible to
represent it as a single dimensional array of 64 tiles. This makes tracking the
order of the moves a bit easier and the moves can be represented as an offset that
makes finding the tile indexes easier but does require a sanity check. The board
is simply an array of Knights with the knight class holding the move number (or
-1 if the tile has not yet been stepped on) and the tile index of the previous
tile. While the previous tile reference is not necessary, it makes drawing the path
much easier which is why it ended up being added.
The Knight
class not only holds information for which order it is in but has methods for
helping determine if it is a valid move. The checkIfAllowedMove function
is used to verify that the move that the knight is making is in an L shape.
This can be done easily by taking advantage of the fact that one of the
distances traveled will be one square while the other distance will be 2
squares which means the absolute value of the two numbers will be equal to 3.
checkIfAllowedMove(knight1, knight2) {
let knightXAdjust = Math.abs( (knight1 % 8) - (knight2 % 8) );
let knightYAdjust = Math.abs( Math.floor(knight1 / 8) - Math.floor(knight2 / 8) );
return (knightXAdjust+knightYAdjust) === 3;
}
To check if a move is a potential move we simply need to
make sure that the tile being moved to is empty, and that the target
destination is an L's distance away from the last valid move.
isTileAPotentialMove() {
if (this.moveNumber >=0)
return false;
let knight = this.game.getLastKnightTile();
for (let cntr = 0; cntr < KT.knightTileOffsets.length; ++cntr) {
if ((knight + KT.knightTileOffsets[cntr]) === this.id) {
return this.checkIfAllowedMove(knight, this.id);
}
}
return false;
}
Part of the reason I created this game was to play around
with solving methods, but having the game playable by humans is an important
aspect. One of the biggest issues with this game is that it is easy to get to a
point where you can no longer win the game yet not notice until later in the
game requiring multiple levels of undo. To make this easier on the player I
wanted to have a warning message appear when the game is no longer in a
winnable state. This obviously requires that the computer is able to detect when
the game is not in a winnable state. My method of detecting if a game is solveable
is to simply make sure that every tile on the board either already has a night
on it or is an L shape away from an empty tile. As you can see in the code
below, this is simply a loop over all the tiles on the board with the empty
ones being checked to see if they are an L shape away from another empty tile
or the last move. This is not the most efficient way of doing this has it be
possible to track this information and reduce the amount of calculations that
we have to do but I will discuss that later when I am covering forward
checking. Another problem with this method is that there may be an isolated
patch of tiles that can connect with each other but not the main board but is
good enough for our needs.
isGameStillWinnable() {
if (this.knightCount > 62) return true;
for (let t = 0; t < 64; ++t) {
if (this.tiles[t].moveNumber === KT.NO_MOVE) {
let hasValidMove = false;
for (let k = 0; k < KT.knightTileOffsets.length; ++k) {
let target = t + KT.knightTileOffsets[k];
if ((target >= 0) && (target < 64)) {
if (this.tiles[target].isValidMove(t)) {
hasValidMove = true;
break;
}
if (target === this.lastKnightTile) {
hasValidMove = true;
break;
}
}
}
if ( ! hasValidMove) {
//console.log(`tile ${t} not valid`)
return false;
}
}
}
return true;
}
When I started working on this project the previous move information
was not stored in the knight so to undo a move, I had to resort to doing a back
look up. This is done by simply looking at all the possible moves from the
current night and seeing if any of them have the ID of the previous move.
Another way that this could have been done is simply loop over all the tiles in
the board, but just searching 8 tiles is much quicker.
undoMove() {
if (this.knightCount <= 0)
return;
let previousTile = -1;
for (let i = 0; i < KT.knightTileOffsets.length; ++i) {
let target = this.lastKnightTile + KT.knightTileOffsets[i];
if ((target>=0) && (target<64)) {
if (this.tiles[target].moveNumber === (this.knightCount-1) )
previousTile = target;
}
}
this.tiles[this.lastKnightTile].setMoveNumber(-1, -1);
--this.knightCount;
this.lastKnightTile = previousTile;
}
Now that we
have a basic game, lets see how a computer would solve it. The obvious starting
point is with the backtracking and forward checking algorithms that we used for
solving Queen’s Challenge. Those methods
worked very well with Queen’s Challenge so our work should be over quickly.
It’s strange that this series has four parts instead of just two.
