# 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 0-1 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)); }

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 = row-1, dy = col-1; while (dx >= 0 && dy >= 0) if (cb[dx--][dy--] == 1) return false; dx = row-1; dy = col+1; while (dx >= 0 && dy < cb.size()) if (cb[dx--][dy++] == 1) return false; return true; }

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; }

Solution Found! - - Q - - - - - - - - - - Q - - - - - Q - - - - - Q - - - - - - - - - - - - - Q - - - - Q - - - - - - - - - Q - Q - - - - - - - valid solutions found so far: 92

## Leave A Comment