Recently we just completed a sprint at Hack Reactor tackling the classic n-queens algorithm problem, and during that process I found a great 'alternative' way to approach the problem, courtesy of a post by former Hack Reactor student Kevin Smith.
In the end, my pair and I ended up taking a more traditional solution that recurses over a matrix-structured board, but Kevin's post presented a great leftfield option and a solid mental exercise.
However, as someone fairly new to computer science I at first found his code a bit difficult to parse, and had to read through it a number of times before it 'clicked'. This post is designed to go into a bit more explanations on what's going on here.
If you're not familiar with n-queens, the prompt is as follows:
Find the number of solutions to fit a number 'n' queens onto a chessboard of n x n size such that no queen attacks any other
There's a subset of this problem known as 'n-rooks', in which the rules are essentially the same as the above , but the rook has a simpler attack pattern, which allows you to more easily test for a given solution.
We'll cover that here, as it's the 'interesting' part of Kevin's solution.
For this prompt, we're visualizing a chessboard of n x n dimentions. Normally we visualize it like this (in the case that n = 4):
[ 0 0 0 0 ] [ 0 0 0 0 ] [ 0 0 0 0 ] [ 0 0 0 0 ]
Essentially, this is an array of arrays, and thus a "two-dimensional array"
Placing pieces on this board would result in the
0s at those locations getting replaced by
1s, like so:
[ 1 0 0 0 ] [ 0 0 1 0 ] [ 0 1 0 0 ] [ 0 0 0 1 ]
In many considerations of the n-rooks problem, you'd iterate through the arrays here, row by row, looking for conflicting piece placements.
But what if we could represent this differently?
An essential piece of information to know here is this:
We can at maximum place one rook at each column
Why is this? Because rooks can attack in any straight line, horizontal or vertical. If any rook were to be placed in the same row or column as another, it would have a clear path of attack, and therefore is not a successful solution for this problem.
Given this, it turns out, we can actually reduce our chessboard above down to a single dimension array:
Here, each position (index) in the array represents one row of the grid in the previous example, and each number found at that index represents the column placement of a rook on that row.
Now that we have this single dimensional array, we can create all the permutations (different board configurations that could be created) quite easily. In Kevin's example, he successively iterates over the array, branching recursively at each step to check possible combinations. This is made quite easy by our 1D array - basically, we just append a rook at each column position per step, and then test the resulting options.
Testing the options
Here's where things get cool. Since we have the constraint that no two pieces can occupy the same column, we can safely say that the same number (representing rook column position), cannot appear in the array more than once:
[ 0 2 3 1]
is valid but
[ 1 2 1 3]
is not, as the rows #0 and #2 have rooks in the same column.
This allowed Kevin a test that I had to read through a few times to understand - he used the Underscore.js library's 'uniq' function to reduce each array down to only unique values (ie, removing any duplicates), then compared the resultant array's length to the original's. If they were of different lengths, it meant that this was not a valid board, and could be thrown out; if they were the same, keep testing, and/or push to our final results.
Pulling it all together
Once we have iteration and tests complete, it's just a matter of counting valid boards.
Note that at this point, we're also well on our way to solving n-queens -- all we need to do is test for diagonal conflicts (hint - it's still totally doable with this 1D array).
In typing this, the simplicity of using a 1D array to solve these problems, and I'm almost embarrassed to admit that it took me a few readthroughs. However, my hope is that some others can use this post to help to clarify what went on in Kevin's solution!
Our final code for n-rooks follows: