Ending OpenMP for prematurely

Question

I have a problem with writing a routine in C++ using OpenMP for. The code of the routine is as follows:

int sudokuSolution [9][9];

bool solvep(int s[9][9], int row, int col) {    
    bool solution = false;
    #pragma omp parallel for
        for (int val = 1; val < 10; val++) {
            if (isPossible(s,row,col,val)) {
                s[row][col] = val;  
                if (solve(s, row + col / 9, (col + 1) % 9)) {
                    sudokuSolution[row][col] = val;
                    solution = true;
                }
            }
        }
    return solution;
}

when running this routine without the parallel clause, everything works fine (i.e. routine returns true every time it's called). However, when I use the parallel for, it sometimes returns false. I wasn't able to figure out, why is this happening and the only way of removing this bug is from my perspective ending the whole parallel block prematurely after solution is set to true. However, if I did my research properly, there is no way to prematurely end a parallel block. Could you please suggest me an alternative?

EDIT: Adding minimal functioning example as requested:

#include <omp.h>
#include <iostream>
#include <list>
#include <chrono>

using namespace std;

bool solutionFound = false;
int sudoku [9][9] = { 5,7,0,9,0,0,0,0,8,
                      0,0,0,0,0,5,0,3,9,
                      0,0,0,0,0,0,2,0,4,
                      0,0,0,0,9,0,6,8,0,
                      0,0,0,8,0,2,0,0,0,
                      0,5,2,0,7,0,0,0,0,
                      6,0,5,0,0,0,0,0,0,
                      7,9,0,4,0,0,0,0,0,
                      2,0,0,0,0,9,0,7,6};

int sudokuSolution [9][9];

bool isPossible(int s[9][9], int row, int col, int val) {
    for(int i = 0; i < 9; i++) {
        if (s[row][i] == val)
            return false;
        if (s[i][col] == val)
            return false;
        if (s[row / 3 * 3 + i / 3][col / 3 * 3 + i % 3] == val)
            return false;
    }       
    return true;
}

bool solve(int s[9][9], int row, int col) { 
    while(s[row][col] != 0) {
        col = (col + 1) % 9;
        row = row + col / 8;
        if(row == 9)        
            return true;
    }   

    for (int val = 1; val < 10; val++) {
        if (isPossible(s,row,col,val)){
            sudokuSolution[row][col] = val;
            s[row][col] = val;
            if (solve(s, row + col / 9, (col + 1) % 9))
                return true;
            sudokuSolution[row][col] = 0;
            s[row][col] = 0;
        }
    }
    return false;
}


bool solvep(int sa[9][9], int row, int col) {   
    int s [9][9];
    for(int i = 0; i < 9; i++)
        for(int j = 0; j < 9; j++)
            s[i][j] = sa[i][j];
    while(s[row][col] != 0) {
        col = (col + 1) % 9;
        row = row + col / 8;
        if(row == 9)        
            return true;
    }   
    bool solution = false;
    #pragma omp parallel for
        for (int val = 1; val < 10; val++) {
            if(!solutionFound) {
                if (isPossible(s,row,col,val)){
                    s[row][col] = val;  
                    if (solve(s, row + col / 9, (col + 1) % 9)) {
                        sudokuSolution[row][col] = val;
                        solutionFound = true;
                        solution = true;
                    }
                }
            }
        }
    return solution;
}

int main() {
    for (int k = 0; k < 100; k++) {     
        for(int i = 0; i < 9; i++)
            for(int j = 0; j < 9; j++)
                sudokuSolution[i][j] = sudoku[i][j];
        solutionFound = false;      
        solvep(sudokuSolution,0,0); 
        bool calcResult = solvep(sudoku,0,0);   
        cout << calcResult;
    }
    return 0;
}

Answer 1

You have many race conditions in your code, both in the loop itself and the solve function. In code that is executed in parallel you must not write to to shared data (s, solution, sudokuSolution) and especially global variables (solutionFound). You will have to go back to your learning material and catch up with data races and the methods to protect against them.

With some experience it is easy to spot the issues in the loop itself. It's much harder to spot in called functions - which is why its so important to give a complete example in your question. Try to define your interfaces such that mutable no shared data is passed to functions. Conceptually you will have to have a copy of the board for each thread to perform backtracking in parallel.

Once you fix the issues with writing to the board, you can use atomic writes, a critical region or a reduction to "share" the solution. But you have to consider both sudokuSolution[row][col] and solution. Logically I suppose sudokuSolution[row][col] != 0 == solution.

Answer 2

You could reduce the solution values on all threads using the || operator:

int sudokuSolution [9][9];

bool solvep(int s[9][9], int row, int col) {    
    bool solution = false;
    #pragma omp parallel for reduction(||:solution)
        for (int val = 1; val < 10; val++) {
            if (isPossible(s,row,col,val)) {
                s[row][col] = val;  
                if (solve(s, row + col / 9, (col + 1) % 9)) {
                    sudokuSolution[row][col] = val;
                    solution = true;
                } else {
                    solution = false;
                } 
            } else {
                 solution = false;
            }
        }
    return solution;
}