The second way the function knows to make no further recursive calls is decided by calling stillLegal(). This Boolean function is called after a queen has been placed in the row row and column i position of the board. If this newly placed queen does not attack any other queen previously placed on the board, then the function returns TRUE; otherwise, the placement of the new queen has violated the rules of the problem and a value of FALSE is returned.

Notice that the for-loop will run over all possible column positions for a queen within any given row. Also, regardless of whether or not NQueens() is called, the queen placed in the board[row][i] spot is removed by overwriting the 'Q' with a blank character.

A visualization method that I use for backtracking solutions is to think of the search space as a tree. At the root is the initial start position of the problem. Child nodes of any parent represent the application of a move from the partial solution state of the parent and the leaf nodes will be a complete partial solution. For N-Queens the initial state is the empty board, a node at level M < N is a configuration where M queens have been placed in the top M rows, and leaf nodes have N queens, one per row, placed on the board. Each non-leaf node will have N child nodes, one for each column in the row below.

Obviously, many of the nodes in such a tree will be illegal positions (and all nodes spawned from those nodes will also resolve to invalid solutions). However, with the tree structure in mind, I imagine the backtracking algorithm as a kind of depth-first graph search that can eliminate whole sub-trees from consideration when the root of the sub-tree is found to violate the conditions of the problem. Whenever a child node and the sub-tree rooted at that node has been completely searched and/or resolved, the backtracking algorithm searches the sub-tree rooted at the "next" sibling node. In the case of N-Queens, this "next" sibling will be the next column in the current row being considered. If all sibling nodes have been examined, the parent node has been completely searched and a sibling of the parent will be next to be processed.

I bring up this tree visualization to show that backtracking can be an excellent candidate for parallel execution. The evaluation of any two different nodes in the tree can be done independently. If one node is a direct ancestor of the other, there will be some coordination issues, but we can easily sidestep this issue in how we assign nodes to be processed to threads. To execute in parallel, each node evaluation can be encapsulated into a task that will be executed by some thread within a thread pool.

With regard to executing the backtracking algorithm with task parallelism, there are three different design choices as to where to insert parallelism. These are:

1. Every new recursive call generates a new task
2. One task created for each sub-tree rooted at a particular depth
3. Create a new task for each child node, but only to a certain depth

In my next post, I'll look at how to apply each of these three designs to the NQueens() code and look at the potential performance issues of each.