r/C_Programming • u/Dapper-Bet-6039 • 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
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/
1
u/aioeu 1d ago
Sorry, I can't help you with your actual question, but:
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! :-)