Parallelizing N-Queens with the Intel Parallel Composer

In this article, we explore new and already existing parallel programming language extensions, directives, and libraries available in Intel Parallel Composer. The basic idea is to present the parallelism alternatives provided by Parallel Composer and show how to apply them to a given algorithm. The key questions we address involve how much coding is necessary to parallelize a given serial application and which mechanism are provided to benefit of threading with higher level constructs?

These new parallel methods are:

• OpenMP 3.0 directives
• New parallel extensions:
  • __taskcomplete
  • __task
  • __finish
  • __par
• Intel Threading Building Blocks (TBB) along with the lambda functions language extension

Each of these new methods provide C++ developers with a new range of scalability, performance, and usability for developing parallel applications not previously available in Intel C++ compiler products. To illustrate the use and performance of these new features, this article demonstrates how to use each method to implement parallel solutions to the N-Queens problem, which is a well-known programming problem that has definite solutions. This article describes using each of these parallel techniques, shows the code for each implementation, and compares and contrasts the utility and performance of each implementation. All code blocks and examples shown in this guide are taken from the actual code samples included with the Intel Parallel Composer.

1.1 N-Queens Samples

Included with this article are a collection of Microsoft Visual Studio project, solution, and C and C++ source files. The algorithm can be tackled by different approaches; for example, you can choose to optimize for speed or memory or both. Therefore, there are several different samples available. The samples illustrate different approaches and algorithms to solve the N-Queens problem

1.2 The Problem

The ultimate goal of the N-Queens problem is to find the total number of distinct solutions to place a given number of chess queens on a quadratic chess board with a specific number of squares on one side of a board (N) in a way that no two queens would be able to attack each other.

Two queens can attack each others when they are placed on the same horizontal row, vertical column or in one of (2*(2*n - 1)) possible diagonals. For example, on an 8x8 board, there are 92 distinct solutions. The difference between a unique and distinct solution is that distinct solutions allow for symmetrical operations, like rotations and reflections of the board, to be counted as one; so an 8x8 board has 12 unique solutions. Another interesting fact is that the complexity of the N-Queens problem increases exponentially. The world record at the moment is held for the solution on a 25x25 board. It was solved on a heterogeneous cluster around the world similar to the more popular Seti@home project and the cumulated computing time was over 50 years!

The number of solutions is: 2.207.893.435.808.352
Start date: October 8th 2004
End time: June 11th 2005
Computation duration time = 4444h 54m 52s 854 i.e. 185 days 4 hours 54
minutes 52 seconds 854

The results are from (http://proactive.inria.fr/index.php?page=nqueens25).

1.2.1 Problem Analysis

The most common approach is to use the brute-force approach, which is to simply test each position for each board size. Unfortunately, trying a brute-force algorithm by testing if every position on the board is valid will inevitably lead to a huge number of positions to validate (n²)!/((n²)-n)!; even for a 4x4 board the possible number of positions is 16!/12! = 43680.

Applying a heuristic approach by only allowing one queen per row reduces the problem size to a vector of n elements, where each element holds the position in the row and the number of possible solutions reduces to nn. This approach yields 256 positions a 4x4 board. You can reduce the number further by allowing for only one queen per column, which will result in a tuple of queens per column Q₁...Q_n) which reduces the number of solutions to n!: only 24 for our 4x4 board. You can review the problem of the 4x4 board to illustrate one possible solution. We start by placing the first queen in row 1, column 1, as in Figure 1.

Figure 1

Since there is no chance to place another queen on column 1, the next queen must be placed in row 2, with the first possible placement being row 2, column 3 (Figure 2).

Figure 2

Unfortunately, there is no way to place a queen on the third row so this placement is not a viable solution; therefore, you must try another column on row 2, in this case column 4, as in Figure 3.

Figure 3

The new position seems valid; the next placement might be row 3, column 2 (Figure 4).

Figure 4

Unfortunately, the new placement leaves no options for row 4. Starting over, one can place a queen at row 1, column 2 (Figure 5). Continuing the original strategy, place the next queen at row 2, column 4.

Figure 5

The new placement allows one to add a new queen in row 3, column 1 (Figure 6).

Figure 6

Finally, there is a possible solution because the new layout allows for another queen to be placed in row 4, column 3 (Figure 7).

Figure 7

There might be other solutions. Starting in row 1, column 3 and stepping through the placements again, one finds another solution that mirrors the first (Figure 8).

Figure 8

A check of other possible solutions should convince you that none exist, so there are two solutions on the 4x4 board. These are the only distinct solutions; how many unique solutions exist?

To answer that question, one must look for symmetry. If you section the board using dotted lines, and create mirror images reflected across the lines you might see another solution (Figure 9). There is only one unique solution as we can get the other one by reflection.

Figure 9

We could present the solution as a vector (v) of (n) values (for the rows). Every value contains the number of the column where the queen can be placed. For the original 16 squares (4x4) we have found: v[4] = [2 4 1 3] and [3 1 4 2]

1.2.2 Algorithm

To summarize, the most obvious approach to solving the problems was to add pieces recursively to the board trying to find all possible solutions. It is relatively easy to determine that we can add one queen in each column and look for solutions found based on the original placement of the first queen. The different solutions are independent from the solutions from the queens in the other columns.

This is an example of a tree search, because the algorithm iterates down to the bottom of the search tree once a queen is placed on the board. The search tree of the above example looks like this:

Figure 10

To code our approach, you must define conditions when queen (a) can be attacked by queen (b). First, you must deal with the cases where queens are in the same row or column, v[a] = v[b] here [4 x x 4].

Figure 11

Second, you must define the condition where the queen can be attacked diagonally. The difference of absolute row count and column count is equal, for a < b. Both queens can attack each other if they stay on the same diagonal. There are two possibilities: b-a = v[b] - v[a]

Figure 12

or b-a = v[a] - v[b]

Figure 13

We can combine both conditions to b-a = absolute value | v[a] -v[b] |. The resulting algorithm might look like the following in pseudocode:

Read board size: n
Set row to 1
Set v[1] to 0
while ( column > 0) do
[
  Find out a safe place in column where to safely place a queen
  if there is a location
    put v[row] = location
    if [row = n]
      [Write solution vector v[1 ... n]]
    end
  else
  if [row < n]
    go forward one line : row = row + 1
    set v[row] to 0
  end
  else do
  one column back : column = column - 1
  end
 end
]

Backtracking improves upon a brute-force search by building solutions step-by-step, and being able to discard a partial solution along with all solutions that would be built from it.

This works for the eight-queen problem; for example, if you start from an empty board and adds queens one-by-one, the moment you add a queen there is a conflict, and you can see that adding more queens will not remove the conflict; therefore, all solutions derived from that queen can be discarded without testing them.