0

I'm trying to write a parallel version of a brute-force algorithm for solving Sudoku.

The serial algorithm is the following, in pseudo-code:

solve(matrix, x, y):
    for i in [0,9]:
        //If test number fits rules
        if(valid(matrix, x, y, i):
            matrix[y,x] = i
            //Try next cell recursively
            if(solve(matrix, nextEmptyX, nextEmptyY)) return true
            //test number not the solution, backtrack.
            matrix[y][x] = 0
 return false;

I apologize if I made a mistake in this pseudo-code, but I think it's correct. Either way, my serial algorithm works.

The problem is when I try to paralelize it like this

solve(matrix, x, y):
    for i in [0,9]:
        if(valid(matrix, x, y, i):
            val = 0
            #pragma omp task firstprivate(x, y, i, matrix, val)
                copy_matrix = copyOf(matrix)
                copy_matrix[y][x] = i
                val = solve(copy_matrix, nextEmptyX, nextEmptyY)
                if(val) print_matrix
            if(val) return true
            matrix[y][x] = 0
#pragma omp taskwait 
return false;

In my mind this code should try each tentative value for each cell in a new task, and at least one task should have the correct solution. But when I run it, it doesn't test every combination of (y,x) (it actually seems to only test the first row of the matrix and it doesn't find the result.

I'm calling like this:

#pragma omp parallel sections
    {
            #pragma omp section
            solve(matrix, 0, 0);
    }

This is true even for a single thread by setting omp_set_num_threads(1)

If I change nothing but remove the OMP annotations, the algorithm works.

Can anyone see a problem?

EDIT: I just realized that sometimes the execution skips over the task block, I don't know why that is happening but it seems to be causing the problem.

ggfpc
  • 86
  • 8

1 Answers1

0

In C, #pragma omp is only for the following line.

The indentation suggests you should have

solve(matrix, x, y):
    for i in [0,9]:
        if(valid(matrix, x, y, i):
            val = 0
            #pragma omp task firstprivate(x, y, i, matrix, val)
              {
                copy_matrix = copyOf(matrix)
                copy_matrix[y][x] = i
                val = solve(copy_matrix, nextEmptyX, nextEmptyY)
                if(val) print_matrix
              }
            if(val) return true
            matrix[y][x] = 0
#pragma omp taskwait 
return false;

Not sure this is enough to solve your issue though.

Gilles Gouaillardet
  • 8,193
  • 11
  • 24
  • 30
  • Thank you for the reply , but that's exactly what I have, I just ommited brackets since its pseudocode. Is there anything that could force OMP to skip a parallel block? It seems to not always enter the task which causes the issue. – ggfpc Apr 02 '18 at 07:51
  • are you also mixing task and sections ? see https://stackoverflow.com/questions/13788638/difference-between-section-and-task-openmp for some explanations. if the problem persist, please edit your question with a [MCVE] instead of pseudo code – Gilles Gouaillardet Apr 02 '18 at 08:26