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.

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.

Queen’s Challenge - part 3 of 6

 Part 3 – Brute Force

Brute force approaches to solving problems are often the first approaches tried when attempting to solve a problem. Computers are fast, so why not just try all the possible solutions until we find one that works? As we will see shortly, while brute force solutions work, they are very inefficient making them infeasible for many problems.

A brute force solution for the Queen’s Challenge game would be to simply try all possible combinations until you find one that works. If I didn’t have my animation framework this would be trivially easy to implement, but by showing each step as I am, the work is a bit more complicated. Without the animation, the brute force method would look something like this:

Q0 = assigned_location
For q1 in range (1..58):

For q2 in range(q1..59):

…

For q7 in range(q6..64):

If (valid layout) break

Doing updates using steps is a bit trickier as we don’t have nested loops so will need to manually track the loop.  If you recall, a for loop is essentially just a macro for making a while loop with a counter. This concept can be easily extended to supporting nested loops by simply holding an array of loop indexes and updating them appropriately. This means that to implement our animated version of brute force solving we first need to set up an array of indexes, which we already are doing to hold the positions of the queens.  The reset method would then look something like this:

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

With the loops properly set up to skip over the locked spot if it is in one of the other seven queen’s starting position, we now can focus on the looping. This can be a bit confusing as while there are 8 queens, one is locked so we only have 7 counters (0 through 6). We need to loop backwards through these to find the lowest counter that needs to be updated. Remember that for a loop to go to the next element, the loop inside of it must have reached it’s end condition and for that loop to reach the end condition the loop inside of it must have reached it’s end condition and so on until the inner-most loop has reached it’s end condition. If a counter is incremented, but has not reached it’s end condition then we can break out of the updating loop as we know none of the loops above it need to be changed yet.

    nextMove() {
        let pieceToMove = 0;
        for (let i = 6; i >= 0; --i) {
            let nextPos = this.moveable[i] + 1;
            if (nextPos === this.locked)
                ++nextPos;
            if (nextPos < (57+i)) {
                pieceToMove = i;
                this.moveable[i] = nextPos;
                break;
            }
        }

Once we have updated the outer-most loop that have reached their end conditions, all the loops above it would be restarted so we simply loop from the outermost updated loop to the end of the list of loops to set them to their next starting state which would be one greater than the previous counter unless the locked queen happens to be on that tile.

        for (let i = pieceToMove+1; i < 7; ++i) {
            let nextPos = this.moveable[i-1] + 1;
            if (nextPos === this.locked)
                ++nextPos;
            this.moveable[i] = nextPos;
        }
    }

We now have our brute force implementation completed. This can be ran and we can watch the computer solve the game. This might take a while. After watching for a few minutes, we can readily see there is an obvious problem with our initial brute force approach. Most of the time, we are in an obviously invalid state as multiple tiles are on the same row! A quick fix could speed this up but how long will the brute force approach take?

To go through the complete loop, which is not necessary as a solution would be found way before then, we would need each of the loops to complete with the inner loops having to run multiple times. There are 7 variables looping through 57 possible positions on the board so a rough approximation would be 57^7 for 1,954,897,493,193 though because loops are going through progressively smaller counts, we would only have 994,596,970,221 iterations. On today’s hardware, we could probably process this number of moves quickly if we weren’t animating them but that is still a huge number of board positions that need to be processed. If we increase the board size, this grows ridiculously quickly. 

So the next step on improving the solver is simply enforcing a constraint on where the queens can be placed. This will be our next step and will dramatically reduce the number of moves. The source code is available on github https://github.com/BillySpelchan/BlazingPorts but may contain spoilers of future versions as I am going to be updating the repo as I work on the remaining parts of this series whenever I find a bit of spare time.

Queen’s Challenge - part 2 of 6

Animated Solver Framework 

Solving a game tends to be where things get challenging as often any brute-force method is going to require an exceedingly large number of trials to find a solution. That is pretty much the case with the Queen’s Challenge puzzle. More advanced approaches need to be used. For this series, we want to compare different approaches which is easiest if the user can see how the solver is solving the problem so we are going to need an animated solver framework which we will be roughing out today. Next, we will implement a brute force solver. Part 4 covers a smarter version of the solver. This will be followed by quite common approach of a backtracking solver. The final part will cover a more complicated approach using constraints.

We know that there are going to be 4 different solvers so we will want to create a base solver class so the game can simply call methods in this class to get the next step in solving. To simplify the solver, we are going to represent positions on the board as a single number so 0 through 7 would be the top row, 8 through 15 the next row and all the way to the last row. Complicating matters is that we do have one locked queen and seven queens that we can place. This can be set up as a locked variable and an array of moveable queens.

class BaseSolver {

    constructor(game) {

        this.game = game;

        this.locked = game.queens[0].y * 8 + game.queens[0].x;

        this.moveable = [0,1,2,3,4,5,6,7];

    }

While we are not doing anything with it now, the solver is going to need to be able to reset itself and set up the initial position of the queens based on the current position of the locked queen. While this is a bit of a kludge, we will assume that the game’s Queen[0] will be the locked Queen.

    reset() {

// TODO

    }

At this point we came into a bit of a dilemma as I am thinking that placing the queens on the board could be handled by the game when running the solver. Ultimately, since I may want to show additional information about the state of the solver (I don’t know as I am writing this as I am working on the code so this is as close to live coding as my blog can be) I figure the placing of the pieces on the game board will be the responsibility of the solver. 

    placeStepOnBoard() {

        for (let i = 0; i < 7; ++i) {

            let qx = this.moveable[i] % 8;

            let qy = Math.floor(this.moveable[i] / 8);

            this.game.queens[i+1].changePosition(qx,qy);

            this.game.queens[i+1].setVisible(true);

        }

    }

The heart of the solver will be making the next move. This will be where the solver looks at the current state of the solution and advances to the next one. This approach is a bit more complicated than having a solver just to try and solve the problem as with a traditional solution you could simply have nested loops, but this will have to infer the loop state from the positions. By having a separate step function for our solver, however, lets us do the solution in discrete steps which can then be rendered so the user will be able to see the solver working, which is the whole point of this exercise.

    nextMove() {

//TODO

    }

Finally, the user may be impatient with the solver and start a new game or switch to a new solver in which case we will want to stop the solver. This allows the solver to remove any visual aids from the board if we actually have any.

    stopSolver() {

//TODO

    }

}

To implement the solver, we are going to need buttons for starting a solver. These are simple enough to add as it is simply GUI code placed in the game’s constructor. While here we will also set the current solver to null to indicate that there is no solver being used.

        this.solver = null;

        this.solveBruteButton= new SLLTextButton("brute",

            new SLLRectangle(530,200,100,30),

            "Brute force", 3);

        this.solveBruteButton.setClickHandler(this);

        this.addChild(this.solveBruteButton);

The code for handling starting the solver is placed in our buttonClicked method and simply calls a startSolver method that we are going to need to write. This simply shuts down an existing solver before setting the solver to the new solver and calling that solver’s reset method. We are using timeouts for animation instead of animationFrames as 60 fps is way too fast for watching the solver so a lower speed is desired.

   startSolver(solver) {

if (this.solver != null)

this.sover.stopSolver();

        this.solver = solver;

        solver.reset();

        setTimeout(this.nextSolverStep.bind(this), 10);

    }

We need to run the animation until the board is solved (or interrupted, but we will fix that later). This is very simple matter of going through all the queens and seeing if any of them are in conflict with an earlier placed queen.

    isBoardSolved() {

        let solved = true;

        for (let q = 1; q < 8; ++q) {

            let queen = this.queens[q];

            for (let i = 0; i < q; ++i)

               if (this.queens[i].isCoordinateBlocked(queen.x, queen.y))

                   solved = false;

        }

        return solved;

    }

Finally, we have our main animation loop where we draw the board and then check to see if the board is solved. If not, we get the next move and set a timer for the next redraw. 

    nextSolverStep() {

        this.solver.placeStepOnBoard();

        if ( ! this.isBoardSolved()) {

            this.solver.nextMove();

            setTimeout(this.nextSolverStep.bind(this), 250);

        }

        draw();

    }

While this framework is simple enough, we now need to get a solver working properly so that we can see a solution as it is happening. Next post I will look at the most basic – and least useful – of the solvers. Namely using brute force. While it will not be a useful method for solving, it is a good starting point and should let us discover if there are any issues with our framework. I am writing this as I write the code so let’s hope things go smooth and that the article is short enough that I can do some additional cleanup work!