Making Knight’s Tour part 1 of 4

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.