Making Knight's Tour part 2 of 4

 Part 2 of 4: Backtracking and forward checking

For Queen’s challenge, we started with a brute force approach and worked up to forward checking. For solving Knight’s Tour, we will start with a backtrack solver. our solver four nights tour is very similar to the one that we used for Queen's challenge. The solver class takes the main game class as its parameter which is used to help verify the game state and make moves on the board. There are two methods in the solver class with the first one being the reset method. This method simply loops through all the tiles in the board and sets the current step to 0. the step represents which of the eight moves that the knight has made.

reset() {

    for (let i = 0; i < 64; ++i) {

        this.game.tiles[i].step = 0;

    }

}

 

The next move method is used by the game to perform the next step of the solution search. Here we are using the last tile that the knight was in and using the step value to figure out which directions we have already attempted. If all of the possible steps have been tried and none of them were successful, we know that we have to backtrack which is done by resetting the step to 0 and then calling the undoMove method in the game. If the next step to take is a valid step as determined by calling the checking routines we developed in the previous part, we take that step by calling the game’s addKnight method. Finally, if the next step was not a valid step, and we never backtracked,  we continue on to the next step by returning a recursive call to this method. This could have been also implemented as a while loop surrounding the entire method, but I find this way less complicated with the same results.

nextMove() {

    let madeMove = false;

    let curTile = this.game.lastKnightTile;

    let step = this.game.tiles[curTile].step;

    if (step >= KT.knightTileOffsets.length) {

        step = 0;

        this.game.undoMove();

        madeMove = true;

    } else {

        let target = curTile + KT.knightTileOffsets[step];

        ++step;

        if ((target >= 0) && (target < 64)) {

            if (this.game.tiles[target].isTileAPotentialMove()) {

                this.game.addKnight(target);

                madeMove = true;

            }

        }

    }

    this.game.tiles[curTile].step = step;

    if ( ! madeMove)

        return this.nextMove();

}

 

Within the code the startSolver method simply is passed the instance of the solver that is to be used and sets it as the solver. The reset for the solver is called and we set a timeout to call our NextSolverStep method to start solving the game.

startSolver(solver) {

    this.solver = solver;

    solver.reset();

    setTimeout(this.nextSolverStep.bind(this), 10);

    this.solverMoves = 0;

}

The nextSolverStep is designed to be called periodically and only performing a single solver step per iteration so that we can have a nicely animated solution. To allow for a fast mode, the number of times that we call the solver’s nextMove method will be dependent on a solvCount variable who’s value will be either 1 or 1000 toggled by pressing the Fast/Normal button. The number of steps that have been tried is updated and displayed to the user so they have some idea of how fast a particular method is.

nextSolverStep() {

    if (this.solver == null)

        return;

    for (let i = 0; i < this.solveCount; ++i) {

        if (this.knightCount < 63) {

            this.solver.nextMove();

            ++this.solverMoves;

        }

    }

    this.moveCountText.setText("" + this.solverMoves);

    if (this.knightCount < 63)

        setTimeout(this.nextSolverStep.bind(this), 25); 

    draw();

}

 

The fact that I added a fast button is probably a good indicator that the backtrack solver’s performance was not what we were hoping for with it taking 6484065 for the corner tile and many of the tiles taking over 10-billion attempts. The problem is that if an invalid move is made, it can take quite a while to finally backtrack to the move that is causing all the problems. We know from Queen’s Challenge that forward checking can solve that problem so that is what we are going to do next.

The forward checking implementation takes advantage of our isGameStillWinnable method to verify that a move is feasible. This is not the proper way to implement this as the routine is very slow but as we are animating the game so there will be no noticeable difference we can get away with our brute force method. This lets us have a very simple class.

class KTForwardSolver extends KTSolver {

    constructor(game) {

        super(game);

    }



    nextMove() {

        if (this.game.isGameStillWinnable())

            return super.nextMove();

        console.log("Unsolvable so early backtrack");

        this.game.tiles[this.game.lastKnightTile].step = 0;

        this.game.undoMove();

    }



}

 

So, what is wrong with the way I am doing the winnable check? It is very costly to do as you are doing  up to 64*8 checks to see if the board is still in a winning state.  So what would be a better way of doing this? Attach a domain array to each tile which holds which possible moves are still available. Whenever a move is made, remove the appropriate moves from the 8 affected tiles. If any of those tiles no longer have a potential move, then you know you are in an unwinnable state and can backtrack. I am leaving the implementation of this as an exercise for my readers.

Forward checking definitely helped the performance as the top left tile now only took 1731697 and there were fewer (though still a significant number) of tiles that required over 10 billion steps to solve. The problem is that we are making a bad decision early and it costs us much later in the solution, so it takes a long time to backtrack. If only we had a way to make better choices. This will be looked at next time.