## Sudoku

February 9th, 2006A couple of people suggested that I might like Sudoku and although I tried it out a couple of times before I never really had the patience to finish it. You just have to complete the grid with numbers so that every column, row and 3×3 square contains the numbers 1-9 exactly once. The WSJ had an article today about how the Sudoku crazy is getting out of hand…

British Airways recently issued a memo to its 13,000 cabin crew members reminding them that working on games like the popular Japanese number puzzle during takeoff and landing is prohibited for safety reasons. BA said the move was prompted by passenger concerns that crew members were doing puzzles.

They also published a sample puzzle of medium difficulty which I was motivated enough to actually complete in about 30 minutes. Marco suggested that I try one of the Guardian’s Sudoku’s puzzles which are created by a Sudoku grand master instead of a computer program and I tried my hand at the difficult Feb 6th puzzle. I spent an hour on it before losing patience and giving up.

I was thinking about how to solve Sudoku puzzles by computer and realised that it was quite easy to brute force a solution. Here is a link to a nice website which has a solver and a discussion of the logic behind it. Then I started wondering about how Sudoku puzzles were created to ensure that they had a unique solution. This seems like a more interesting problem to think about. You can make the grid into a graph and the problem is equivalent to finding a proper 9-colouring of the graph given a partial 9-colouring. I am sure Hemanshu will have several interesting things to say about this when I meet him in Champaign this weekend.

I don’t know why I get addicted to some types of puzzles and I am cool to others. I really got addicted to Freecell, but I didn’t like Sokoban very much (even in Nethack I tried to cheat as much as my luck would allow it). Even though some Sudoku games are challenging, somehow I don’t think I will get addicted to them.

Ps. If you want some challenging Freecell games, take a look at this link. There are some very interesting graph theory problems related to Freecell also.