Parallelized Sudoku Solving Using OpenMP

Sudoku is a logic-based, combinatorial number-placement puzzle. The objective is to fill a 9x9 grid with digits so that each column, each row, and each of the nine 3x3 subgrids contains all of the digits from 1 to 9. While a single Sudoku puzzle is trivial for a modern computer to solve using a standard backtracking algorithm, complex variants or massive batches of puzzles require significant computational resources. Parallelizing these algorithms using OpenMP (Open Multi-Processing) is an effective way to leverage multi-core architectures to drastically reduce execution time.

The Backtracking Algorithm

The standard approach for solving Sudoku is backtracking. This algorithm explores the search space by attempting to place numbers in empty cells one by one. If a placement violates the rules, the algorithm "backtracks" by resetting the cell and trying the next available number. Because the search space can grow exponentially with the number of empty cells, an optimized sequential algorithm uses constraint propagation to prune branches of the search tree that cannot lead to a valid solution.

Introducing OpenMP Parallelization

OpenMP provides a simple, portable, and scalable interface for shared-memory parallel programming in C, C++, and Fortran. To parallelize a Sudoku solver, we must identify regions of the search tree that can be explored independently. A common strategy involves the following steps:

Initial Constraint Propagation: Perform a preliminary pass to fill in cells that only have one possible candidate.
Task Decomposition: Once the grid reaches a state with multiple choices, the solver can spawn parallel tasks. Instead of the algorithm committing to one branch, it creates copies of the board state and assigns different branches to different processor threads.
Work Stealing: OpenMPs tasking model allows threads to "steal" work from others if they finish their allocated branches early, ensuring efficient load balancing.

Implementation Considerations

Parallelizing recursive algorithms presents challenges, specifically regarding memory management and thread safety. Each thread requires its own local copy of the Sudoku grid to ensure that modifications in one branch do not interfere with calculations in another.

// Conceptual structure for OpenMP parallel tasking#pragma omp parallel{    #pragma omp single    {        solve_recursive(board);    }}

In the solve_recursive function, the code is structured to check if a specific threshold of search depth has been reached. If the search depth is shallow, the program spawns tasks:

if (depth < MAX_PARALLEL_DEPTH) {    for (int num = 1; num <= 9; num++) {        if (is_valid(board, row, col, num)) {            #pragma omp task shared(found)            {                // Create local copy and recurse                solve_recursive(new_board);            }        }    }    #pragma omp taskwait}

Performance Gains and Limitations

The speedup obtained through OpenMP depends heavily on the "branching factor" of the specific puzzle. Puzzles with very few initial clues result in a wider search tree, providing more opportunities for parallelization. Conversely, puzzles with many clues may resolve too quickly for the overhead of thread management to be justified.

A critical consideration is the "early exit" condition. In a sequential program, once a solution is found, the entire process terminates. In a parallel environment, threads must share a global flag to indicate that a solution has been found, allowing other threads to abort their search and terminate gracefully. This prevents the system from wasting CPU cycles searching for additional solutions when only one is required.

Conclusion

Integrating OpenMP into a Sudoku solver is an excellent demonstration of task-based parallelism. By decomposing the backtracking search tree into independent tasks, developers can achieve significant performance improvements on modern multi-core processors. While the overhead of task creation must be carefully managed through thresholding, the scalability offered by OpenMP makes it an essential tool for high-performance combinatorial searching.

Reference Files For Parallelized Sudoku Solving Algorithm Using OpenMP

Screenshoot

File Name

sankar_spring_2014_cse633.pdf

File Size

0.83 MB

File Type

PDF

File Site

Jagomart.net

Description

This file is just a reference file for Parallelized Sudoku Solving Algorithm Using OpenMP. Does not guarantee that the specific things you want are included in it.

Download on the Jagomart.net website

Direct download (wait 10 seconds)