8 Queens Problem

Today, we are going to look at the classic problem of placing Queens on a chessboard, such that no Queen is attacking any other Queens. It’s immediately obvious that we cannot place more than 8 Queens and meet these conditions, but can we place 8 Queens on the board? The answer is yes, we can.

One approach would be to place the Queens randomly on the board, then check for the conditions of the problem. Using this approach the first Queen can be placed on one of 64 squares, the next on one of 63 square, and so on. This would result in 64 * 63 * 62 * 61 * 60 * 59 * 58 *57 permutations, which is a very large number, so we can abandon that idea!

Chess players refer to the vertical columns on the board as files, and the horizontal rows are ranks. A bit of thought reveals that there must be only 1 Queen in each of the files A to H, and also only 1 Queen in each of the ranks 1 to 8. This can be encoded as an 8 digit number, representing the rank within each file, going from A to H. For example the number ‘12345678’ would mean the Queens were placed on square A1, B2, C3, D4, E5, F6, G7 and H8. Obviously, this is not a valid solution as A1 and H8 are attacking each other, but it is a start.

If we generate all the possible permutations of ‘12345678’ (there are 40,320) and place the Queens on the board accordingly, we would be guaranteed that no Queen would be attacking any other Queen vertically or horizontally. We would still need to check for diagonal attacks and eliminate those permutations. Also we would be certain that we had found all possible solutions.

I’ve coded a page with this algorithm here. It has a button to start the script.

This is the Javascript code for the algorithm. The results are displayed in a dropdown list; I’ve added an event listener to that to display the Queens on the chessboard.

imgBoard = new Image();
imgBoard.src = "images/chessboard.png";
imgQueen = new Image();
imgQueen.src = "images/queen.png";
if (canvas.getContext) context = canvas.getContext("2d");
iFiles = [];

imgBoard.onload = function() {
  document.getElementById("clickMe").addEventListener("click", onClick, false);
  message = document.getElementById("message");
  select = document.getElementById("dropdown");
  canvas = document.getElementById("canvas");
}

function onClick(event) {
  const startTime = Date.now();
  var resultsFound = 0;
  //initialise '12345678' 
  for (i = 0; i < 8; i++) iFiles[i] = i + 1;
  getNextPerm();
  while (iFiles[0] != 0) {
    //check for diagonal attacks
    isValid = true;
    for (i = 0; i < 7; i++) {
      for (j = i + 1; j < 8; j++) {
        if ((j - i) == Math.abs(iFiles[j] - iFiles[i])) {
	  isValid = false;
	  break;
        }
      }
      if (!isValid) break;
    }
    if (isValid) {
      resultsFound++;
      s = "";
      for (i = 0; i < 8; i++) s = s + iFiles[i];
      //populate the drop down with correct values
      var option = document.createElement("option");
      option.value = s;
      option.innerHTML = s;
      select.appendChild(option);
    }
    getNextPerm();
  }
  const endTime = Date.now();
  document.getElementById("clickMe").style.display = "none";
  message.innerHTML = resultsFound + " results found in " + (endTime - startTime) + " milliseconds";
  select.addEventListener('change', drawBoard);
  select.style.display = "inline";
  drawBoard();
}	

function drawBoard() {
  context.drawImage(imgBoard, 0, 0, 560, 560, 0, 0, 560, 560);
  //draw Queens
  for (i = 0; i < 8; i++) {
    x = 8 - parseInt(select.value.substring(i, i + 1), 10);
    context.drawImage(imgQueen, 0, 0, 70, 70, i * 70, x * 70, 70, 70);  
  }
}

function getNextPerm() {
  n = iFiles.length;
  //find the largest index k such that elements[k] < elements[k + 1]
  for (k = n - 2; k >= 0; k--) {
    if (iFiles[k] < iFiles[k + 1]) {
      //find the largest index l greater than k such that elements[k] < elements[l]
      for (l = n - 1; l > k; l--) {
        if (iFiles[k] < iFiles[l]) {
          //swap elements k and l
	  sTemp = iFiles[k];
	  iFiles[k] = iFiles[l];
	  iFiles[l] = sTemp;
	  //reverse remainder of string
	  k++;
	  n--;
	  while (k < n) {
	    sTemp = iFiles[k];
	    iFiles[k] = iFiles[n];
	    iFiles[n] = sTemp;
	    k++;
	    n--;
          } 
	  return;
        }
      }
    }
  }
  //not found
  iFiles[0] = 0;
}

This finds the 92 results in 4 milliseconds on my PC. Click on the dropdown to see individual results on the chessboard.