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!
No comments:
Post a Comment