November 06, 2009
Multicore-enabling the N-Queens Problem Using Cilk++Justin Zhang
The N-Queens problem asks this question: Given an n-x-n chessboard and n queens, is it possible to place the n queens on the chessboard without any conflict? Is so, how many different ways can they be placed? An arrangement is said to be conflicting if at least two queens conflict with each other. Two queens conflict if they share the same row, column, or diagonal. For example, the following is a solution for eight queens:
An excellent overview of the problem is available here.
Algorithm
The classical solution to N-Queens problem is brute force enumeration with pruning. Brute force enumeration tries every possible arrangement of the n queens and checks if any of them satisfies the non-conflicting criteria. For example, there are n^2 locations on the board, so there are n^2 possible locations for the first queen, n^2-1 for the second, and so on. Thus we have choose (n^2, n) = (n^2)!/((n^2-n)! * n!) possible arrangements of queens. By enumerating all of these possibilities and checking each of them, all solutions can be found. For n=10, this number is approximately 1.73e13.
Because there could be only one queen per row in a non-conflicting arrangement, we can constrain the first queen to locations in the first row, the second queen to the second row, and so on. This will give n possible locations for each queen, resulting in n^n possible arrangements. For n=10, this is 1e10. Observe that there could be one queen per column as well; the i-th queen will have only at most n-i+1 valid locations, because the previous i-1 queens already took I-1 columns. The number of possibilities is then reduced to n!, or 3.6e6 for n=10.
The final point to reduce enumerations is to prevent queens from sharing a diagonal. While this is straightforward to code, it is hard to provide an actual estimate of the number of enumeration after using it. The following is a pseudo-code for this enumeration plus pruning algorithm:
queens=[]; //locations of already put queens
try (int i) //put i-th queen
{
if (i>n)
{
found_a_solution;
return;
}
for j=1..n, //possible locations of i-th queen in i-th row
{
if (putting i-th queen at location (i,j)
does not conflict with previously put queens)
{
queens[i]=j; //store location of i-th queen
try(i+1); //put (i+1)-th queen
}
}
}
The complexity of this algorithm is upper-bounded by n!.
Implementation
I implemented the above algorithm in C++. Storing the queens array variable is a bit tricky. There were three choices before me: An STL vector, an array, or pointers. There are definitely other ways this could be implemented, such as using an array for space and bookkeeping pointers manually, but here I only considered these three basic cases. They each have their pros and cons:
All three choices were implemented. Before multicore-enabling them, their serial versions were built first. After all, it's always good to have the serial version of a parallel implementation at hand. In the following, the black code is the serial version, and the modification to parallelize them with Cilk++ are highlighted in blue.
Parallelizing a piece of code with Cilk++ is easy. What I mainly needed to do was to insert cilk_spawn before every recursive call, and cilk_sync before I used the return value from such calls. Also I needed to remove any data races. The two main tools I used were Cilkscreen (a data race detector), and reducers (race-free global variables provided with Cilk++).
The following are the three implementation. (The STL version is illustrated below, and the other two implementations are available by clicking on the links.) 
|
 |
|
|||||||||||||||||||||||||||||
|
|
|
