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.