'(The Blog) With No Name', perhaps best described as a stream of notes and thoughts - 'remembered, recovered and (sometimes) invented'.

Saturday, May 21, 2005

Sudoku - Yet Another Puzzle!

Anand has a nice introduction to this newly famous class of puzzles at his blog 'Locana'. He has also kept a sample puzzle and its solution as well.

A few observations:
I took over an hour to solve the instance of Sudoku featured at Locana. Finding the basic pattern was simple enough but implementing it fully was somewhat laborious (this indicates a possible relevance for programming; it could also mean I missed something!). Anand says there are other harder instances of this puzzle which could take more time.

With the limited experience of having seen only one instance of this puzzle, one wonders what is the minimum number of small squares in the grid that ought to be filled so that the rest of the layout is uniquely determined (in the example Anand gives 30 squares are filled initially) - the distribution(s) of these squares to be filled and the frequencies of the numbers from the set (1-9) used (the starting arrangement need not have all the numbers in equal numbers; how to quantify their relative frequencies?) could be important as well. Indeed, trying to create instances of Sudoku, generalizing to larger grids etc.. could perhaps present worthwhile challenges.

I have yet to figure out how many valid final configurations there oculd be - those configs which have nos. 1-9 in every row, column and 3X3 square. Then come the questions of whether for every such configuration, the minimum number of numbers to be provided initially is the same, what symmetries could a valid initial configuration have etc..

In short, Sudoku appears to raise plenty of questions, and some of these might have interesting answers.

Note Added On 23rd May 05:
Here is more info on Sudoku from wikipedia. It says some of the questions posed above are still open. Links to related (and interesting) topics such as 'Latin Squares' are also available there.