What the heck is ‘sudoku’?

My youngest child just started 7^th grade, and her math teacher sometimes assigns a puzzle called sudoku for homework. The first time she asked me to help her with one of these assignments, I thought it was a variation on magic squares. But after looking at the rules for completing a sudoku, I realized that it’s completely different. A sudoku is a pure logic puzzle, whereas a magic square is an arithmetic puzzle. The fact that most sudoku (e.g. in newspapers) use digits 1-9 is merely convenience. Some sudoku puzzles use letters, while others use geometric and/or colored symbols. I found a pretty nice sudoku application on the web, if you want to give it a try.

I’m very interested in the information theory and coding aspects of these puzzles. It strikes me as being somewhat like compressing a file. (Actually, I guess it would be “decompressing”.)