What is the minimum number of bits required to store a sudoku puzzle?
Along the same lines as ratchet freak's answer, if you fill in the non-starred cells in the following matrix, a 3x3 box at a time, always choosing the next box to fill in to be one that shares rows or columns with a box you've already filled in, you get a pattern like the following for the number of choices per step (filling in the top middle box first, the top right box next, etc).

In each 3x3 box after the first, once you've filled in one row or column of the box, three of the remaining six digits are localized to a single row. Choose their locations first, and then fill in the remaining three cells. (So the actual order of which cells to fill in might vary depending on what you already know, but the number of choices is never more than what I've shown.)

After you've filled in these cells the stars are all determined.

* * *    9 8 7    6 5 4
* * *    6 5 4    3 3 2
* * *    3 2 1    3 2 1

6 5 4    * * *    6 3 3
3 3 2    * * *    5 3 2
3 2 1    * * *    4 2 1

6 3 3    6 5 4    * * *
5 3 2    3 3 2    * * *
4 2 1    3 2 1    * * *

If I've calculated correctly, this gives 87 bits. There's some additional savings to be had in the last 3x3 block, per the comment by Peter Shor: every value is localized to one of four cells, and every row contains at least one cell with only four possible values, so certainly the factors in that block should start with 4 not 6, but I don't understand the remaining factors in Shor's answer.