Queen's Challenge - Part 5 of 6

 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.