Monday, June 14, 2021

Queen's Challange Part 6 of 6

 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.