Solving the n-queens problem
The “eight queens puzzle” is a well-known problem, in which the goal is to calculate how many different ways 8 queens can be placed on an 8 x 8 chessboard, such that none of them are threatening each other (meaning — none of them occupy the same row, column, or diagonal, such that one could capture another in one move).
The eight queens problem is an example of the more general “n-queens problem” — the problem of finding the number of valid solutions for placing n queens on an n x n sized board. Note that the n represents the same number in both cases — the number of queens must be the same as the number of rows/columns on the board.
It’s an interesting problem, in that the results do not scale entirely predictably with the size of n. For n=5, there are 10 possible solutions. For n=6, there are only 4. For n=7, we can find up to 40 possible solutions! This makes it much more interesting than the equivalent problem with rooks, in which the number of solutions can be easily calculated as n!, and therefore increase quite predictably as n grows.
The Brute Force Method
One way to solve this would be a “brute force” calculation of every board position. We could start on the top-left corner (a8, I believe, in chess-people parlance), and place a queen there. Our goal, then, would be to exhaust every possible state of the board that involves the first queen in that top-left corner before moving on. We would therefore find the first possible place to put the second queen. Continuing to place queens, we would test every possible state of the board in which the second queen is in that position (and the first queen in the top-left corner), before moving the second queen to the next possible position. Once we have tested every possible combination for every possible placement of the second queen, we could finally be confident that we have tried every combination that involves the first queen in her top-left-corner spot. We could then move the first queen to the second spot on the board and, in the same manner, test every possible combination that involves her in that new spot. We would keep a running tally of every time we found a valid solution during this process, and at the end we would know how many possible states of the board represent a possible solution.
This strategy for brute-force problem solving has a recursive “backtrack” feature that is worth noting and remembering. First, we scan the board for the first valid placement of a piece. Then we place the piece, and recursively call the same operation on the new state of the board. Once that recursive call has returned and found any valid solutions, we remove the piece we just placed, and find the second valid placement for it. This pattern of making a move, having a recursive call, and then reversing the move, is a strategy that can be used to solve a variety of problems, and is one way to solve the coin problem.
It should not surprise you that this could take a very long time for large values of n. Depending on the how it was implemented, we might be testing up to (n * n)^n combinations. But there is an even worse problem with this approach — if implemented as stated above, it will produce duplicate solutions. If there were to be a particular solution that involved queen 1 (Q1) in spot a8 and queen 2 (Q2) in spot b6, we would later stumble across an equivalent solution that involved Q2 in a8 and Q1 in b6. Put another way, we would be testing for permutations, instead of unique combinations. We would therefore have to keep a record of which solutions we had found so far, so we could discard any that were duplicates.
We could save ourselves a lot of trouble if, instead, we simply had an algorithm that would not produce duplicate solutions in the first place. Actually, if we had that, we wouldn’t even need to keep track of what the solutions were, we could simply count them up as we came across them, and safely forget the particulars of what each one was.
Indeed, this can be achieved by a slight tweak in the above algorithm. If we mandate that the second queen be placed somewhere after the first (meaning either in a lower row than the first or in the same row but in a column further to the right), and that the third queen be placed somewhere after the second, we can guarantee that we will not produce identical combinations. This will also save our algorithm a good deal of time.
Another, slightly better, brute force method
The above strategy will work, but there are yet more efficient ways to solve this problem. The fact that the number of queens is the same as the number of spaces on the chessboard gives us a distinct advantage. Since there are only n rows and n queens, it follows that there will be exactly one queen on each row in a valid solution. If there were two queens on a row, they would be threatening each other, and we could not produce a valid solution. If there were any row empty, it would follow that we would have to fit all n queens into the remaining (n — 1) rows, which would mean two queens would be forced to double up on a row, which they cannot do. It follows therefore that we cannot have a valid solution with any empty rows (the same is true of columns, of course, so feel free to read the following reasoning and mentally switch ‘row’ with ‘column’, if you are so inclined).
What is nice about this is that it means every row will have a queen. This means that, for our first queen, we do not actually need to check what will happen if we place her in every single position on the board. We can effectively assign her to the first row, and check every possible combination that involves a queen in the first spot on that row (a8), every possible combination that involves her in the second spot (b8), etc. Once we have finished checking every combination with that queen on every spot in the first row (a8-h8), we will know that we have checked every combination that involves a queen in the first row. Since we know there are n0 combinations that don’t have a queen in the first row (remember — no empty rows!), we can conclude we have checked every possible unique combination of the board.
Similarly, imagine we have already placed our first queen in the first row, and we want to check for any possible solutions that involve her in that spot. Where should we start looking for a place to place our second queen? We can skip the first row this time and start looking for any spots on the second row. Since we know every row needs a queen, we might as well assign this queen to the second row, and whether we do or don’t find any good spots for her on the second row, we shouldn’t bother trying moving onto combinations that leave the second row empty (since, again, no row can be left empty). If we have checked every combination with a queen in the first row and a queen in the second row, we will know we have tried every valid combination and found every valid solution.
The short of this is that we should assign each of our n queens to each of the n rows. Instead of checking if every piece can be placed on every spot on the board, we can check for every combination that involved Q1 in row 1, Q2 in row 2, Q3 in row 3, and so on. This already narrows the number of combinations we need to check to a maximum of n ^ n. We do not need to check what would happen if we place Q2 in row 3 and Q3 in row 2, because checking for such things will only produce duplicate/equivalent board states. By assigning Q2 to row 2 and Q3 to row 3, we guarantee that such duplicate states cannot occur.
Implementing the algorithm
Now, imagine you were attempting to implement this solution in your programming language of choice (feel free to consider using PowerPoint or Super Mario World). You might keep a representation of the board in memory in the form of a two-dimensional array, and mark occupied spots with a 1, and vacant spots with a 0. This is not the optimal solution (as will be discussed in a later post), but it will work well.
You would also need a function to check for conflicts. This would be a simple matter of checking if placing a queen in a space would place it in the same row, column, or diagonal as any other queens. The diagonals here are trickiest, because there are more of them than there are rows and columns, and there are both major (top-left to bottom-right) and minor (top-right to bottom-left) diagonals.
You could then define a function (that will be called recursively) that takes the current state of the board as an argument, as well as the next row on which to place a queen (we will necessarily only call it on the next empty row). It would look through each spot on the current row, and if it would not cause any conflicts, place the queen in each spot, and for each spot, recursively check the next row for any valid solutions that involve the queen in that spot.
We would also, of course, keep track of any time we find a valid solution. Since we are checking for invalid placements as we go, anytime we find ourselves successfully placing our nth and final queen on our nth and final row, we know we have reached another valid solution, and can increment our solution count.
The pseudocode for this would look something like this: