Thursday, January 16, 2014

N Queens Problem - Backtracking


The N Queens problem is a simple yet effective way of assessing a developer's ability to use recursion. For that reason, it may show up during technical interviews, so I wrote a quick little example using the chessboard.js library for visualization.

Link: http://queens.zolmeister.com/
Source: https://github.com/Zolmeister/queens

Here is a simple solution in JavaScript:
function solve(n) {
  var ans = []
  solver([])
  return ans
  function solver(current) {
    if (current.length === n)
      ans.push(current)
    else
      for (var i=0; i < n; i++) {
        for (var j=0, l=current.length; j < l; j++) {
          var prev = current[j]
          if (prev === i)
            break
          if (prev-(l-j) === i)
            break
          if (prev+(l-j) === i)
            break
        }
        if (j === l)
          solver(current.concat([i]))
      }
  }
}


My solution uses a technique called backtracking, which is basically depth-first search without an end condition. Note that I do not recommend the pattern above with a 'return' above a function, but it provides an interesting exercise for those who have never seen it before to understand JavaScript hoisting.

The algorithm moves left to right, placing a queen in the next available column. The key to the above code is the inner loop. This is what checks to see if a move is legal, such that no other queen on the board conflicts with the one to be placed. After that, it is simple recursion, with a condition that if the board is full then add it to the solution set.

No comments:

Post a Comment