SudokuMP


Project Proposal

Summary

We plan to implement a sudoku solver in parallel using the OpenMp library. We will do so using Crook's Algorithm, also known as the Humanistic Method, for solving sudoku puzzles, with a brute force game solver to handle cases in which the Humanistic Method fails to finish the puzzle.

Background

Sudoku is a logic-based number puzzle featuring a 9x9 board divided into rows, columns, and 3x3 square blocks. The goal of the game is to fill each row, column, and block with unique numbers in the range 1 through 9. Variations of sudoku have used larger boards, such as hexadoku: sudoku with a 16x16 board.

Here is an example of a sudoku puzzle (left) along with its solution (right):

The difficulty of any particular sudoku puzzle depends on how many numbers are initially given to the user. Easy sudoku puzzles generally start with 32 or more numbers, medium puzzles with 26-30 numbers, hard puzzles with 22-24 numbers, and expert puzzles with fewer than 20 numbers.

The Challenge

Programming a parallel sudoku solver is challenging for the following reasons:

  1. Sudoku is NP-Complete. There are over 6.67 x 1021 possible Sudoku grids. Thus, if we were to implement a brute force solver, the solver would need to maximize efficiency.
  2. If we were to implement a humanistic solver, the solver would need to search for solutions over rows, columns, and blocks. Since there is a lot of overlap between those, we will need to use fine-grained synchronization.
  3. Due to the speed of the Humanistic Method, it may be difficult for a humanistic solver to benefit greatly from parallelism.

Resources

We plan on starting this project from scratch. We will research Crook's Algorithm for solving sudoku puzzles deterministically, and combine the algorithm with a brute force solver to ensure that our solver can solve any sudoku puzzle. Then, we will write a sequential solver in C++. We will parallelize our solver using OpenMP, which we could test on the Xeon Phi chip for maximum speedup.

Goals and Deliverables

Our goal is to achieve close to linear speedup proportional to the number of cores used. This may be difficult for a humanistic solver (which is fast but harder to parallelize) and more achieveable with a brute force solver (which is slow but has more potential for speedup after parallelism).

Our stretch goal would be to create a GUI that displays a sudoku puzzle solving itself in real time. Another stretch goal would be to generalize our solver to accept any n x n sudoku board (where n is a square).

Platform Choice

We would like to run our solver on the Gates 3000 machines and the 3.2 GHz Intel Xeon Phi co-processors. We chose to use OpenMP because we are most familiar with it, and it also offers a good variety of synchronization tools (i.e. atomic, atomic capture, locks, etc.).

Schedule

Week Of Plan
3/27 Finalize idea and submit proposal.
4/3 Implement sequential solver.
4/10 Parallelize solver.
4/17 Improve upon parallelization.
4/24 Implement any stretch goals, wrap-up project.
5/1 Complete project presentation and write-up.