27 September 2005

Su Doku

Jimmy introduced me to Sudoku, a placement puzzle involving numbers. Will intrique engineers and logic nuts alike. It is very popular in the US now after gaining world popularity in 2005. I consider it a culture neutral game that can be played by anybody with numerical skills.
The general problem of solving Sudoku puzzles on n2 x n2 boards of n x n blocks is known to be NP-complete. This gives some indication of why Sudoku is difficult to solve, although on boards of finite size the problem is finite and can be solved by a deterministic finite automaton that knows the entire game tree. For more on the math behind it.. go here
Check out the online version

No comments: