Eight Queens and Processing.js

In the earlier post about the 8-queens problem, we arrived at the final solution.
We couldn’t get a chance on deeper insights on the intermediate steps involved in solving.
The GIF image found at the wikipedia entry says it all.
I just tried emulating the GIF animation with html5/canvas and processing.js

The animation is achieved with the help of alert() function.
There are better alternate ways to do it.

This actually solves not just 8 queens problem but the generalized N Queens problem.
It is controlled by the dim variable (please see the code below).
You can choose the larger number at your own risk.

Fortunately, all the measurements like
1) the cell size (70), 2) font-size(48) and 3) painting location of the queen (X)
worked together perfectly (well, almost).
So, if you want the board to be bigger or smaller, please also take care of other dependent parameters.

I have written three files.
1) .html file 2) .pde (processing.js) file 3) .js file (that contains the core logic of solving the problem. This uses the backtracking algorithm)
Let us see the code of these files in the same order

my_chess_board1.html

<!DOCTYPE html>
<html>
  <head>
    <title>Eight Queens</title>
    <meta charset="UTF-8">
    <script type="text/javascript" src="8q.js"></script>
    <script type="text/javascript" src="processing-js-1.4.1/processing-1.4.1.js"></script>

  </head>

  <body>
    <canvas data-processing-sources="my_chess_board1.pde" style="border: 1px solid black;"></canvas>
  </body>
</html>

my_chess_board1.pde


int dim = 6;
int siz = 70;
String queenStr = "X";
Color white = #FFFFFF;
Color black = #000000;
Color grey  = #DDDDDD;

void setup() {
  size(siz * dim, siz * dim);
  textFont(createFont("Arial", 48));
  noLoop();
}

void draw() {
  drawBoard(dim, siz);
  MAIN(dim, 1, placeQueen, deleteQueen);
}

void drawQueen(row, col, clr) {
  fill(clr);
  float tWidth = textWidth(queenStr);
  text(queenStr, col * siz + tWidth / 2, row * siz + siz * 0.75);
  alert(' ');
}

void placeQueen(row, col) { drawQueen(row, col, black); }

void deleteQueen(row, col) {
  if((row % 2 == 0 && col % 2 == 0) || (row % 2 == 1 && col % 2 == 1))
    drawQueen(row, col, white);
  else
    drawQueen(row, col, grey);
}

void drawBoard(boardSize, cellSize) {
  for(var r = 0; r < boardSize; ++r) {
    for(var c = 0; c < boardSize; ++c) {
      if((r % 2 == 0 && c % 2 == 0) || (r % 2 == 1 && c % 2 == 1))
        fill(white);
      else
        fill(grey);
      rect(r * cellSize, c * cellSize, cellSize, cellSize);
    }
  }
}

8q.js


function colPresence(c, qpos) {
	for(var i = 0; i < qpos.length; ++i)
		if(qpos[i] == c)
			return true;
}

function diagPresence(r, c, qpos) {
	return diagChk(r - 1, c - 1, -1, qpos) || diagChk(r - 1, c + 1,  1, qpos);
}

function diagChk(r, c, d, qpos) {
	return r < 0        ? false :
	       qpos[r] == c ? true  :
	       diagChk(r - 1, c + d, d, qpos);
}

function tryPos(boardSize, r, c, qpos, placeQueenFun, deleteQueenFun) {
	var nextr, nextc;
	if (r == boardSize)
		return;

	if (c == boardSize) {
		if (r == 0) {
			console.log("Solution not possible");
			return;
		}
		nextr = r - 1;
		nextc = qpos.pop() + 1;
		deleteQueenFun(nextr, nextc - 1);
	} else if (colPresence(c, qpos) || diagPresence(r, c, qpos)) {
		nextr = r;
		nextc = c + 1;
	} else {
		qpos.push(c);
		placeQueenFun(r, c);
		nextr = r + 1;
		nextc = 0;
	}

	tryPos(boardSize, nextr, nextc, qpos, placeQueenFun, deleteQueenFun);
}

function MAIN(boardSize, noOfColsToTry, placeQueenFun, deleteQueenFun) {
	for(var i = 0; i < noOfColsToTry; ++i) {
		console.log('Trying for '+ boardSize +', '+ i);
		tryPos(boardSize, 0, i, [], placeQueenFun, deleteQueenFun);
	}
}

Advertisements