16.04.01 Eight Queens
The Problem
The problem to place 8 queens on a chess board such that no queen threatens any other is well known and solved. In this article I would like to show a solution where the problem is solved during compile time, resulting in an executable that prints only some constants determined at compile time. One queen would threaten another when she is located on a row, column or on one of the two possible diagonals where another queen is already located. A common approache to get one solution for the problem is to iterate over the rows of the board trying to place a queen in one column where no other queen is already placed at the same column or diagonals and see if it is still possible to place the rest of the queens on the next rows. This will be done recursively until all queens are placed on the board or it exposes that it is not possible to place all queens on the board. To check whether a column or one of the diagonals is already occupied by a queen, a bookkeeping structure keeps track of all columns and diagonals in use.
I have implemented this algorithm just using class and type declarations and some constant expressions. I have got the inspiration for this from reading the book 'Modern C++ Design' from Andrei Alexandrescu, so most of the basic ideas are not mine. While I tried to figure out how I could solve this I have learned a lot and had much fun. So I hope you will enjoy the solution I have found, even if there is a better one (I suspect there are some). As I now start to talk about nearly only static types, I will use the word 'type' frequently to remind us that I am talking about types, even if there are words like 'algorithm' in the text.
Some Tools
For the bookkeeping something similar to an array of booleans will be needed. With type lists like introduced in 'Modern C++ Design' one can build a generic list type with a specific set of items in it and some functionality to get a type with a specific item removed. In addition I will need some device to determine if an item in question is part of a the list. The generic set to build a list with a set of items itself can be implemented with a few templates:
template <int I>
struct item {
enum {id = I};
typedef item<I-1> next;
};
struct null {};
template <class H, class T>
struct node {
typedef H head;
typedef T tail;
};
template <int I>
struct set {
typedef node<item<I>, typename
set<I-1>::value > value;
};
template <>
struct set<-1> {
typedef null value;
};
The template 'item' is an item of the set created from a compile time constant integer value to give each item a different static type. The inner type 'next' can be used like an increment to find the item that follows on another item (while the value 'id' will decrement to make algorithms easier). The struct 'null' is a type to serve as a generic null for indication of list ends or empty sets. I will use it often. 'Node' is simply used to link two types together. The inner type 'head' will be an instantiation of 'item' and 'tail' another instantiation of 'node' or the type 'null' if it is the last type in the linked type list. Finally the template 'set' defines a linked list type of I+1 nodes by recursively declaring the inner type 'value' as a node with an item as head type and another 'set::value' with the template parameter decremented. To end the recursion and to get the type null into the tail of the last node, the template 'set' if fully specialized with a value type equal to 'null'. In addition one would get a resulting type of 'null' for an empty set (with I equal to -1). First the approache to remove an item out of a linked list:
template <class List, class Item>
struct remove;
template <class List, class Item>
struct remove<node<Item, List>,
Item>
{
typedef List result;
};
template < class Head,
class Tail,
class Item >
struct remove<node<Head, Tail>,
Item>
{
typedef
node<Head,
typename remove<Tail,
Item>::result
> result;
};
template <class Item>
struct remove<null, Item> {
typedef null result;
};
The template 'remove' takes an instantiated node type and an item to remove as template parameters. It declares a new type 'result' that will be another list but with the given item removed or will be the type null if the resulting list is empty. The compiler has to choose the first or the second specialization, depending on wether the head of the node is equal to the item to remove or not. In case that the head of the node is equal to the item to remove, the compiler has to choose the first specialization because it defines a specialization for the case that the first template parameter of the given node (the head) is equal to the second parameter of the 'remove' template (the type to remove). The result type is simply the tail of the node. If it was the last type in the list it would be just struct null. The second specialization handles all other cases where the first parameter is of type node and where head, tail and the type to remove are unrelated. Here the result is a typedef of a node with the same head type as the node passed to the template as a parameter and the original tail without the item to remove. Now again the compiler has to decide which of the first two given specializations is more appropriate to the tail of the list. Once the compiler finds the first specialization and removes the item, the typedef is complete. The third specialization applies for the case the list is empty or the type to remove is not part of the list.
I did not provide a complete type or default declaration for the remove template. I found two advantages to do so. The first is that you will find an error whenever you try to instantiate this template with another type than an instantiated node or the null type much quicker, because the compiler will report an incomplete type and not the missing of any type. The second advantage is that you can avoid typing the keyword typename too much because you will get all of the needed types from the template parameter list. A third interesting feature arises from this: this would work even if you deleted the head and tail types out of the node because these types are deduced from the specializations of the remove template.
Now to the second functionality (don't take that word too seriously, because we are still talking about static types): we have to determine if a given item is still in a list of available columns or diagonals:
template <class List, class Item>
struct inSet;
template <class Tail, class Item>
struct inSet<node<Item,Tail>, Item> {
enum { result = 1};
};
template <class Head, class Tail, class Item>
struct inSet<node<Head, Tail>, Item> {
enum { result = inSet<Tail, Item>::result};
};
template <class Item>
struct inSet<null, Item> {
enum { result = 0};
};
This is quite similar to the removal approach, but in this case the result is not a type but an integer constant. In the case the type is found in the given node, the constant will be declared to 1. Otherwise the declaration will be forwarded to an instantiation of inSet with the tail as parameter. That is nearly all what is needed for the bookkeeping. Further algorithms will need a structure to select one of two given types by a constant boolean expression. With this 'select' we can simulate something like branches to give the compiler a direction what template to instantiate next. This structur takes two types and a boolean. The default declaration has a typedef named result that points to the first type. A specialisation of that template for the boolean parameter to be true will define the type result to the second template parameter. The overall construct now defines a type 'result' that will be resolved to the first or the second template parameter whether the third parameter is true or false:
template <class A, class B, bool>
struct select {
typedef A result;
};
template <class A, class B>
struct select<A, B, true> {
typedef B result;
};
The Bookkeeping Structure
The bookkeeping structure is not a data structure in the common sense. It is still a type. It keeps a list for the columns not in use (or not threatened by a already placed queen) and the same information for both diagonals. All three type list types are passed as template parameters to the template. It defines three inner structs, each taking a row and a column as parameter. The first (calc_diag) calculates the diagonal threatened by a queen placed at the given row and column. The second (isValid) declares a constant boolean to true if it would be possible to place a queen with the given coordinates on the board without threatening another queen. The last algorithm (named 'use') declares a new bookkeeping structure that arises from a new queen placed. But in case it would not be possible to place another queen the resulting type will be declared as struct null. The last two algorithms derive from the struct 'calc_diag' to give an easier access to the values calculated by calc_diag.
To see if a queen could be placed on a specific square of the board, the latter algorithm have to check whether the used column or one of the diagonals is already occupied by another queen. Here we can draw our inSet tool out of the toolbox and apply it to the list of available columns and the lists of available diagonals to see if the comlumn and the diagonals the queen would threaten are still free. If so, the queen could be placed at this square of the board. The inner template 'use' declares a type named result. It will resolve to a new 'state' type with the new queen placement applied or to struct null if this placement is not possible. To decide whether this movement was legal or not, template 'use' uses the 'isValid' template and apply it as third parameter to the 'select' template (that was the device able to select a type of two given ones driven by a boolean expression). The first parameter to 'select' would be null and the second parameter the new state. The new state results from the original state by striking the used column and used diagonals out of the corresponding lists with the remove algorithm. The complete bookkeeping structure state is shown in the source. It also shows the declaration of the constant 'size' which defines the size of the board and the number of queens to place on it.
The Algorithm
Now to the algorithm to find a solution to the eight queens problem: The initial state type starts with all columns and diagonals are marked available. Now we can see if we will find a solution to the problem if we try to place the first queen in the first column of the first row and to apply the algorithm recursively to see if we can place the remaining queens on the rest of the rows. If it was not possible to place the remaining queens, the next column will be tested. In case that it is not possible to place the first queen somewhere in the first row there will be no solution for the problem at all. But in case there is a place to put the first queen on, the entire solution is found, because the recursive apply to the algorithm to check if it's possible to place the remaining queens one the rest of the board evaluates the rest of the solution. I call the template to solve the problem 'solution'. It takes the bookkeeping type and a starting column and row as parameters and is defined like this:
template <class State,
class Column,
class Row>
struct solution { ... };
The first part of the class definition declares a new state type by applying the column and row passed as parameter to the state that was passed :
typedef typename
State::use<Column, Row>::result
newState;
typedef
solution<newState,
item<size-1>,
typename Row::next>
tryNextRow;
typedef
solution<State,
typename Column::next,
Row>
tryNextColumn;
The both other typedefs a instantiations of the 'solution' template. The first one is the solution that would result from placing a queen here and going ahead with the next row. The second one is the solution that would would be found from sticking to this row and trying to place the queen on the next column. Now we have a new state and two new maybe solutions. The template has now to evaluate if it is possible to place a queen at the given coordinates with the given state and if it is possible to place the rest of the queens on the remaining rows or if the template 'solution' has to find a solution by trying to use the next column:
typedef typename
State::isValid<Column, Row>
checker;
enum {
thisValid = checker::result };
enum { useNextRow = (thisValid
&& tryNextRow::isValid) };
typedef typename
select<tryNextColumn,
tryNextRow,
useNextRow>::result
nextStep;
enum { isValid =
nextStep::isValid};
enum { row = Row::id };
enum { column = Column::id };
The constant thisValid checks if it is possible to place a queen at this Row and Column. If we could place a queen here and it is posible to place the rest of the queens on the next rows the constant useNextRow would be true. The 'select' template selects tryNextColumn or tryNextRow to be the next step the compiler has to go depending on wether this constant is true or false Finally the whole solution is valid (the value of the constant isValid) if the next step is valid too. The both constants 'row' and 'column' at the end of the definition are for output purposes. In addition there are a lot of specializations for the solution template to mark the end of the recursion and one to mark a successful end of the algorithm. For all of these specializations the type nextStep is defined as struct null and for all but one the constant isValid is set to false. It is set only to true for the one that marks the successful end of the algorithm. The successful end of the algorithm is found if it was able to place a queen on every row.
Finally some executable Statments
Now we found a solution with an instantiation of the solution class template. Every step the algorithm went is now recorded in the next instantiation of the solution template named 'nextStep'. For the last step the 'nextStep'' typedef is struct null. For printing the solution on the screen something like a loop has to be used. But now we have to use a real loop not only cyclic type definition. Using an integer for loop control would not work because one cannot index a type. And using a pointer would be pointless, because one cannot point to a type. For now almost only class templates and specializations of them was used. A similar approach can be used to build a loop too. But this time inheritance is used to build a loop and it will be unrolled by the compiler so that no variable for loop control will be needed:
template <class Solution>
struct queen : queen<
typename Solution::nextStep>
{
queen() {
// prints Solutions row, column
}
};
template <>
struct queen<null> {
queen() {
std::cout<<"Result:";
}
};
This class 'queen' instantiated with the instantiated 'solution' found, will result in a class that will print the solution on the screen in it's default constructor when instantiated. The output in the constructor looks indeed a little bit more complicated (but only a little bit, if you are still with me up to this point) because not on every step the compiler took to solve the problem there was a queen dropped at the board. This whole definition of struct queen and the main function is shown in the source.