The exact cover problem is an NP-complete problem with many widespread use cases such as crew scheduling, railway scheduling, benchmarking as well as having applications in set theory. Existing algorithms can be slow when dealing with large datasets however. To solve this problem in a quick manner this thesis uses a new method based on an existing algorithm called Algorithm X utilizing parallelization with the task construct of OpenMP to produce better results, at best providing a speedup of 4.5 when compared to a serial optimized implementation of Algorithm X. Since creating child tasks through the task construct causes additional overhead this thesis examines the effect granularity has on the solver by varying how many child tasks should be created before opting to solve the rest of the problem serially. The optimal number of child tasks is found to be very low when using a high amount of cores and vice versa when using fewer cores. Since the new method created for this thesis can solve the exact cover problem faster than Algorithm X it can prove to be beneficial when solving the problems mentioned earlier.

This thesis investigates the scalability of parallel Sudoku solving using Donald Knuth’s Dancing Links and Algorithm X with two different MPI communication methods: MPI One-Sided Communication and MPI Send-Receive. The study compares the performance of the two communication approaches and finds that MPI One-Sided Communication exhibits better scalability in terms of speedup and efficiency. The research contributes to the understanding of parallel Sudoku solving and provides insights into the suitability of MPI One-Sided Communication for this task. The results highlight the advantages of using MPI One-Sided Communication over MPI Send-Receive, emphasizing its superior performance in parallel Sudoku solving scenarios. This research lays the foundation for future investigations in distributed computing environments and facilitates advancements in parallel Sudoku solving algorithms.