Queen's Challenge - Part 4 of 6

 Part 4 – One Queen Per Row

Last time we saw a big problem with the brute force approach which we saw that queens were often placed on the same horizontal line as other queens which we know is not possible. This is a problem that can easily be rectified by imposing a constraint on where we are allowed to place the queens.  Ultimately, we are still going to be brute forcing the solution but by removing the most obvious issues with brute force.

The term constraint is simply mathematical speak about a rule restricting the values a variable can hold based on the value in other variables. Having more than one queen in a given row is clearly not valid so we can eliminate all boards where there are multiple queens on a single line. Applying the constraint that each queen must be on a unique row drastically will improve the performance of our search for a solution.

Creating our row-based brute force solver is simple enough as we can just extend the BaseSolver to get much of the logic. The only things we then need to implement is the reset and the next move methods and they are very similar to the brute force solver.

class RowBruteSolver extends BaseSolver {
    constructor(game) {
        super(game);
    }

    reset() {
        this.locked = this.game.queens[0].y * 8 + this.game.queens[0].x;
        let lockedRow = this.game.queens[0].y
        let spot = 0;
        for (let i = 0; i < 7; ++i) {
            if (i === lockedRow)
                spot += 8;
            this.moveable[i] = spot;
            spot += 8;
        }
    }

 

As with the brute force solver, we set the locked tile to be the tile number of the tile based on the row and column of the locked tile in the game. We need to know which row this tile is on, which is just the y coordinate of the locked queen. As each row of tiles has 8 tiles on it, we know that the tile number will be 8*the row but we know we need to skip the row that row that the locked queen is on. To do this we use a spot variable that starts at 0 and if the current row is the same row as the locked row increases the spot by 8 to move the starting spot to the first (0) column of the next row. The queen is set and we update the spot for the next queen by adding 8 to it.

 

    nextMove() {
        let pieceToMove = 0;
        for (let i = 6; i >= 0; --i) {
            let nextPos = this.moveable[i] + 1;
            if ((nextPos % 8) > 0) {
                pieceToMove = i;
                this.moveable[i] = nextPos;
                break;
            }
        }
        for (let i = pieceToMove+1; i < 7; ++i) {
            this.moveable[i] = Math.floor(this.moveable[i] / 8)*8;
        }
    }
}

 

The nextMove method tries to move the last row’s queen to the next column and if that move results in the queen going off the board , moves up the list row by row until it finds a queen that it can move to the right without going off the board. Once that has been done, we simply set the queens below it to the first tile of that column.

Watching the results of this solver clearly shows an improvement from the first solver. If you are patient and can wait a few hours, you can even see a solution to the game. Watching for a minute or so will quickly show us the next issue that we need to solve. We still are placing queens in locations were they are in conflict with each other and then processing all the queens below the conflicting queens even though we know that none of those potential layouts will result in a valid solution. Still this is a big improvement over the brute force approach.

From a worst-case perspective, we know that there are 7 queens with each queen having 8 possible locations so that would be 8^7 possible boards that need to be examined. While 2,097,152 boards is certainly better than 994,596,970,221 it is still quite a bit of work. We can do even better by finding a way to remove all those unnecessary searches. But how can we do this? A simple change to our solver will allow us to eliminate entire branches of moves so we don’t waste time testing moves that can’t possibly work as we will discover in the next part.