Data Description

We found three 16x16 and three 25x25 Sudoku puzzles with different difficulty levels to test our software and compute speedup. All the problems were found online. We manually took out a few cells from the solution board to adjust problem difficulty.

Model Details

Serial Version

• Backtracking Algorithm
• Depth first search
• Search through permutations of all possibly correct values until it reaches a solution.
• Pseudocode
At the i-th empty cell on the board: for all possible fill-ins: fill the number if this is the last empty cell: return the solution else: search the (i+1)-th empty cell return with no solution

OpenMP Version

• Serially generate a list of incomplete solutions through bootstrapping: fill a few empty cells with all possible values, and generate a shared queue of possible board to be solved by each thread
• Each thread solve the boards in parallel with the backtracking algorithm
• Use dynamic scheduling to balance work load on all threads: each thread will pop a new board from the queue to solve when it finished solving the previous board

MPI + OpenMP version

• Serially generate a list of incomplete solutions
• Evenly dispatch the list of boards to nodes
• Each node generates a list of incomplete solutions using the same method as the OpenMP version
• Each node performs OMP-level parallelism to solve the puzzle
• All nodes output the solutions to a queue of solutions to be gathered and printed out by the master node

Advanced Feature

• MPI Random Shuffling: The queue of boards is shuffled before dispatching to each node. This will make sure that the work load of each node is relatively balanced, and no node waits a long time for the other nodes to finish.
• MPI Dynamic Scheduling: The slave nodes request a new problem board every time they finished the previous one. The master node is constantly waiting for these requests so that it always responses immediately. Once the master node dispatches all the problem boards it has, it broadcasts a stopping message and waits till all slaves stop. Non-blocking MPI communication functionalities are applied to implement this feature.

Our documentation for the source code is on this page: documentation. Please click on the "Classes" tab to see the details of all classes we created.