Sudoku OK, kudos UK

Thanks to Suresh for the introduction and for the opportunity to add a few posts to the Geomblog. Since it is a "holiday" weekend in the US and elsewhere, I thought I would begin with some posts on puzzles and games from a computer science perspective.

As Lance observes, there seems to be a sudden and unexplained interest in Sudoku in my home country. It felt very odd to read about this while living in the US, since it makes the extraordinary interest this seems to have generated (newspapers publishing tens of puzzles every day and competing with each other for who has the best puzzles) seem very abstract and hard to imagine. Of course, since I was reading about this in an online newspaper, it's quite possible that they were merely hyping the phenomenon in their own interest.

The game is pretty simple: one is given a 9 by 9 grid, formed of 9 subgrids of size 3x3 each. Some digits from 1 to 9 are filled in some of the squares, and the goal is to complete the grid under the constraints that each digit must appear exactly once in each row, column, and subgrid.

I tried some of these puzzles online at http://www.sudokufun.com/sudoku.php and the guardian, and finished them in an hour or so each. As a game, I didn't find it very satisfying: it didn't seem to require too much wit or inventiveness to finish. Once I picked up a few heuristics, it seemed to follow pretty easily from repeated application of the Sherlock Holmes method: eliminating possibilities. Perhaps it takes a few more tries to get addictive. There is certainly something rewarding about the "endgame" where the last few squares can get filled in very quickly indeed.

As a good computer scientist, my first thought was also how to generalize this puzzle. If we call this version Sudoku-3, then one can easily imagine how Sudoku-n will look like, and very quickly (by websearching, of course...) discover that the decision problem is NP-Complete (that is, to decide whether a given instance has any solution). Is this the end of it? Not really. There are many other questions that spring to mind that I do not know the answer to:

• 
  Counting version: How many different filled in Sudoku-n grids are there? Let me get you started: For n=1, the answer is 1. For n=2... actually, I don't know, but there are at most (4!)^4 ways to arrange 4 lines of permutations of {1,2,3,4}, so checking all 300,000-ish possibilities won't take too long on a modern PC. Someone who is a whiz with mathematica could probably do this in a few lines of code. But for 3, one will need some smarter techniques to do the counting, perhaps building up satisfying sublocks, and using symmetries more cleverly. I couldn't spot any entries in Neil Sloane's encylopedia of integer sequences for this problem yet.
  
  
• Algorithms. One important feature of the puzzles that are printed is that there is exactly one solution. For these the decision problem is simple: the answer is always "solvable!" However, given this fact, is there now a simple algorithm to find the solution which does not resort to exhaustive checking? here someone has laboriously gone through an example of how to solve the puzzle by repeatedly applying simple elimination rules. Can you prove that this is always sufficient?
  
  There's a danger of a tautology here: apparently many of these puzzles are generated by computer and then checked automatically that there is a unique solution. So the difficulty of these puzzles is only as hard as the complexity of the checker! In other words, if the checker runs the elimination algorithm to verify that there is a unique solution, then it will reject some grids that can be solved uniquely if they do not yield to the elimination method. Indeed, some grids are crafted by human designers and these are supposed to be superior (although, I do not know how easy it would be to distinguish machine generated from human). I tried one of each, and although the human generated puzzle took longer and seemed to require some additional rules to finish, it would be hard for me to say where the creativity comes from.
  
  
• Puzzle generation. Staying on this theme, how could you generate a random instance of a puzzle to give to someone to solve? Randomly filling in a few entries then checking whether there is a (unique) solution might work. But now how do you make this a good puzzle? Perhaps the generated instance is too easy (eg, if very many entries are filled in already, or all 9 copies of one digit are filled in). How to tune the algorithm to generate good grids, or ones at differing levels of difficulty? I suspect that this problem very rapidly becomes a subjective matter, and comes down to a variety of heuristics, but perhaps one could define some metrics or desired properties and make it more rigourous.
  
  
• (Philosophical -- Extra Credit). Why is this a craze? What is it about these puzzles that makes them enjoyable? As has been proved by many computer scientists, many popular games and puzzles, from Tetris and Minesweeper, to various block pushing and object arranging games, are NP-Hard. Does this explain why we enjoy them? Is there something common to these "constraint satisfaction problems" that makes them enjoyable? There's something a little wrong with this hypothesis though: the instances of these games used to prove hardness have a tendency to be very repetitive, and boring seeming. For instance, the reduction used to prove Tetris NP-Hard relies on a very regular initial arrangement and many repetitions of the same block in sequence. When I play Tetris, I enjoy much more the application of essentially simple heuristics to try to produce an arrangment that can adapt to whatever happens to come next. When I play Lemmings, I know that the level designers have in mind some sneaky way of using the physics of the game in order to win the game. The reason I didn't enjoy my first games of Sudoku very much was because it seemed too deterministic: I wanted some non-determinism, but not too much!
  

So, I haven't really been hooked by this craze. I think I will stick to my preferred newspaper puzzle, the cryptic crossword, of which more in a later post...