/ Javascript

N-Queens

N-Queens, for those unfamiliar, is a classic algorithm challenge which I first came across several months ago. I came across it again recently in working with a group of students and someone suggested an additional challenge: implement a solution using web workers. Now I had never worked with web workers before so obviously I did it. And it was incredibly easy! But that is for the next post. I thought it would be helpful in explaining that to have a plain old sequential JS solution to refer to, so, here it is.

The Question

 ---------- ---------- ---------- ----------
|          |\\\\\\\\\\|          |\\\\\\\\\\|
|          |\\\\\\\\\\|          |\\\\\\\\\\|
|          |\\\\\\\\\\|          |\\\\\\\\\\|
|          |\\\\\\\\\\|          |\\\\\\\\\\|
 ---------- ---------- ---------- ----------
|\\\\\\\\\\|          |\\\\\\\\\\|          |
|\\\\\\\\\\|          |\\\\\\\\\\|          |
|\\\\\\\\\\|          |\\\\\\\\\\|          |
|\\\\\\\\\\|          |\\\\\\\\\\|          |
 ---------- ---------- ---------- ----------
|          |\\\\\\\\\\|          |\\\\\\\\\\|
|          |\\\\\\\\\\|          |\\\\\\\\\\|
|          |\\\\\\\\\\|          |\\\\\\\\\\|
|          |\\\\\\\\\\|          |\\\\\\\\\\|
 ---------- ---------- ---------- ----------
|\\\\\\\\\\|          |\\\\\\\\\\|          |
|\\\\\\\\\\|          |\\\\\\\\\\|          |
|\\\\\\\\\\|          |\\\\\\\\\\|          |
|\\\\\\\\\\|          |\\\\\\\\\\|          |
 ---------- ---------- ---------- ----------

The question is fairly straight forward: given an NxN chess board (4x4 above), how many ways can you place N queens such that no queen is attacking another? For those who may not play chess a queen can attack any piece that is aligned with it either vertically, horizontally or diagonally. It's the diagonals that make you do the work.

Ultimately the solution is one of recursively examining permutations of each of the N queens and counting the successful solutions. The trick is in finding how to minimize the number of checks.

The Setup

First we need a board to work with. While we could create more elaborate structures if we wanted to render this to the web, it's all a matrix in the end and that will do just fine for this.

function makeEmptyMatrix(n) {
  var matrix = [];
  for(var i = 0; i < n; i++){
    var row = [];
    for(var j = 0; j < n; j++){
      row[j] = false;
    }
    matrix[i] = row;
  }

  return matrix;
};

This simple function will take whatever N number of queens we decide to test and build an array of length N with each element being another array of length N. The matrix array itself then houses N 'rows' with each row having N 'columns' just like our chess board.

function makeColsArray(n) {
  var arr = [];
  for(var i = 0; i < n; i++) {
    arr[i] = i;
  }
  return arr;
};

The reason we need this may not yet be apparent, and that's ok, but it will create a single array of length N. It will be used to track which columns have we queen in.

The last functions are utilities which we will used to check the diagonals for any conflicts with another queen.

function hasMajorDiagonalConflictAt(board, colIndex, rowIndex) {
  var n = board.length;
  while(--colIndex >= 0 && --rowIndex >= 0) {
    if(board[rowIndex][colIndex]) return true;
  }

  return false;
}

A major diagonal is one which goes from top left to bottom right across the board, like a ''.

A minor diagonal goes the other way, like a '/'.

function hasMinorDiagonalConflictAt(board, colIndex, rowIndex) {
  var n = board.length;
  while(++colIndex < n && --rowIndex >= 0) {
    if(board[rowIndex][colIndex]) return true;
  }

  return false;
}

Each of these functions takes a reference to the board in it's current state, the current column and the current row. They then move up checking the top half of the board for any conflicting queens on their diagonals. The reason it only checks the top half of the board will be more clear soon.

The Solution

As I mentioned before the answer is to recursively check all permutations of placing each queen across the board track all arrangements with no conflicts. Certainly the naive approach would work but the three helpers we have made here can save us a lot of work.

Observations
  1. If we start at the top left square and place a queen we immediately know two things.
  • First, we cannot place another queen in the top row.
  • Second, we cannot place another queen in the first column.

That might seem simple but it saves our algorithm an immense amount of work! That is several thousand possible placements we don't have to check!

  1. If we place pieces across the board starting from top and work to the bottom we never need to check the diagonals below the piece we are currently placing.

  2. If we only place pieces in empty rows/columns and check the diagonals for conflicts before moving on we can short circuit an enormous number of unnecessary placements.

Bringing It All Together

Now that we have an outline let's take a look at the code!

function plainCountNQueens(board, cols, row, count){
  cols = cols || makeColsArray(board.length);
  row = row || 0;
  count = count || 0;

  if(cols.length === 0) {
    return ++count;
  } else {
    for(let i = 0; i < cols.length; i++) {
      let col = cols[i];

      if(!hasMajorDiagonalConflictAt(board, col, row) && !hasMinorDiagonalConflictAt(board, col, row)) {
        let cols = cols.filter((item, index) => index !== i);
        board[row][col] = !board[row][col];
        count = plainCountNQueens(board, cols, row+1, count);
        board[row][col] = !board[row][col];
      }
    }
  }
  return count;
};

So, the function expects to get handed a reference to the current state of the board, the available columns, the current row in which to place a piece and the solution count. If it doesn't find these it must be the first call and it will set them to their initial values.

It moves down each row in the board and places a piece in one of the available columns. Here it checks the major and minor diagonals for any conflicts and if it finds none, continues to the next row, the recursive call, to do it all again.

When it reaches a call in which there are no columns left available then all pieces must have been placed. The count is incremented and returned up the call chain. The previous steps is returned to and picked up until there is a row with an untested and unplaced column to try. Then it travels to the bottom once again.

Finally when all trails have been chased to their end of cut off by a conflict the count is returned all the way up the call stack and into the context which originally called the function, delivering our solution!

Clarifying Points

Some astute observers might notice a few things that I have done in this solution and initially wonder why. Let me address a few those here.

  1. I placed a piece on the board and passed the board down by reference, picking the piece back up when the call returned. However I filtered a new copy of the columns array for every recursive call.
  • Placing and removing a piece is a constant time operation and thus there was no benefit to the added space complexity
  • Removing an element from an array and putting it back is a linear operation that would have to occur twice for every recursive call. Filtering is linear and only must occur once.
  • While both are O(n) it took the time on my original test array down from 9ms to 6ms with that one change. That's 33%
  1. Why not do this with a binary matrix and use bitwise operations?
  • It's on my list :D