Blog Archives

N-Queens, Algorithms, REST, and Ajax – Hack Reactor Week 2

Inside Hack Reactor

Week 2 at Hack Reactor has come to a close, but the frantic pace of learning continues. We kicked off week 2 by finishing up our Sub-Class and OOP sprint that involved making individual nodes “dance” on the page with any random behaviors we decided to give them. What we ended up with were fancy screen savers with objects that could interact with each other (and explode!). This led us to a discussion of particle systems, which sounds like something I want to devote some time to once this course is over.

We had another guest lecture at the beginning of the week regarding algorithms, complexity analysis, and ways to approach solving interview problems. Solving complex problems like this while under pressure is a skill I need to work on, but luckily there are a few great online resources to help build your skills. Some of my favorites that I’ve used so far are:
Project Euler
Coderbyte
TopCoder Algorithm Tutorials

Our discussion of algorithms led us into our next project, and my favorite project of the week, called N-Queens. This goal of this project is to find how many ways n queen chess pieces can fit on an nxn chessboard without being able to attack each other. So, if you have a 4×4 chessboard, how many different ways can you fit 4 queen chess pieces on the board so that all 4 queens are safe from being attacked by the other queens? The answer for the 4×4 board is 2 different arrangements of queens. For a more in-depth explanation, check out the wikipedia entryfor the 8 queens solution.

Currently, the largest board that all solutions have been found for is a 26×26 board. At this time, 27×27 is too large of a solution to be handled by today’s computer processors with the current algorithms. However, some students in the senior Hack Reactor class are tackling this problem with an app called supercomputer.js that leverages many networked computers, each solving a small portion of the entire algorithm (similar to the Playstation 3 Folding@Home project out of Stanford).

We spent much of the first day building a JavaScript algorithm for finding single solutions to this problem, and testing it on small chess boards (less than 8×8). We ran through a series of tests written in Jasmine to ultimately come to an algorithm that would successfully find every solution for a given n. However, our first attempt was a brute-force solutions that used 2-dimensional arrays to build every possible configuration of n queens on the board. We then tested every one of these board layouts to determine if it was a valid arrangement where the queens couldn’t attack one another. The boards that passed our test were put into a results array, and then counted. This solutions was very inefficient and took a tremendous amount of computer processing power to complete. This first attempt could not find a solution to any n over 7, because the browser would time out before the JavaScript was done running.

Now that our algorithm was finding all of the correct solutions, it was time to optimize it so that we could find solutions to chess boards above 8×8. Our first optimization involved making our tests for evaluating correct boards more efficient. With these improvements, we were able to find all 92 solutions to n=8 in just over 20 seconds on a Mac mini. From there, we decided to trim down the number of chess boards our algorithm generated.

Instead of creating a large tree data structure of all possible solutions, we started checking early on in the board building process if the piece we just placed was in conflict. So, once we placed a queen on the first row, we knew no other queens could be placed on that row, thus moving on to second row right away. We also knew that the first queen placed on the second row cannot be placed in the same column as the piece on the first row, thus “pruning” our data tree of all possible iterations below that conflicting node. We also checked for diagonal conflicts before placing each piece. The result of this “pruning” was allowing our algorithm to find all solutions on an 8×8 board in about 2.5 seconds!

We were pretty excited about our 10x improvement in speed, but we decided to see if we could make it even faster. Up until this point we represented our solutions using 2-dimensional arrays, which take a lot of iterations to traverse all of the elements. We decided to represent our boards using a simple 1-dimensional array instead. For example, a 3×3 array normally looks like [[1,0,0],[0,1,0],[0,0,1], with the 1 representing a queen (not an actual solution obviously). Instead, we can represent this same array with [0,1,2] , with each index of the array representing a row, and the value of that index representing where in that row the queen is located. Once we implemented this new storage mechanism, our time for finding the n=8 solution was reduced to 49 milliseconds! It was very satisfying to see such huge speed gains from each improvement we made in our code. Here is our final JavaScript solution:

window.countNQueensSolutions = function(n){
  var startTime = new Date();
  if (n===0){return 1;} //0 queens fit on a 0x0 board 1 time
  var solutionCount = 0;
  var rNQueens = function(tempBoard){
    if(tempBoard.length === n){
      checkQueenSolution(tempBoard) && solutionCount++;
      return;
    }
    for(var i = 0; i < n; i++){
      var boardCheck = tempBoard.concat(i);
      if (checkQueenSolution(boardCheck)){
        rNQueens(boardCheck);
      } else {
        continue;
      }
    }
  };
  rNQueens([]);
  var endTime = new Date();
  console.log('Number of solutions for ' + n + ' queens:', solutionCount, 'in', endTime - startTime, 'milliseconds');
  return solutionCount;
};

window.checkRookSolution = function(matrix) {
  return _.uniq(matrix).length !== matrix.length ? false : true;
};

window.checkQueenSolution = function(matrix) {
  if(!checkRookSolution(matrix)){
    return false;
  }
  for(var i = 0; i < matrix.length; i++){
    for(var j = i+1; j < matrix.length; j++){
      if(i - j === matrix[i] - matrix[j] || i - j === -matrix[i] + matrix[j]){
        return false;
      }
    }
  }
  return true;
};

The remainder of week 2 was spent learning about HTTP requests, REST, and how to use Ajax with the service from Parse. We lumped this all together to create a real-time chat room client that all of the Hack Reactor students could use. Once everyone was up and running with the chat client, we implemented features like preventing script attack hacks, creating friends lists, and allowing the user to create and join new chat rooms.

This week was intense, but the instructors are warning us about the start of week 3, which involves us diving into Backbone.js. I’m running through some Codeschool tutorials on Backbone right now to get prepared for next week!