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.
