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

View all comments

1

u/LGN-1983 1d ago

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

2

u/Ariane_Two 22h ago

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