Monday, August 22, 2005

sudoku

The "Bangalore times" of Times of India have presented a game called "Sudoku."

The details of the game are here

What I want to know is that , can we algorithmise this game ?
In other words, given an input grid can we arrive at one (or more) solutions ?

2 comments:

Tejaswi said...

Sodoku has captured Appa's imagination these days, and he is busy coding up solutions in Java. So, if you are interested, go to my place and talk to him.

From what I remember, the general grid problem is NP-complete. But given the size of the grid as constant, back tracking and dynamic programming methods are possible. And that is what Appa is doing, for grids of size 9, etc.

The fever has come and gone, I think. You are somewhat late Peedus.

sudeep said...

I have forgotten backtracking and dynamic programming....I am not that interested in "NP" and all that.... Totally ditzz in the algorithms dept... :-)

Need to attack some problems....
long time....