Sudoku, if you are unaware, is a great game where you fill in a 9×9 grid based on some number of given clues such that:

• Each row contains only one instance of 1 to 9
• Each column contains only one instance of 1 to 9
• Each of the 9 3×3 boxes contain only one instance of 1

Like most great games, it is easy to understand the rules, and very difficult when you get into the more complicated problems (which are the ones with fewer clues). A valid Sudoku puzzle also follows some lemmas:

• There exists a solution to the puzzle
• That solution is unique

Unfortunately, the proof of these lemmas is beyond the scope of this blog, but using these two lemmas we are faced with an interesting question, and it is the question posed by the people at The Distributed Sudoku Project. What is the minimum valid Sudoku puzzle? That is, what is the minimum number of clues that can be given and still have a unique solution.

They propose a trivial lower bound of 8, with the following argument:

“A trivial lower bound is 8: assume only 7 numbers are given. Then in any solution you can interchange all occurrences of two non given digits, and thus there are always at least two different solutions.”

However, all known minimal Sudoku puzzles contain 17 clues, making the possible range of the true minimal Sudoku puzzles to be somewhere between 8 and 17 clues. The organizers of the project have managed to narrow it down to between 11 and 17 clues, but have opted to use distributed computing to try and either eliminate all the possibilities for each number of clues, or, find an example of a new minimal Sudoku puzzle.

Distributed computing is an obvious choice at this point because they have opted for a brute force approach to further tighten the bound of minimal puzzles. They essentially wish to check every possible combination of hints from 11 to 17, and check if that layout of hints yields a valid solution. Testing to see if your hints yields a valid solution is fairly trivial to determine systematically, but testing all the possible positions of those numbers in the 9×9 grid is where distributed computing starts being the only way to determine this (other than some great mathematical insight).

References:

http://dist2.ist.tugraz.at/sudoku/

http://en.wikipedia.org/wiki/Sudoku

http://www.afjarvis.staff.shef.ac.uk/sudoku/sudgroup.html (cool article on the math behind Sudoku)