N-Queens Implementation in Javascript

Week 2, Day 4 of Hack Reactor:

Having already passed the data structures sprint where we implemented 4 different instantiation patterns in JavaScript. Our next two-day sprint focused on algorithms and working on an implementation of the classic N-Queens problem.

The problem is simple: How many ways are there to arrange n queens on an n by n chessboard such that no queens are in a direct line of attack.

Our first implementation was very, very slow, taking ~15 minutes for N=8.

How we stored the chessboard: 2D-array


[ [0,1,0],

  [1,0,0],

  [0,0,1] ]

Having (barely) passed the core requirements, we then set our eyes on the extra-credit section. There was a lot of room for improvement in the time complexity. Since the nature of the problem requires a brute-force technique along with a collision detect on every queen being placed. I discovered that the large majority of our code’s time was being spent checking for collisions. Since our algorithm spent most of its time checking collisions, that was the first place to improve. At a glance, our implementation of collision detection had a time complexity of O(n^2) on each row for a total time complexity of O(n^3)…(after n^2, it pretty much goes downhill from there).

My initial thought for improving efficiency was a different way of representing the chessboard that was more efficient than the 2D-array we were currently using.

From a 2D-array to a 1D-array:


[1, 0, 2]

Since we know that every solution will have a queen in every row, we don’t care about the spaces where there aren’t queens. We only care about the locations of each queen in the row. With this implementation, each index of the array represents the row, and the value represents the location of the queen in that row.

For example, row 0 has a queen in position 1, row 1 has a queen in position 0, and row 2 has a queen in position 2. By using this representation, the time complexity for checking collisions is O(N) since we are only traversing one array.

But  how we can do better? I’ll give you a hint: hash tables.

From a 2D-array to an object:


{0: 1, 1: 0, 2: 2}

Using the same logic as rows, the keys represent the rows and the values represent the location of the queen in that row. However, since objects are implemented as hash tables in javascript, we can take advantage of the constant time lookup, O(1).

We had less than a day at this point to refactor our original N-Queens implementation. We felt the other two implementations, although more efficient, would not give us much of a challenge. We instead went with a bitwise implementation because who doesn’t love a good bitwise from time to time.

Following this very old code, here is our bitwise javascript implementation of N-Queens:


var countNQueens = function(n){
  var all = Math.pow(2,n) - 1;
  var solutionCount = 0;

  var findSolutions = function(cols,ld,rd){

    var pos = ~(cols | ld | rd) & all;

    while(pos>0){
      var bit = -pos & pos;
      pos = pos ^ bit;

      findSolutions((cols | bit), (ld | bit) << 1, (rd | bit) >> 1);

    }
    if (cols === all) {
      solutionCount++;
    }
  };
  findSolutions(0, 0, 0);
  console.log(solutionCount);
  return solutionCount;
};

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s