Part 5 – Backtrack Solver
While a
smarter brute force method had a drastic effect on the performance of our
solver, we were still trying out a huge number of combinations that were
clearly not going to work. If only there was some way to eliminate the bulk of these
clearly invalid moves. There is an approach called backtrack solving, which
attempts to prune as many searches as possible. This is often depicted as a
tree, so lets represent our first few rows as a tree.
As you can
see, for each of the moves in the first row of the board, each piece of the
second row has 8 moves it can make. For each combination of the first and
second piece, there is an additional 8 moves for that combination, and so on.
If, however, the first row and the second row are in conflict, then all the
moves underneath the second row position are also in conflict so the entire
branch underneath that move can be eliminated. This leads to a very simple
process. For whatever row we are working on, lets call it depth as that is the
generic term for a tree search, we try the first available position. If that
position is not in conflict with any other queens, we go to the next row
otherwise we go to the next position. If for a given row there is no valid
position, we backtrack by going to the previous row and moving it to the next
position. Repeat until all pieces are placed on the board or there are no more
possible moves to try (no solution to the problem).
Implementation
of a backtrack solver is not that much more difficult than brute-force methods but
does require some slight modifications to how the solver works. Instead of
placing all the pieces on the board, we only place the locked piece and a queen
for each of the rows we have processed. We will use the term depth to represent
how many of our pieces we have placed. As I am a programmer, the count will
start at 0.
class BacktrackSolver extends BaseSolver {
constructor(game) {
super(game);
this.depth = 0;
}
We can
change how pieces are placed on the board by overriding the placeStepOnBoard
method and making all the pieces beyond our current depth invisible. Some minor
changes to reflect this change were made to the isBoardSolved method but I
won’t go over the details here.
placeStepOnBoard() {
super.placeStepOnBoard();
for (let i = this.depth+1; i < 7; ++i)
this.game.queens[i+1].setVisible(false);
}
The reset
method is very simple as we just need to set the depth to 0 and start our first
queen off on either the first row or second row if the first row is occupied by
the locked queen.
reset() {
this.locked = this.game.queens[0].y * 8 + this.game.queens[0].x;
let lockedRow = this.game.queens[0].y;
if (lockedRow === 0)
this.moveable[0] = 8;
else
this.moveable[0] = 0;
this.depth = 0;
this.placeStepOnBoard();
}
Because we
need to check if a queen is in conflict with another queen, we will take
advantage of the game logic we already have within the game instead of
re-writing the logic. This can be a bit confusing as the locked queen is
queens[0] while our queens are 1 through seven but you only need to add 1 to the
current depth to find the queen we are working with. We first check to see if
the queen we are looking at is in a valid position assuming it is not valid if
we are backtracking. If the board is in a valid state then we start the next
depth by placing the next queen in the starting column of it’s row, skipping
over the locked row when necessary and we have finished our move. If the board
is not in a valid position, then we stay at the same depth moving our queen to
the next column of the row. If the queen is able to be moved, we are done. On
the other hand, if the queen is at the end of the row, we need to backtrack so
we reduce our depth and repeat the above.
nextMove() {
let moved = false;
let backtrack = false;
while ( ! moved) {
let queen = this.game.queens[this.depth+1];
queen.setVisible(false);
if ((!backtrack) && (this.game.canEnterTile(queen.x, queen.y))) {
// spawn next depth
++this.depth;
let lockedRow = this.game.queens[0].y;
this.moveable[this.depth] = (queen.y+1) * 8;
if ((queen.y+1) === lockedRow)
this.moveable[this.depth] += 8;
moved = true;
} else {
if (queen.x < 7) {
this.moveable[this.depth] += 1;
moved = true;
} else {
backtrack = true;
--this.depth;
}
}
}
}
}
Running the
solver will usually result in a solution in under a minute, which is really
good when you consider that we are only doing 10 steps per second. So,
mathematically speaking, how long should this take? Best case would be 7 steps.
The theoretical worst case is 8^7 for 2,097,152 which happens to be the same as
the brute-force lines method. For this particular problem, we know that we will
be pruning a lot of branches so our results will be significantly better than
worst case, but calculating this is not a trivial matter so will leave the
calculations to the more mathematically inclined.
Can we
improve things further? Watching the results, you will notice that many of the
boards checked are positions that are obviously bad based on the above pieces.
If only there was a way of just checking potentially valid tiles. We will call
this forward checking and look at it next time.
