Cracking Sudoku

Tackling problems and coding solutions for them is an essential part of the job of a software engineer like myself. The only problem with this is that sometimes work becomes a little boring and repetitive. With some tasks you can even begin to feel a little like a brainless code monkey that knows how to do its job very well, but lacks the stimulation of problems that appeal to the creative capabilities of the brain. Enter the Sudoku!

I have always liked logical puzzles as a kid (and adult too) and when I was first introduced to sudoku I was immediately hooked. If you are new to the whole sudoku thing, here is a very quick explanation of the game: The aim of the puzzle is to enter a number from 1 through 9 in each cell of a 9×9 grid made up of 3×3 subgrids (called "regions"), starting with various numbers given in some cells (the "givens"). Each row, column and region must contain only one instance of each number. That’s it – simple as that!

Well, it isn’t that simple actually. The rules may be very straightforward, but the solutions to the puzzles require some really complex logic at moments. Sudokus come in varying difficulties depending on the complexity of approaches required to solve them. Surprisingly, the amount of numbers you start with does not have much effect on the difficulty. If you are seeking knowledge of how to improve your skills, make sure you check this website which has a nice summary of some of the most well-known strategies. If you are feeling up to the challenge, you can go try a puzzle at http://www.websudoku.com/

As a programmer and a geek I found myself thinking NOT of how to solve the sudokus, but how to make the computer do it for me. It turned out the latter problem is by no means less interesting. There are various takes on the matter, but I preferred to capitalize on the fact that the rules of the game are so few and simple. My strategy would try and place numbers in the empty spaces and simply validate the resulting grid. If an error is found it would go back and simply try a different number. The good thing about this strategy (also called backtracking algorithm) is that it is guaranteed to always work when given a valid puzzle. I wrote a very simple solver (source code included of course) in C# that implements backtracking with a stack and arrives at a solution within seconds (usually less than 1). Feel free to try it out with some of the sample puzzles I included with it. I will probably consider writing something more interesting if I have the time. Quality puzzle generation, for example, also seems like an area worth investigating.

What do you like to do for brain work-outs while taking a short break from work? What kind of brain teasers keep you entertained? Feel free to share them.