Solving the N Queens puzzle via backtracking

mgcadmin 25-01-2022

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

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

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 n-12 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.