I am sure that everyone knows that Sukoku is a logic-based number placement puzzle. The objective is to fill a 9×9 grid so that each column, each row, and each of the nine 3×3 boxes (also called blocks or regions) contains the digits from 1 to 9, only one time each (that is, exclusively). The puzzle setter provides a partially completed grid. ( Wikipedia )

However, did everyone know that it is also an NP-Complete problem when the grid size is increased infinitly? Like a rubics cube, a lot of people are obsessed with finding new algorithms to solve sudoku puzzels.  A cornell professor even created an algorithm to solve any puzzle.

“But in discovering an algorithm critical for X-ray diffraction microscopy, [Cornell Physicist Veit] Elser and colleagues solved two problems. First, they gave researchers a new tool for imaging the tiniest and most delicate of biological specimens. And second, they discovered that the same algorithm also solves the internationally popular numbers puzzle Sudoku.” (Cornell News)

Why is this so important to CS 322?

I was thinking of a simple way to solve any 9×9 puzzle. The only method that is relevant to CS 322 will be to write out the puzzle as a system of equations. Then you can use matrices to solve it.  This will be very tidious. And could be O(n x m)

But since sudoku is an exact cover problem, an exact cover is a subcollection of that is a partition of U: The sets in are pairwise disjoint and their union is U (wikipedia), it can be solved using  Dancing links techniques which make solving sudoku O(n).

 In short, sudoku is great!

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

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

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

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

http://www.news.cornell.edu/stories/Feb06/Elser.sudoku.lg.html