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.
