Part 6: Forward Checking
Backtracking drastically improved our search for a solution but there was the issue that we would still place queens in positions where they were obviously in conflict. This issue can be removed by simply using the concept of domains. The idea here is that every queen has a domain made up of the tiles that they can occupy. When you place a queen on the board you examine the domains of the queens not yet placed and remove the invalid locations from those domains. Queens are then placed only in tiles still within their domain. The figure below shows the domains for the current step.
This has
two important advantages over backtracking. First, you are only checking tiles
that are not in conflict with another queen. Second, if a domain for one of the
future queens becomes empty then you know immediately that the current solution
is not valid and can backtrack.
This does
add a bit of complexity as when you backtrack, you need to add back into the
other queen’s domains the moves that you had marked as invalid. An easy way to
do this, which is the method I will be using for this animation, is to simply have
an array for the domain with values indicating when a location has been removed
from that domain. This is an inefficient way of doing things. A faster way
would be to use bit fields to represent valid moves with the bit-fields pushed
onto a stack every domain and pulled from the stack to backtrack. Bit
manipulation tends to be hard to read code, so as speed is not a concern due to
large delays between frames, I’ll stick with the easier to understand method.
There is a
lot involved in the implementation with the first thing done when I was writing
this was to display the domains while slowing down the animation speed to allow
for easy visualization on what was happening. When domain adjustments were
working, I got the game working up to the backtrack step. Finally I implemented
the backtracking and was surprised when everything just worked!
The setup
for this class was a bit more complicated than the other solvers as we need to
create a two-dimensional array to track our domain. We are using -1 to indicate
a domain location that is valid, with the depth that a location became invalid for
inaccessible tiles.
class ForwardSolver extends BaseSolver {
constructor(game) {
super(game);
this.depth = 0;
this.domains = [];
for (let y = 0; y < 8; ++y) {
let row = [];
for (let x = 0; x < 8; ++x) {
row.push(-1);
}
this.domains.push(row);
}
}
As with the
backtrack solver, we will need to adjust the placeStepOnBoard method. This is
identical to the backtrack solver so we copy that code. Could have inherited from
BacktrackSolver to remove duplicate code but it is just three lines and the
rest of the class is quite different from the backtrack solver.
placeStepOnBoard() {
super.placeStepOnBoard();
for (let i = this.depth; i < 7; ++i)
this.game.queens[i+1].setVisible(false);
}
Resetting
the solver is simply a matter of setting all the domain variables back to the valid
value of -1. Next we need to place the starting queen on the board. This is a
bit tricky as the locked queen doesn’t really have a depth so we will use a
depth of -1 to represent this initialization phase. This is a bit of a kludge
but makes the logic of the rest of the solver routines easier to write. The
updateDomains method is used to set the domains up with the conflicts caused by
the locked queen removed from the other pieces domains. This method will be
explained below. Once the locked queen has been accounted for, we set the depth
to our 0 starting depth and we are ready to go.
reset() {
this.locked = this.game.queens[0].y * 8 + this.game.queens[0].x;
for (let y = 0; y < 8; ++y) {
let d = y === this.game.queens[0].y ? 0 : -1;
for (let x = 0; x < 8; ++x) {
this.domains[y][x] = d;
}
}
this.depth = -1;
this.updateDomains(this.game.queens[0].x, this.game.queens[0].y);
this.depth = 0;
this.placeStepOnBoard();
}
The heart
of forward checking is our updateDomains method. This is broken into two
separate parts. The first part is where we remove invalid moves from the
domains of the queens on rows below the current queen. If the queen being
placed is the locked queen then we use the domain level 0 otherwise we use the
current domain. We only need to remove moves from rows below the current queen.
We know that queen’s can’t be in the same row, o, or diagonal, so these
coordinates are calculated based on the distance from the queen that is being
placed on the board.
This is
where things start to get a little confusing. We can’t just set the domains to
invalid but need to check that the tiles we are marking as invalid have not
already been marked invalid by a queen placed at a lower depth. This is required
to make sure backtracking works as a tile may have more than one queen in
conflict so backtracking only restores domain moves that are actually valid.
These are simple conditional checks so we make sure the diagonal is on the
board and the tile is sto;; viable and if so mark it with the current depth to
indicate it is now invalid.
updateDomains(qx,qy) {
// remove invalid moves from domain by marking with
level
let domainLevel = (this.depth < 0) ? 0 : this.depth;
for (let y = domainLevel; y < 8; ++y) {
if (this.domains[y][qx] < 0)
this.domains[y][qx] = domainLevel;
let dx1 = qx + y - qy;
let dx2 = qx -y + qy;
if ((dx1 >= 0) && (dx1 < 8) && (this.domains[y][dx1] < 0))
this.domains[y][dx1] = domainLevel;
if ((dx2 >= 0) && (dx2 < 8) && (this.domains[y][dx2] < 0))
this.domains[y][dx2] = domainLevel;
}
Once we
have marked the domain variables, we need to actually do the forward check and
see that every domain still has a move left. This is a loop through the rows below
the placed queen skipping over the locked row if it is encountered. We then
loop through the domain for that row exiting if we find a free tile. If there
is no valid tile then we set the backtrack flag and exit out of the row loop. If
the backtrack flag was set we call backtrack.
// see if remaining rows still valid
let row = domainLevel;
let needToBacktrack = false;
if (row >= this.game.queens[0].y)
++row
for (let i = domainLevel; i < 7; ++i) {
if (row === this.game.queens[0].y)
++row;
let move = false;
for (let c = 0; c < 8; ++c) {
if (this.domains[row][c] < 0) {
move = true;
break;
}
}
if ( ! move) {
needToBacktrack = true;
break;
}
++row;
}
if (needToBacktrack)
this.backTrack();
}
Backtracking
is easy. We simply loop through all the domains. Any domain set to the current
depth level or higher gets set to -1 which makes it a usable tile again. Once
this is done we set the depth to a lower depth and are finished.
backTrack() {
for (let y = this.depth; y < 8; ++y) {
for (let x = 0; x < 8; ++x) {
if (this.domains[y][x] >= this.depth)
this.domains[y][x] = -1;
}
}
--this.depth;
}
The nextMove
method is a much simpler way of implementing backtrack but only because all of
the above work. This method finds the row associated with this depth. Once on
the row, we loop over the domain for the row until we find the available tile. If
we then use the updateDomains method to place the queen for this depth on that
tile. If there is no spots available for our queen we backtrack.
nextMove() {
let row = this.depth;
if (this.game.queens[0].y <= row)
++row;
let moved = false;
for (let c = 0; c < 8; ++c) {
if (this.domains[row][c] < 0) {
this.moveable[this.depth] = row*8+c;
this.domains[row][c] = this.depth;
++this.depth;
this.updateDomains(c, row);
moved = true;
break;
}
}
if (!moved)
this.backTrack();
For debugging, we then draw the domains by looping over the domains for all tiles on the board and if the domain is -1 set a highlight tile in the game to our highlight color. While this was meant for my own debugging but as the effect is really cool, I decided to leave it in the game.
// show domains
for (let y = 0; y < 8; ++y) {
for (let x = 0; x < 8; ++x) {
if (this.domains[y][x] === -1) {
this.game.boardHighlights[y * 8 + x].setBackgroundColor("rgba(0,0,128,.5)");
this.game.boardHighlights[y * 8 + x].setVisible(true);
}
}
}
}
Running
this only takes a few seconds which is an improvement. There is still some situations
where lower board positions have domains that are clearly in conflict with each
other but this is really very slim improvements so I will stop my solver series
here. For those of you who wish to progress to the next step, you will want to
look into arc consistency.
