It is not a difficult, but it demands concentration, good memory, and logic to play. It also takes practices, lots of them, to play well. Wait. These are the same requirements for pretty much everything in life. Aren’t they?
I really never played before this summer. Previously, I solved it like a programmer would, using the dependable backtracking algorithm. Even with aggressive sub-tree pruning, the simplest level still daunted this weekend programmer.
If you don’t know the game, it is deceivingly simple. There is a 9-by-9 grid divided into 9 3-by-3 sections. Each row, column, or section shall have exactly digit from 1 to 9 exactly once. Sudoku was invented in America and popularized in Japan. The name means “lonely digits (數ç¨),” describing the single rule of no digit will meet its same ever. Search the word and you shall find thousands of site offering you endless puzzles to solve. Almost every periodical has a puzzle or two somewhere in the pages.
Surprisingly, the best algorithms to solve Sudoku use graph theories, the same used in various networking problems. Imagine each row, column, and section are nodes attached to the root that is the whole puzzle itself. Those nodes are connected, since they share cells. Each of those nodes has sub-nodes that represent each permutation. The result is a complex graph and the solution will be a sub-graph.
To find the solution, the algorithm systematically prune the graph until the last one: the solution. The algorithm is very similar to those used to solve many networking problems. Unfortunately, it also belongs to the same class of the problem known as NP-Complete. Human kind has not found solution to any problem in this class. We have also proven that a solution to one will also solve all in the class. Whoever finds a good algorithm to solve Sudoku is likely to become a six millionaire. Since there are at least six million-dollar awards unclaimed so far. (The P=NP problem is not related to Sudoku. I think.) He or she is likely to become a multi-billionaire, since the applications of this algorithm are very profiting.
Why is Sudoku so popular? It is both simple and challenging. A child can solve one; a genius mathematician would be stumped. It has a maddening mid-game that seems impossible, followed by an exhilarating phase that everything falls into places. On my iTouch, I downloaded Enjoy Sudoku Daily, a free app on the iTunes Store. Next time you are stuck in an airplane seat, flip the magazine to the Sudoku page and give it a try.
If you get addicted to it, welcome to the club.
2 Responses to Sudoku