nQueens – Part 2 – Implementation
Last time we discussed the problem of nQueens and the general logic used to create our algorithm. We are now going to take that solution and implement it in code.
Before we were talking, human to human. We do this a lot, so it’s much easier to get ideas across. Now we will be talking human to computer, which is a bit more difficult, they lack the ability to deal with ambiguity. Which means we need to be more precise, and explicit; both in speech and thought.
Lets take a look at our current logic, though for the sack of less drawing, we are moving from a board of 5×5, to a board of 4×4. Lets review our logic so far.
- Pick an available number from the column array, and pick one from the row array.
- Check the major and minor arrays. C + R = Major index , C – R + 3 = Minor index. (C for column number, R for row number. We are adding 3, to make the minor index 0 based.)
- If you get a (o) when you check the major and minor arrays, you are good to go. Place a queen at that chosen spot. Then remove the chosen numbers from their respective column and row arrays. Then mark major and minor arrays as taken (x) at the spots you checked. Section 1 has a more detailed walk-through of this.
Let’s see how this looks on a 4×4 board.
Step 1: Our empty board, all choices are available.
Step 2: We chose 0,0 as it was the first available spot, no conflicts. We took 0 out of both the Row and Column arrays. We also marked the spots taken in the Major and Minor arrays.
Step 3: You’ll see that the first thing we tried, was to place a queen at [1,1]. This was because the numbers were available to us, so we tried it. We then did a lookup in the Major and Minor array, and found there was a conflict with the Minor array, so we moved onto the [1,2] where we placed our second queen.
You’ll note that we no longer have a valid board. There is only 1 available slot and we need to place 2 more queens to have a valid solution. What do we do now?
As a person I’m sure you would say,”Ummm, I guess we try some different spots?” You, person, are totally right. We try some different spots. But how would we tell a computer this? Also since computers are fast at this kind of problem, how do we tell it to try EVERY possible spot, then tell us which ones work.
Lets try some plain language logic for this. We have a good starting point, Step 1, an empty board. With a bit of trial and error, it turns out that for a 4×4 board, there is no solution that involves starting a piece at [0,0]. That means we should step back to the empty board, and try the next possible spot, [0,1] and go through again.
Above, you can see our logic laid out in a branching fashion. For this first iteration I’ve laid each choice to match it’s row:column value. Diagrams laid out like, because of the branching, are often called trees. Get it? Branches, trees. Yeah, you get it. If we were to fill the above diagram out fully, the [0,0] circle would have one more child node, [1,3]. [1,3] would have no valid children.
I’ve changed the positioning a bit, to reflect a more typical tree data structure. The [1,3] choice is also shown. Clearly [0,0] is a dud, we must move onto [0,1].
After choosing [0,1], our first 2 child options end up having diagonal conflicts. The third one, however, was just right. Each successive choice in our algorithm also proves to be valid, and we now have one functioning board that satisfies the nQueens requirements. Awesome!
A successful board
Any time you see data branching, as we did in the above node diagram, that problem is a good candidate for recursion. If are comfortable with recursion, then hopefully this post was useful to you by visualizing the flow of data. If you do not know what recursion is, you should google around for resources on it. But before you do, be confident knowing that what we walked through in this post and the previous one, was recursive. If you understood what we’ve said, you can grasp recursion just fine.
That’s all well and good, but what about some code?
Here is my decently commented solution. I solve it using ‘recursion with side-effects.’ Which just means that there are a few variables that each recursive call can all see, and they can all modify.