# 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.