Friday, January 15, 2021

Queen's Challenge - part 1 the base game

 It's a new year so lets do something different, sort of. I am going to try something a bit different over the next several months. This month I will be going over the creation of the game, which is normal enough. One feature I want to add to the game is a solver. I figured it would be both interesting and informative to go over the techniques for solving the game ranging from brute force to smart brute force to backtrack solving to constraints. Each method would build off the other and would be added to the game.

Whar game am I talking about? Queens challenge is a chess puzzle, though no knowledge of chess is necessary to play. The goal of the game is to arrange 8 Queens on an 8x8 Chess board in such a way that none of them can capture another Queen. Originally this was a Flash game, but I have rewrote the game in JavaScript. The game is on my spelchan.com site with the source code on my repository (link here). 

The game uses my SLL library but could have easily been written from scratch. The game consists of two classes. The Queen class extends SLLImageLayer making it effectively a sprite. The purpose of this class is to hold position information for the Queen. A simple method for determining if a provided board location is in conflict with the Queen is provided. 

class Queen extends SLLImageLayer{
constructor(x,y,locked) {
super("queen", QC.playerQueen, QC.QueenClip);
this.changePosition(x,y);
this.setLocked(locked);
}

changePosition(x,y) {
this.x = x;
this.y = y;
this.moveTo(QC.boardOffsetX+this.x*QC.tileSize,
QC.boardOffsetY+this.y*QC.tileSize);
}

setLocked(b) {
this.locked = b;
if (b)
this.setImage(QC.lockedQueen);
else
this.setImage(QC.playerQueen);
}

isCoordinateBlocked(x,y) {
if (this._visible === false)
return false;
if ((x === this.x) || (y===this.y))
return true;
return (Math.abs(this.x - x) === Math.abs(this.y-y));
}
}

This is a very easy method as one simply has to check against the list of existing Queen’s to see if any of them are directly horizontal, vertical, or diagonal from the Queen that is being processed. If this happens to be the case, then the queens are in conflict. 

The game then consists of randomly placing the first Queen on the board. We can then let the players add other Queens by clicking on the desired tile on the Chess board. To make things simpler, we create a highlight rectangle that will follow the mouse and will check to see if the tile the player is over is valid. Once eight pieces are on the board, the player has won.

Not very much too the game, but solving the game is a bit tricker. Next month I will adjust the code so that we can use a solver to solve the game. This will be done in a visual way so that it will be possible to see the moves that the computer is trying so that the different methods of solving the game are better emphasised.