Any comments and criticisms welcome
An approach from compressed sensing seems to provide a range from $69.96$bits to $171.72$bits:
1.)Storing the puzzle implies storing the solution (information theoretically).
2.)The hardest sudoku puzzle seems to have $t(\alpha)\alpha^{2}$ entries for some $t(\alpha)$ that depends on $\alpha$ (For example, $t(3) ~= 2.44444$ to $3$). http://www.usatoday.com/news/offbeat/2006-11-06-sudoku_x.htm
Hence, we have a vector $P$ of length $\alpha^{4}$ that have atmost $t(\alpha)\alpha^{2}$ non-zero entries.
3.) Take $M$, a $\beta \times \alpha^{4}$ matrix with $\beta \ge 2t(\alpha)\alpha^{2}$ and which has any $2t(\alpha)\alpha^{2}$ columns independent and with entries in $\{0,\pm 1\}$. This matrix is fixed for all instances of the puzzle. $\beta = kt(\alpha)\alpha^{2}$ for some fixed $k$ suffices from UUP.
4.) Find $V = MP$. This has $\beta$ integers which on average is bounded by $|\alpha^{2}|$ since entries of $M$ are random with entries in $\{0,\pm 1\}$.
5.) Storing $V$ needs $\beta\log{\alpha^{2}} = 2kt(\alpha)\alpha^{2}\log{\alpha}$ bits.
In your case, $\alpha = 3$ and $t(\alpha) ~= 3$ and $2kt(\alpha)\alpha^{2}\log{\alpha} = 69.96k$bits to $85.86k$ bits. $k=2$, the minumum required provides roughly $139.92$bits to $171.72bits$ roughly as a lower bound for the average case.
Note that I have hand-waived some assumptions such as sizes of entries of $MP$ and number of entries one has on average in the puzzle.
$A.)$Of course, it mightbe possible to reduce $k$ from $2$ since in sudoku the position of the sparse entries are not that mutually independent. Each entry on an average $t(\alpha)-1$ entries each in its row, column and sub-box. That is given, that some entries are present in a sub-box or column or row, one can find the odds of entries being present in the same row, column or sub-box.
$B.)$ Each row, column or sub-box is assumed to have on an average $t(\alpha)$ non-zero entries with no-repeating alphabet. This means some types of vectors with $t(\alpha)$ non-zero entries will never occur, thereby reducing the search space of solutions. This could also reduce $k$. For instance, fixing $t(\alpha)$ entries in a sub-box, a row and a column would reduce the search space from ${}^{\alpha^{4}}C_{t(\alpha)\alpha^{2}}$ to ${}^{\alpha^{4}-(3\alpha^{2} - 1)}C_{t(\alpha)\alpha^{2}-3t(\alpha)}$.
A comment: May be a multi-user arbitrarily correlated Slepian-Wolf model will help make the entries independent while still respecting the atmost $t(\alpha)\alpha^{2}$ non-zero entries criterion. However, if one could use it, one need not have gone through the compressed sensing route. So applicability of Slepian-Wolf might be hard.
$C.)$From an error correction analogy, an even significant reduction may be possible, since in higher dimensions, there could be gaps between the half-the-minimum-distance radii hamming balls around code points with a possibility to correct greater errors. This also should lead to reduction of $k$.
$D.)$ $V$ itself can be entropy compressed. If the entries of $V$ are quite similar in sizes, then can we assume that the difference between any two of the entries is atmost $O(\sqrt(V_{max})) = O(\sqrt{|\alpha^{2}|})$? Then if encoding the differences between the entries suffices, this itself will remove the factor $2$ in $\beta\log{\alpha^{2}} = 2kt(\alpha)\alpha^{2}\log{\alpha}$.
It would be interesting to see if $2k$ can be made equal or less than $2$ using $A.)$, $B.)$, $C.)$ and $D.)$. This would be better than $89$ bits (which is the best so far in other answers) and for the best case better than the absolute minimum for all puzzles which is around $73$bits.
