Unit 25: N Queens
Learning Objectives
After taking this unit, students should
 be familiar with using recursion to search and prune the solution space to a problem
 be familiar with the class N queens problem and its solution
Searching and Backtracking
We now look at how recursion can help with solving problems that require searching and backtracking. A classical example for this is the \(n\)queens problem, which can be stated as given a \(n \times n\) chessboard, find a possible placement of \(n\) queens on the chessboard, such that the queens do not threaten each other. In other words, there is exactly one queen in each row, in each column, and each diagonal. The 8queens puzzle was first published by Max Bezzel in 1848, with the first solution published Franz Nauck in 1850. The generalized \(n\)queens problems were introduced later. It is known that there is no solution for \(n = 2\) and \(n = 3\), but a solution exists for \(n > 3\).
If we visualize the chessboard as a 2D array, with #
as the position of a queen, and .
as an empty position on the board, then a solution to the 4queens problem looks like this:
1 2 3 4 

Recursive Formulation
Let's see how we can formulate the problem recursively. The first step is to simplify the problem to the most trivial case where we can solve it. It is tempting to say that a simpler version of the problem is an \(n1\)queens problem, and so the most trivial case is 1queen. While the solution to 1queen is trivial, there is no solution to both 2queen and 3queen problems. Further, if we have found a solution to the \(n1\)queens problem, extending it to a solution of the \(n\)queens problem is not trivial.
Generate All Permutations
As a start, let's borrow the idea from Unit 24 and generate all permutations of the queens' positions. Let's label the columns a
, b
, c
, .. etc. Since we know that there must be exactly one queen in each row, and one queen in each column, the positions of the queens can be represented as a string that is a permutation of abcde..
. For instance, the solution of the 4queen problem depicted above can be represented by bdac
.
1 2 3 4 5 

A simple algorithm is thus to generate all possible \(n!\) permutations, and for each one, check if it is a valid placement. We already ensure that there is exactly one queen per row and one queen per column. It remains to check that the queens do not threaten each other diagonally.
Let's write a function that checks, given a string representation of the queen positions, whether there is any queen that threatens another or not:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 

Solving the \(n\) queens problem is then easy. We simply generate all permutations, which correspond to all possible placement of the queens. For each generated permutation, we check if it is a valid placement, i.e., if two queens threaten each other.
The code below prints out all possible solutions to the \(n\) queens problem.
NQueens Solution: Version 1  

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 

Line 13 above is the key difference between this and permute
from the previous unit. We added an extra condition to check if the placement of queens is legit and only print out the answer if it is.
Stopping at the First Solution
We can easily change the code above so that it stops upon finding the first solution.
NQueens Solution: Version 2  

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 

We modify the function so that it returns true
upon discovering a valid placement (Line 16) and false
otherwise (Line 18). On Line 2324, we only continue our loop if the current search does not return true
. Otherwise, a valid placement is found, and we return from nqueens
at Line 24. If we reach Line 28, then this means that our search is fruitless, and we return false
.
Backtracking
The search process above mirrors the process in which we generate all possible permutations. We first fix the placement of the queens on the top rows. Essentially, we attempt to see if this placement can lead to a valid placement of queens on all rows. If we are successful (nqueens
return true
), then we are done. Otherwise, the current placement that we attempted is a mistake  we thus backtrack on our decision and try a different placement.
For example, in the figure above, we first try placing the first queen on the first column (i.e., all permutations that start with a
). Recursively searching for all possible placements that start with a
fails to yield a valid 4queen solution. We backtrack on this decision and try to place the first queen on the second column b
(which eventually leads to a valid placement bdac
).
Backtracking can be done simply using recursion  the recursive call stack remembers our past decisions for us, and returning from recursive calls serves as backtracking, without us explicitly doing so.
For instance, Line 22 attempts a possible placement of queen on Row row
, and if it fails to yield a solution on Line 23, the code backtracks and attempt another possible placement in the next loop.
Making It Faster: Pruning Impossible Solutions
One of the principles of writing efficient code is to avoid doing useless work. The code above, which tests all permutations, actually generates much useless work. Suppose the queens in the first two rows already threaten each other, then, there is no need to continue to generate all possible placements of queens for the remaining rows.
For example, in the figure below, there is no need to generate any permutation with the prefix ab
. Placing two queens in these two positions lead to invalid solutions, regardless of where the rest of the queens are.
We can thus avoid searching through possibilities that we know are not useful. This concept is called pruning and is a key to speeding up many searchingbased solutions. We want to prune away bad solutions as early as possible. This can be achieved easily, by checking if the queens already placed on the first \(k\) rows threaten each other.
The code below extends Version 2 of NQueens solution by adding a condition to prune impossible solutions on Line 22.
NQueens Solution: Version 3  

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 

Adding this condition can speed up the code significantly.
Such an algorithm is also known as a branchandbound algorithm, where we attempt different possible solutions and prune away partial solutions that we know will never work. This is an important concept in artificial intelligence (AI). In fact, the nqueen problem is a typical example used in introductory AI courses for branchandbound search. Again, such solutions are more naturally expressed recursively.
Problem Set 25
Problem 25.1
In the code with pruning above, we check if the queens placed on Rows 0 to row
threaten each other, and call nqueens
recursively only if these queens do not threaten each other. Identify the repetitive work being done in the calls threaten_each_other_diagonally
, and suggest a way to remove the repetitive work.
Problem 25.2
Consider the code to generate all possible permutations of a string from Problem 24.1. Suppose that we restrict the permutations to those where the same character does not appear next to each other. Modify the solution to Problem 24.1 to prune away permutations where the same character appears more than once consecutively.
Appendix: Complete Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 
