Three Parallel Backtracking Designs | Dr Dobb's

Three Parallel Backtracking Designs | Dr Dobb's

Before we get into the meat of this post, let me revisit the serial code I used for illustration last time. Specifically, I want to use a better method for recording queen positions.

Rather than keeping a 2D array that mimics a physical chessboard, I propose using an integer vector with length equal to the number of rows. The data stored in each element will be the column of a placed queen. This eliminates the chance that two queens will be on the same row, and the test for a legal position can simply search all lower indexed elements to see if those elements correspond to the same column (vertical attack) or are along a diagonal from the newly placed queen. If such a case is found, the newly placed queen attacks an already placed queen and stillLegal() will return FALSE since the position has no hope of leading to a legal solution.

It may seem like a "six of one, half dozen of another" situation, but having the simpler and smaller data structure to represent the current state of a partial solution will be a benefit to our parallel solutions. The simpler aspect is seen in the tests needed in stillLegal(). Checking for queens in the same column and testing the diagonal attack squares is easy, as seen in the code below. The positions of queens placed in rows "above" the currently placed queen are all that need to be examined. Any new move generated at the same level simply overwrites the previous column value in the vector and the test ignores any column values that are stored in higher indexed ("below") locations.

Read full article from Three Parallel Backtracking Designs | Dr Dobb's