Sudoku is a combinatorial number placement puzzle.

The objective of this game is to fill a 9×9 grid (board) with digits so that each column, each row, and each of the nine 3×3 subgrids (boxes) contains all of the digits from 1 to 9. A simple 9x9 Sudoku puzzle is shown on the right.

Higher-rank sudokus usually have n²×n² board with n×n boxes (n>3). (e.g. 16*16, 25*25, 100*100)

However, high-rank problems with a large number of empty cells can take hours or even days to solve. Execution time will increase drastically with n.

Thus, we aim to parallelize a sudoku solver algorithm with several parallelization techniques, namely OpenMP and MPI, so that any giant sudoku can be solved within a reasonable amount of time.

We have done research about this problem in depth. Researchers in other institutions have implemented Sudoku solvers with OpenMP even though we did not find their code online. The theoretical speedup of Sudoku solver with OpenMP is linear. We have seen some theoretical works on MPI implementation, but we did not use them for our Sudoku solver.