Channels ▼

Clay Breshears

Dr. Dobb's Bloggers

Backtracking for Fun and Profit

November 22, 2011

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.

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 


Video