Three Parallel Backtracking Designs | Dr Dobb's

Three Parallel Backtracking Designs | Dr Dobb's
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.

BOOL stillLegal(int *board, int r)

{

  BOOL safe = TRUE;

  int i;

  // Check vertical

  for ( i = 0; i < r; ++i)

    if (board[i] == board[r]) safe = FALSE;

    // Check diagonals

    int ld = board[r];  //left diagonal columns

    int rd = board[r];  // right diagonal columns

    for ( i = r-1; i >= 0; --i) {

      --ld; ++rd;

      if (board[i] == ld || board[i] == rd) safe = FALSE;

    }

 

    return safe;

}

In parallel, different tasks are going to need a private copy of the board and current partial solution to be examined. Otherwise you have a data race. The smaller data structure saves time and space in the parallel code because each new task generated from a call to NQueens() will use a copy of the current board to be used as a formal parameter.

Design 1: Every New Recursive Call Generates a New Task

void NQueensD1(int *board, int row, int N)

{

  if (row == N)

    handleSolution(board);

   

  else {

    for (int i = 0; i < N; ++i) {

      board[row] = i;

      if (stillLegal(board, row)) {

        // make copy of current board position

        int *bnew = new int[N];

        for (int j = 0; j <= row; ++j) bnew[j] = board[j];

#pragma omp task

        NQueensD1(bnew, row+1, N);

      }

    }

  }

  return;

}

all tasks ultimately do very little work in this implementation. The only thing a non-leaf task does is create new tasks for queens on the next row of the board, if there are any legal positions for a queen on that row. It takes time to create a task and assign that task to a thread. Since there isn't much computation in any task, the task creation time will be a large percentage of the work time. In other words, the overhead of creating the task will be high, let alone assigning it to a thread for execution. Since each task must have a private copy of the state configuration, there can be a large memory usage, too. Thus, any time spent allocating memory for a new current state object and copying relevant values is just more overhead that was not needed in the serial version.

Design 2: One task Created for Each Sub-Tree Rooted at a Particular Depth

void NQueensD2(int *board, int row, int N)

{

  for (int i = 0; i < N; ++i) {

    board[row] = i;

    if (stillLegal(board, row)) {

      if (row < LEVEL)

        NQueensD2(board, row+1, N); // go deeper in search tree

      else {

        int *bnew = new int[N];

        for (int j = 0; j <= row; ++j) bnew[j] = board[j];

#pragma omp task

        NQueens(bnew, row+1, N);   // generate task of serial function

      }

    }

  }

  return;

}

Design 3: Create a New Task for Each Child Node, But Only To a Certain Depth

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