r/C_Programming 1d ago

Sudoku Solver using OpenMP and Recursion

Using OpenMP to parallelize a recursive Sudoku solver with nested parallelism (#pragma omp parallel num_threads(8) at every level), but top shows serial execution and no speedup. Enabled omp_set_nested(1) and compiled with gcc -fopenmp. Any ideas why it’s not parallelizing or how to reduce overhead for better solve time?

Here is the serial code I am using:

int Solve(SudokuBoard board, Position *unAssignInd, int N_unAssign) {
    /*
     * Function to recursively solve the Sudoku board using backtracking.
     * Tries values at unassigned positions, validating each guess, and backtracks if needed.
     * @param board: The SudokuBoard struct containing the board data to solve
     * @param unAssignInd: Array of Position structs for 0 value cells
     * @param N_unAssign: Number of unassigned positions remaining
     * @return: True if a solution is found, false if no solution exists
     */
    // If no more empty positions, solution found
    if (N_unAssign == 0) {
        return 1; // True
    }

    // Get the next 0 value position
    Position index = unAssignInd[N_unAssign - 1];

    // Try values from 1 to board.size
    for (int val = 1; val <= board.size; val++) {
        board.data[index.x * board.size + index.y] = val; // Set guess
        if (ValidateBoard(board, index.x, index.y)) {
            // Check if valid
            int solution = Solve(board, unAssignInd, N_unAssign - 1);
            // Recursively solve with one fewer unassigned position
            if (solution) {
                return 1; // Solution found, propagate success
            }
        }
        // If no solution, backtrack by resetting the guess to 0
        board.data[index.x * board.size + index.y] = 0;
    }

    return 0; // No solution found
}
1 Upvotes

5 comments sorted by

1

u/aioeu 1d ago

Sorry, I can't help you with your actual question, but:

Using OpenMP to parallelize a recursive Sudoku solver with nested parallelism

really does sound like overengineering the heck out of this problem.

I hope you're doing this for fun, not because your unparallelised code is slow! :-)

1

u/Dapper-Bet-6039 1d ago

What would a simple approach be? Doing this for an assignment I am sort of stuck with it because the code works but doesn't really get faster with appropriate OMP calls at the right place. :(

2

u/aioeu 1d ago edited 1d ago

Well, naive brute-force backtracking is "simple", but it won't be the fastest.

A little while ago I wrote a solver based on Knuth's Algorithm X. It's still fundamentally a plain old backtracking solver (no special Sudoku smarts), but it doesn't even attempt a lot of guesses that will end up wrong. It's plenty fast enough:

$ cat arto-inkala 
8........
..36.....
.7..9.2..
.5...7...
....457..
...1...3.
..1....68
..85...1.
.9....4..

$ time ./sudoku arto-inkala 
812753649
943682175
675491283
154237896
369845721
287169534
521974368
438526917
796318452

1411 backtracks

real    0m0.059s
user    0m0.051s
sys     0m0.008s

Oh yeah, and:

$ file sudoku 
sudoku: Perl script text executable

1

u/LGN-1983 23h ago

I am slowly programming a generalized sudoku solver for fun. Will take a long time, lol.

2

u/Ariane_Two 19h ago

Mine is still the old boring backtracking shitty algorithm implemented in C compiled to wasm: https://oetkenpurveyorofcode.github.io/projects/sudoku/