## Tuesday, 2 February 2010

### Sudoku!

Most of you have heard about the number game 'Sudoku'. It is one of the most popular games in the world. Even sudoku tournaments are conducted now a days.

The rules are very simple and one with a bit of logical ability can solve the puzzle easily. Just for fun I have created an e-version of sudoku which can solve any valid sudoku game. My e-version can create n number of sudoku games. It can print and to some extent it will even help you to solve the puzzle!

Sudoku! in action

Try to know more about Sudoku!

History
'Sudoku' the popular number game which we see in our dailies has a long history.
Though the Sudoku puzzles which play in this modern world is little bit different from the old one, the basic principles and the rules remains the same.
The game Sudoku was inspired from the concept of Latin squares' (used in statistical analysis) by the famous Swiss mathematician Leonhard Euler in which the numbers in a grid appears only one. He developed this concept in 18th century.

Origin
'Sudoku' is a Japanese name in which 'Su' means number and 'doku' means single place which tells that only one number can comes in its place.

Many people still thinks that this game was originated from Japan or China. But actually this game was developed by an independent puzzle maker Howard Garnes in late 1970s and was published in Dell Magazine in the US under the name of 'Number place'. That was developed on Euler's concept with a 9x9 square grid on which he added a third dimension (the regional restriction). This is the popular version we see in the news papers today.

In the mid 1980s Nikoli Inc., a Japanese puzzle giant published the current version of Sudoku puzzle and that became a huge hit in Japan. Mr. Maki Kaji, the president of Nikoli was behind this. The original Japanese name was 'Suuji wa dokushin ni kagiru' roughly translating to mean the numbers must be unmarried or single. This name was shortened as 'Sudoku' (pronounced SUE-dough-coo; su = number, doku = single) which became a huge international hit later. But that Japanese version took around 20 years to become a popular game to the people in other parts of the world. And soon most of the reputed new papers started publishing daily Sudoku which helped to increase its popularity.

How to play?
Every Sudoku puzzle has a unique answer. Sudoku requires no calculation or arithmetic skills. It is essentially a game of placing numbers in squares, using very simple rules of logic and deduction. It can be played by children and adults and the rules are simple to learn. The objective of the game is to fill all the blank squares in a game with the correct numbers.
There are three very simple constraints to follow. In a 9 by 9 square Sudoku game:
* Every row of 9 numbers must include all digits 1 through 9 in any order
* Every column of 9 numbers must include all digits 1 through 9 in any order
* Every 3 by 3 subsection of the 9 by 9 square must include all digits 1 through 9

How to solve a Sudoku?
Though there are lot of systematic methods to solve a Sudoku, the most popular method (and time consuming too!) is to mark the possible candidates in each cell and then logically excluding them one by one based on the rules. This technique is called 'Pencil Marking'.

Other popular methods:
Hidden Candidates (Singles, Pairs, Triples and Quads), Naked Candidates (Pairs, Triples and Quads), X-Wing, Swordfish etc. Some people even use the guessing techniques like Nishio or Trial and Error.

Please refer the following urls to find the details:
http://www.sudokuoftheday.com/pages/techniques-overview.php
http://angusj.com/sudoku/hints.php

Techniques used in computer programs:
Advanced computer programs use Donald Knuth's 'Dancing Links' technique to generate or solve Sudoku puzzles. This technique uses a recursive, backtracking algorithm to solve the puzzle in a very fast and efficient way.

Some Sudoku puzzles in the internet:
http://www.prokerala.com/news/games/sudoku.php
www.sudoku.com
www.websudoku.com
http://sudoku.friko.net