/ Algorithms

N-Queens - Web Workers

Well it has been not one but two posts in the lead up to this one. I going to avoid repeating myself here, so if you aren't familiar with the N-Queens problem, web workers or why I'm talking about them together, check those out. I'm going to jump straight into:

Architecture

I mentioned in the last post that web worker threads are expensive. This means that while I might have wanted to make an individual worker for every recursive call it was not a logical approach. Instead I chose to break the work up like this:

The main thread created what I called a supervisor worker. This supervisor then looped over each possible placement of the first piece in the first row. At each initial placement the supervisor sent a sub worker off to carry out the recursive search for all the possibilities from that placement.

I decided on this approach for a couple of reasons. First, it creates N+1 threads which seemed safe up to any N which I was going to be patient enough to wait for an answer for. Second, it divided up the work in a nice logical and easy to write way which avoided any duplication of work.

Overall I'd say the approach worked out quite well and was very straight forward to implement. The only thing that was significantly different from the normal solution was creating a mechanism by which the the supervisor could see when all it's sub workers had returned.

Let's dive into the code and take a look

Code

Supervisor

First I set up an onmessage within the supervisor which was listening for the start message and the value of N

var solutionCount = 0;
var stable;
var horses;

onmessage = function(e) {
  if(e.data.type === 'start') startSubRoutines(e.data.n);
};

function startSubRoutines(n){
  var board = makeEmptyMatrix(n);
  var cols = makeColsArray(n);
  stable = cols.map(function(){ return false; });
  horses = stable.map(function(){ return new Worker('./recursiveWorker.js'); });

  for(var i = 0; i < cols.length; i++) {
    var col = cols[i];
    board[0][col] = !board[0][col];
    horses[i].onmessage = receiveMessage;
    horses[i].postMessage({
      board: board,
      cols: cols.filter(function(item, index){ return index !== i; }),
      row: 1,
      horse: i
    });
    board[0][col] = !board[0][col];
  }
}

The sub workers, which I called horses, are placed into an array after I create an empty stable which the horses will return to. Then one by one I place piece on the board and send a horse off with a copy of the board(remember data is sent to a worker as a copy by default). Then I pick the piece up and move to the next horse.

Notice I set the horses onmessage handler to the receiveMessage function.

function receiveMessage(e) {
  switch(e.data.type) {
    case 'count':
      countSolution();
      break;
    case 'stable':
      stableHorse(e.data.horse);
      break;
    default:
      console.log('I didn\'t prepare for ', data.type);
  }
}

function countSolution() {
  solutionCount++;
}

The receiveMessage function looks for either a message type of 'count' or 'stable'. When the 'count' message comes in this means a solution has been found and the I increment the solutionCount.

When a 'stable' message arrives it means a horse has finished its ride and I can mark a branch as traversed.

function stableHorse(horse) {
  stable[horse] = 'returned';
  if(checkStable()) {
    postMessage({ solutionCount: solutionCount });
    self.close();
  }
}

function checkStable() {
  return stable.reduce(function(memo, horse) {
    if(horse !== 'returned') {
      memo = false;
    }
    return memo;
  }, true);
}

Each horse carries it's index in the stable so I can mark it returned. Then I run checkStable to see if there are still any horses away. If so the function exits. If, however, this was the last horse I postMessage to the main thread with the solution count. The process is done!

Sub Workers

The sub workers essentially contains the base logic of the straight sequential solution. Really the only change is that it has to start from an onmessage handler and it needs to send each solution, and it's exit, back to the supervisor.

onmessage = function(e) {
  recurse(e.data.board, e.data.cols, e.data.row);
  postMessage({ type: 'stable', horse: e.data.horse });
  self.close();
}

function recurse(board, cols, row){
  if(cols.length === 0){
    postMessage({ type: 'count'});
  }else{
    for(var i = 0; i < cols.length; i++){
      var col = cols[i];

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

Wrap Up

That's it! With the normal solution in place and an understanding of web workers this was pretty simple. The key was finding where to divide up the work and in this particular case it kind of fell out naturally.

Now, hopefully you're wondering more than how I implemented this process. For me there was one real question: "Should I use web workers? If so, when?". I can say that, although this was a rather contrived usage, I have a pretty good idea now of when, and for what tasks, web workers would be useful. Stay tuned for my analysis and my next experiment: concurrency in Go.