Solving the N Queens puzzle via backtracking
Using the algorithmic technique of backtracking to solve the famous N Queens chess puzzle.
The N Queens Puzzle
The N Queens puzzle comes to us from the world of chess, prior to the advent of computers it was a logical puzzle played by chess enthusiasts. Its stated as such: Given an NxN Chessboard, how many ways, if any, can N queens be positioned so that no may queen may attack another? This translates to placing the queens so that their is no other queen in the same row, column, or diagonal spacing of the chess board as the one being placed. On a standard chess board this requires placing 8 queens on an 8x8 board. It becomes quickly apparent that the number of possible configurations is a HUGE number.
Searching for a solution
We could simply take 8 queens and try placing them in every single combination possible. This is whats called a "brute force" solution, and is HORRIBLY inefficient, though there ARE cases when such a solution is the only possible solution, thankfully this is not one of them. This type of puzzle is a constraint satisfaction problem of the optimization variety similar to the 01 knapsack problem, the traveling salesman problem, and many others. It can requires the analyzing the board in various states to see if the current state of the board satisfies the criteria, or "constraints" imposed upon it to be considered a valid solution. Thus this is also a searching problem. But what are we searching? The answer is that we are searching whats called a state space tree. The above mentioned brute force solution is whats called an "exhaustive search" and thankfully there have been methods devised to make our exhaustive search a little less, well, exhaustive. The de facto technique employed for solving the n queens puzzle is to use the algorithmic technique known as backtracking, which will be the focus of this article.
Backtracking
As I mentioned above, the n queens problem can be looked at as a searching problem, where search through the different configurations of the board. This is called a "state space" search. We can think of the different configurations as we iterate through each placement as a node on a tree with the the leaves of the tree being the complete configuration. To examine each and every possible state would be the aforementioned "exhaustive search". While searching for the solution that satisfies the constraints that we have specified, we are in fact performing a preorder depth first traversal of the tree, albeit in an abstract manner. To avoid having to perform an exhaustive search we "prune" the state space tree as we traverse it. This is accomplished by gauging our progress at each node, and if we encounter a local condition that violates the constraints, we know that we nolonger need to continue along this path of the tree, and can thus "backtrack" to the previous node and traverse along a neighboring path instead. Following the convention established in "Foundations of Algorithms" by Neopolitan et. al. we employ whats called a "promising" function. Implementing the depth first traversal in a recursive method allows us to implement the backtracking algorithm in a straight forward fashion: A very high level psuedocode for the backtracking technique looks like this:
function check_node(node current) If a solution has been found Then print the solution else if check_promising(current) Then for each child of node current check_node(child) else backtrack. function check_promising(node current) If current node meets local constraints return true else return false
Solving the N Queens puzzle with Backtracking
Now that we know what the backtracking algorithm is and have a technique for solving our puzzle, the next step is to implement it. A simple way to represent the chess board is as a 2 dimentional array of integers, with a 0 representing an unoccupied space, and a 1 representing a queen.
typedef vector<vector<int>> ChessBoard;
void init(ChessBoard& board, int n) {
board = vector<vector<int>>(n, vector<int>(n, 0));
}
The next step is to develop our promising function. We established above that each queen we place cannot threaten any other queen on the board, meaning that for each queen placed, it can not share a row, column, or diagonal positioning with another queen. Armed with this knowledge we can develop a function to check if a given position in the array satisfies those conditions so far:
bool promising(ChessBoard& cb, int row, int col) {
for (int y = 0; y < cb.size(); y++)
if (cb[row][y] == 1 && y != col)
return false;
for (int x = 0; x < cb.size(); x++)
if (cb[x][col] == 1 && x != row)
return false;
int dx = row1, dy = col1;
while (dx >= 0 && dy >= 0)
if (cb[dx][dy] == 1)
return false;
dx = row1; dy = col+1;
while (dx >= 0 && dy < cb.size())
if (cb[dx][dy++] == 1)
return false;
return true;
}
With the ability to check each node on the path in place we then develop the traversal function its self:
bool solve(ChessBoard& cb, int row) {
if (row == cb.size()) {
printBoard(cb);
return true;
}
for (int i = 0; i < cb.size(); i++) {
if (promising(cb, row, i)) {
cb[row][i] = 1;
if (!solve(cb, row+1))
cb[row][i] = 0;
}
}
return false;
}
If we compile and run the above program, we will be presented with all 92 solutions to the 8 queens puzzle, One such solution looks like this:
Solution Found!   Q           Q      Q      Q              Q     Q          Q  Q        valid solutions found so far: 92
Wrapping up
The above program will find valid solutions for any valid of N that solutions exist for. As N increases, the valid solutions explodes. But with the larger the state space to search, the slower the algorithm will become, despite the large number of valid solutions. The above program will find all 92 solutions to the N Queens puzzle practically instantly, likewise with the 14,200 solutions to the n12 puzzle. I have yet to let it run N 16 or N 24 to conclusion, though i have used it to find several thousand solutions for each. Finding even ONE solution to the N 32 puzzle takes quite a bit of time. Backtracking is not the only way to solve the N Queens problem. As backtracking is a depth first search, there is a breadth first solution using a very similar technique called branch and bound, But thats a topic for another article.

A Different Take on Merge Sort: Binary Search Trees?

Deleting Entries From OpenAddress Hash tables

Transform any Binary Search Tree in to a Sorted Linked List

From Regular Expressions To NFA by way of Abstract Syntax Trees: Thompsons Construction

Extending Sedgewick's explicit Digraph NFA

Iterative Inorder B Tree Traversal

Simple DB Migration with JDBC

Welcome to CodeBlahger, A Blahging Platform for Programmers.

The Façade Pattern

The Interpreter Pattern: Implementing Interpreters the OOP way
Leave A Comment