Fighting Queens Problem

This week, my Programming Languages class has been covering the fighting queens problem, which is based on queens in chess. In chess, queens can move diagonally, vertically and horizontally as far as they would like. The solution to the problem is to find an arrangement of queens such that no queen can move into the same spot as another queen. Another way to think of this is to have no queens on the potential paths of any other queen. For example, a valid configuration of queens is shown as well as an invalid configuration.

   Valid Configuration                                Invalid Configuration

The goal of this week is to program a way to find every valid configuration for any size of board. However, we have to accomplish it in two ways. The first way is using an imperative language, in this case C++. Imperative languages require the developer to implement the logic behind how the solution is calculated. The second way is using a declarative language, in this case Prolog. Declarative languages simply require the developer to say what he or she wants and the language handles how that information is found. For example, if the developer wanted to use an imperative approach to calculate the sum of even numbers between one and nine, he or she would need to first determine a way to see how a number is even, then select only the even numbers, then add them together. If the developer wanted to do the same thing with a declarative language, he or she would simply say sum the numbers between one and nine when the number is even.

In order to implement the fighting queens problem in C++, it is very easy to implement the naïve, or brute force, method. This method generates every possible board configuration then checks to see if it is valid. This works well for small boards but isn’t very good for large boards. This is because of how quickly the number of possible configurations of boards increases. On a 1-by-1 board, only one configuration is possible. On a 2-by-2 board, there are six configurations. On a 3-by-3 board, there are 84 configurations. On a 4-by-4 board, there are 1,840 configurations. Clearly, as the size of the board increases it becomes less and less feasible to check all the configurations. Implementing a method to reduce the number of boards to be checked can be done using an approach called backtracking. Implementing backtracking is very hard, though, so instead of implementing it ourselves in the imperative C++ we can use the declarative Prolog instead. Prolog already has backtracking implemented, so we just need to write a statement that tells Prolog to find all possible valid configurations of the board.