<p>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).</p>

<p>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.)</p>

<p>After you've filled in these cells the stars are all determined.</p>

<pre>* * *    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    * * *</pre>

<p>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.</p>

CC BY-SA 3.0
2011-09-10T17:19:26.287Z
You can reduce the number of choices when you fill in the sixth 3x3 box, as well. This box becomes 4,3,2 / 3,2,1 / 2,1,1 for a total of 83 bits, if I calculated it correctly.
Peter Shor 
CC BY-SA 3.0
2011-09-11T02:33:56.040Z
@Peter - nope.  The 3 numbers to the right could be the same as the numbers above.  You don't know all of them are distinct.  The most assured unique numbers are 3 so the first box is a pick from six items.  (This one location is an example.  It is true for the others too.)
Hogan
CC BY-SA 3.0
2011-09-11T02:38:31.773Z
@David - going by my comment to Peter I don't think your numbers are wrong.  In the 2nd box you have `6 5 4 4 3 2 3 2 1` I believe it needs to be `6 5 4 6 5 4 3 2 1` for the worst case.
Hogan
CC BY-SA 3.0
2011-09-11T02:40:26.667Z
Hogan, no, see the part in my answer about "once you've filled in one row or column of the box, you can always choose the next row or column to fill in to be one in which there are at most four possible values"
David Eppstein
CC BY-SA 3.0
2011-09-11T02:45:40.717Z
@David - Lets label the 3 x 3s 1,1 1,2 1,3 going left to right top to bottom.  Let lable the Squares A - I going left to right top to bottom.  The location D in 1,3 knows 3 numbers in the 3x3 it is in (A,B,C) and it knows 3 numbers in 1,2 (D,E,F) but it does not know those 6 numbers are different.  They could be the same 3 numbers from box 3,1 and 2,1 thus there are MAX 6 choices.
Hogan
CC BY-SA 3.0
2011-09-11T03:00:44.280Z
@David -- I see you are saying you might fill in (G,H,I) or (D,E,F) in box 1,3 (Depending on the duplicates with (D,E,F/G,H,I) in box 1,2 -- Good point.  It seems following the same method Peter is right for box 3,2
Hogan
CC BY-SA 3.0
2011-09-16T17:04:09.920Z
My analysis was wrong. You can get 4,3,3,3,3,3,2,1,1 without too much work. As David says, for the sixth box, it's easy to see that every number can go into four cells. After you've put the first number in, there will always be some number that goes into at most three cells, and if you look at the last four cells, you can show that these take at most 3,2,1,1. This is a simple case analysis, using the observation that if the last three cells are in all different rows or all different columns, you get 2,1,1. This gives 85 bits. I'm sure you can do better, but it would take some more work.
Peter Shor 
CC BY-SA 3.0
2011-09-18T16:39:18.880Z
And looking at the last five cells, a case analysis gives 4,3,3,3,3,2,2,1,1, which saves another half bit, giving a grand total of 84 bits. You're not going to do any better than 4,3,3,2,2,2,2,1,1 with this method, which would give 83 bits. And even if you can save another bit, it'll be a lot more work, so I'm stopping here.
Peter Shor 
CC BY-SA 3.0
2011-09-10T01:05:19.040Z
2011-09-12T15:51:41.037Z
2011-09-12T15:51:41.037Z
David Eppstein
<p>going on with @peter's answer here's a worst case posibilities list for each cell as you are filling it in starting from top left</p>

<pre><code>9   8   7       6   5   4       3   2   1
6   5   4       6   5   4       3   2   1
3   2   1       3   2   1       3   2   1

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

3   3   3       3   3   3       1   1   1
2   2   2       2   2   2       1   1   1
1   1   1       1   1   1       1   1   1
</code></pre>

<p>this makes for 4,24559E+29 posibilities or 99 bits</p>

<p>edit: forgot that last square is fully determined by all others</p>

CC BY-SA 3.0
2011-09-09T21:29:48.190Z
Very nice!! Let me add that it's not clear to me that you could ever achieve these worst-case possibilities for a real Sudoku solution (especially if you use a sophisticated algorithm that uses some Sudoku techniques to narrow down the possibilies for which numbers can go in a cell).
Peter Shor 
CC BY-SA 3.0
2011-09-09T21:38:16.583Z
@peter but you need to add those narrowing in e-n and decoding and I realized that if you have to choose one and don't fix the order (easiest way but not optimal really), you need to add that to the encoding as well
ratchet freak
CC BY-SA 3.0
2011-09-09T21:44:52.580Z
No, if you use the same algorithm for figuring out the best cell in the en- and the decoding procedure, it will give the same cell (since it's working on the same data), so the en- and decoding procedures will be synchronized, and you don't have to add the order to the encoding. This idea also makes the LZW data compression algorithm work.
Peter Shor 
CC BY-SA 3.0
2011-09-10T00:37:16.747Z
I think that the *minimum bits* required to store a valid sudoku puzzle is not a computable function (Kolmogorov). However the 103 bits by Peter/ratchet seems a good bound.
Marzio De Biasi
CC BY-SA 3.0
2011-09-10T01:01:04.060Z
@Vor: what you say is true for generalized sudoku, where the board could be $n \times n$. However, in the setting where the board is limited to $9 \times 9$ (and only one decimal digit can go in each cell) the number of possible puzzles is finite, and we could calculate best possible compression for each one, in principle.
Aaron Sterling
CC BY-SA 3.0
2011-09-10T01:01:21.323Z
@vor it has a explicit lowerbound (the 73 bits mentioned in the comments)
ratchet freak
CC BY-SA 3.0
2011-09-10T01:13:23.383Z
A cool example of the computation of a finite prefix of an uncomputable sequence is [Computing a Glimpse of Randomness](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.163.9446), which computes the first 63 bits of Chaitin's Omega.
Aaron Sterling
CC BY-SA 3.0
2011-09-10T01:14:38.743Z
@ratchet: you're right but the 73 bits needs a "lookup table" (and the question doesn't allow it).
Marzio De Biasi
CC BY-SA 3.0
2011-09-10T01:15:27.010Z
@Aaron: you must fix an UTM, but in order to calculate the best compression for each valid sudoku you must also fix a bound on time and/or space, too. However I just found that the minimum number of givens required for an unique solution is 17 ...  :-D :-D
Marzio De Biasi
CC BY-SA 3.0
2011-09-10T01:34:15.533Z
@Vor: Technically the Turing machine that outputs the correct number of bits when given a sudoku puzzle as input is finite because the input set is finite, so "how many bits are needed to describe this puzzle" is "trivially" computable. I'm saying that we could actually find such a Turing machine explicitly (in principle, the computations would take way too long), because it can't be harder than computing a finite prefix of an Omega number.
Aaron Sterling
CC BY-SA 3.0
2011-09-10T01:45:10.427Z
@Aaron: you are right (... Given the first n bits of $\Omega_U$, one can decide whether $U(x)$ halts or not on an arbitrary string x of length at most n ...). Thanks for the good (and interesting) article !
Marzio De Biasi
CC BY-SA 3.0
2011-09-10T13:17:06.960Z
The center of the center should be 4. After all, you can freely fill the center square top 3 with 6 5 4 and the left side with 5 4, then you have 5 used values, and only 4 left for the middle cell. Sadly this doesn't save you a bit.
Dorus
CC BY-SA 3.0
2011-09-09T20:46:31.880Z
2011-09-10T00:38:23.717Z
2011-09-10T00:38:23.717Z
ratchet freak
<p>You don't need a full look-up table to achieve optimal compressibility. I believe that modern computers using a very reasonable look-up table are able to count the number of <em>constrained</em> Sudokus, which are Sudokus with some digits already in place. Using this, here's how you encode (decoding is similar).</p>

<p>Fix an ordering of the squares. Suppose the number on the first square is $d_1$. Put $N_1$ to be the number of Sudokus whose first square is less than $d_1$. Let now $d_2$ be the number of the second square. Put $N_2$ to be the number of Sudokus whose first square is $d_1$ and whose second square is less than $d_2$. And so on. The encoded number is $N = \sum_i N_i$.</p>

<p>This method of encoding is known as <em>binomial encoding</em> in the literature. It should enable you to effectively (in a real-world sense) calculate the index of any given Sudoku, and vice versa. You will then require only $72.4$ bits, as alluded to above (this means that you could code several of them with that average number of bits).</p>

<p>Edit: The Wikipedia page on the <a href="http://en.wikipedia.org/wiki/Mathematics_of_Sudoku#Method_and_algorithm_details_for_the_9.C3.979_grid_direct_enumeration" rel="nofollow">mathematics of Sudoku</a> helps us clarify the picture. Also helpful is a table compiled by <a href="http://www.afjarvis.staff.shef.ac.uk/sudoku/ed44.html" rel="nofollow">Ed Russell</a>.</p>

<p>It turns out that if you consider only the top three rows, then there are essentially only 44 different configurations to consider. In the table, you can find the total number of configurations equivalent to any given one (assuming that the top row is 123456789), and the total number of completions of each one. Given a Sudoku, here is how we would compute its ordinal number:</p>

<ol>
<li>Normalize the configuration so that its top row is 123456789.</li>
<li>Find out which of the 44 different configurations it belongs to. The Wikipedia article gives an algorithm for that. The table lists the number of equivalence classes for each configuration, as well as the number of completions.</li>
<li>Determine the ordinal number of the configuration of the top three rows inside its equivalence class. This can be done in two ways: either using a list of all the equivalence class (there are 36288 in total in all equivalence classes), or by finding a way to quickly enumerate all of them.</li>
<li>Normalize the remaining rows by sorting rows 4-6 and 7-9 by their first column, and then sorting these two blocks of rows in some arbitrary way. This reduces the number of completions by a factor of 72.</li>
<li>Enumerate all completions having the same first column. There are about $2^{20}$ of them for each equivalence class, so that shouldn't take too long. Some tradeoffs are possible here as well.</li>
<li>Let $i$ be the equivalence class, $j$ be the ordinal number of the configuration of the top three rows within the equivalence class, $k$ be the ordinal number of the completion. There are two arrays $C_i,D_i$ (which can be computed from Ed Russell's table) such that $C_i + jD_i + k$ is the ordinal number of the Soduko up to the $9! \cdot 72$ symmetries considered. From that you can compute the actual ordinal number.</li>
</ol>

<p>This procedure is reversible, and will generate a Sudoku from an ordinal number. Note that Sudoku enumeration has been reduced to a few minutes (in 2006; see the talk page of the Wikipedia article) or less, so I expect that on a modern computer this approach would be very practical and take a few seconds or less.</p>

CC BY-SA 3.0
2011-09-11T20:04:22.400Z
Is it possible to count the solutions to constrained sudoku efficiently?  It is #P-complete if you generalize the size and you allow blanks in arbitrary places.
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-12T02:55:23.823Z
do you have a reference for binomial encoding?
v s
CC BY-SA 3.0
2011-09-12T04:52:02.737Z
As I alluded to in my answer, [arithmetic encoding](http://en.wikipedia.org/wiki/Arithmetic_coding) will achieve near-optimal compression for this scenario.
Peter Shor 
CC BY-SA 3.0
2011-09-12T21:00:33.003Z
@v s: I found one at some point, keep looking.
Yuval Filmus
CC BY-SA 3.0
2011-09-12T21:02:42.950Z
@Tsuyoshi: It is entirely irrelevant whether it is #P-complete or even computable for general $n$. The case $n=9$ is easy enough to calculate on a modern computer. Whether it is possible to realize the finer counting needed for this binomial/arithmetic encoding, I have no idea, but I suspect that it is.
Yuval Filmus
CC BY-SA 3.0
2011-09-12T21:33:07.113Z
You might be right, but your claim implies that the number of sudoku grids (6.67×10^21) is easy to compute on a modern computer.  It is indeed possible to compute, but is it easy?
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-13T22:20:18.043Z
I got that impression from one of the papers describing how to do the calculation. You could even calculate some of the "heavier" data in preprocessing and store it in a reasonably-sized table - the speed gains can be dramatic. As far as I remember, it took them only a few hours, and that some years ago. Now suppose you use a table to make it 1000 times as fast. What's more, at each stage the numbers decrease exponentially, so most of the work is probably concentrated at the first stage.
Yuval Filmus
CC BY-SA 3.0
2011-09-15T01:03:59.993Z
@tsuyoshi I _believe_ that there's some version/extension of BDDs that makes the computation relatively straightforward - I'd need to do a little bit of digging for it, but I know that they've been used for some fairly complicated combinatorial counting problems.
Steven Stadnicki
CC BY-SA 3.0
2011-09-15T12:41:14.203Z
Yuval, @Steven: Thank you for the additional information.  I had an (incorrect) impression that the computation took a long time (more than a few hours), but I must have been confusing it with some other computation.
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-11T19:57:14.227Z
2013-01-28T22:43:39.590Z
2013-01-28T22:43:39.590Z
Yuval Filmus
<p>Here's an algorithm which I suspect will produce a pretty good encoding. You have the finished sudoku you want to compress, and let's say you have already encoded some cells of it, so there's a partial sudoku (not necessarily with a unique solution) with some cells filled in. </p>

<p>Use a fixed algorithm to count how many numbers can be placed into every empty cell. Find the lexicographically first cell into which the smallest number of different numbers can be placed, and encode which one of these numbers goes into it (so if a cell can only contain a 3, 7, or 9, the 3 is encoded by "0", the 7 by "1" and the 9 by "2"). Encode the resulting sequence using arithmetic coding (which takes into account the number of possible numbers that a cell can contain). </p>

<p>I don't know how long the resulting binary sequence will be, but I suspect it's pretty short, especially if your algorithm for counting how many numbers can be placed into a cell is reasonably sophisticated. </p>

<p>If you had a good algorithm that estimated the probability of each cell containing a given number, you could do even better.</p>

CC BY-SA 3.0
2011-09-09T18:37:59.017Z
2011-09-09T18:37:59.017Z
Peter Shor 
<p><strong>Any comments and criticisms welcome</strong></p>

<p>An approach from compressed sensing seems to provide a range from $69.96$bits to $171.72$bits:</p>

<p>1.)Storing the puzzle implies storing the solution (information theoretically).</p>

<p>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$). <a href="http://www.usatoday.com/news/offbeat/2006-11-06-sudoku_x.htm" rel="nofollow">http://www.usatoday.com/news/offbeat/2006-11-06-sudoku_x.htm</a> </p>

<p>Hence, we have a vector $P$ of length $\alpha^{4}$ that have atmost $t(\alpha)\alpha^{2}$ non-zero entries.</p>

<p>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.</p>

<p>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\}$.</p>

<p>5.) Storing $V$ needs $\beta\log{\alpha^{2}} = 2kt(\alpha)\alpha^{2}\log{\alpha}$ bits.</p>

<p>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.</p>

<p>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.</p>

<p>$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.</p>

<p>$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)}$.</p>

<p>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.</p>

<p>$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$.</p>

<p>$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}$.</p>

<p>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.</p>

CC BY-SA 3.0
2011-09-10T01:10:42.467Z
2011-09-11T02:11:00.793Z
2011-09-11T02:11:00.793Z
v s
<p>This is to report an implementation of completed-sudoku compact encoding (similar to suggestion by Zurui Wang 9/14/11).</p>

<p>The input is the top row and 1st 3 digits of the 2nd row.  These are reduced to 1-9!
and 1-120 and combined to &lt;=  4.4x10^7. These are used as givens to count lexicographically all the partial sukokus of 30 digits up to the matching sequence.  Then the final count up to the entire 81 digits is done the same way.  These 3 sequences are stored as 32-bit integers of max 26 bits, so can be compressed further.  The entire process takes about 3 minutes, with the 1st 30 digits taking most of the time.  The decoding is similar--except matching counts instead of sudokus.  </p>

<p>Coming soon--Revision includes 1st 3 digits of 2nd row in enumeration of 30 digit completions (2nd 32-bit code), comparisons with Jarvis enumeration (Jscott, 3/1615)</p>

CC BY-SA 3.0
2013-01-28T19:53:19.113Z
2015-03-16T21:28:40.660Z
2015-03-16T21:28:40.660Z
jscott
<p>I would go with the following simple analysis:</p>

<p>Each value could be stored in 4 bits (ranges from 1-9, these three bits even allow for 0-16)</p>

<p>If we considered to store the WHOLE solution (not optimal), having $9 \times 9 = 81$ values. 3 bits each = 243 bits.</p>

<p>However, as the rules that the solved sudoku has to follow, storing every bit is in fact redundant. However, since the order is important, you need to store the first 8 values in each  row (thus determining the 9th value), for 8 rows (thus determining the last row). This reduces the sudoku to $8 \times 8$ for 3 bits, 192 bits (24 bytes).</p>

<p>I guess I could reduce it to:</p>

<p>$b = \lceil \log_2(v) \rceil  (n-1)$</p>

<p>where</p>

<p>$v$ = range of values (I've seen 0-5 sudokus a lot)</p>

<p>$n$ = number of rows / columns</p>

<p><strong>Edit:</strong> <em>Neo Style:</em> I know Latex.</p>

CC BY-SA 3.0
2011-09-15T00:01:18.083Z
2011-09-15T00:10:50.860Z
2011-09-15T00:10:50.860Z
Alpha
<p>That number is different for each Sudoku. One of the rules for Sudoku is that it has exactly one solution.</p>

<p>So if you look at an example, that's the minimum amount of data that you must store.</p>

<p>If you work from the opposite side, you can remove digit by digit and run a solver on the result to see if it still has exactly one solution. If so, you can delete another digit. If not, you must restore this digit and try another. If you can't, you have found a minimum.</p>

<p>Since most puzzles start mostly empty, a run length encoding will probably yield good results.</p>

CC BY-SA 3.0
2011-09-09T15:39:18.663Z
This greedy approach not necessarily achieves the minimum, perhaps you need to select carefully which digit to remove in each step.
didest
CC BY-SA 3.0
2011-09-09T15:45:35.320Z
It's just an example. Google for "sudoku puzzle generators" to get more sophisticated ones.
Aaron Digulla
CC BY-SA 3.0
2011-09-12T15:45:45.997Z
I really don't see why you would expect this to perform particularly well. This just seems to be gut feeling rather than an answer.
Joe Fitzsimons
CC BY-SA 3.0
2011-09-09T14:57:18.457Z
2011-09-09T14:57:18.457Z
Aaron Digulla
<p>Note: This is about the standard 9x9 sudoku puzzle. The solution only has to support <strong>solved, legal puzzles</strong>. So a solution doesn't need to support empty cells and can rely on the properties of a solved sudoku puzzle.</p>

<p>I was wondering this, but I couldn't think of an answer that I was content with. A naive solution would use one byte for each cell (81 cells), totalling 648 bits. A more sophisticated solution would store the entire sudoku puzzle in a base-9 number (one digit per cell) and require $\lceil\log_2(9^{81}))\rceil = 257$ bits.</p>

<p>But it can still be improved, for example, if you know 8 of the 9 numbers in a 3x3 subgrid you can trivially deduce the 9th. You can continue these thoughts to the point where this question boils down to <strong>What is the amount of unique solved sudokus?</strong> Now you can use a huge lookup table that maps each binary number to a sudoku puzzle, but that wouldn't be an usable solution.</p>

<p>So, my question:</p>

<h3>Without using a lookup table, what is the minimum amount of bits required to store a sudoku puzzle and with what algorithm?</h3>

CC BY-SA 3.0
2011-09-09T14:40:16.847Z
Is there really a qualitative difference between leaving out the 9th number in a 3x3, row, or column and just storing the minimal sudoku with empty spaces that has that unique solution? "doesn't need to support empty cells" is a bit of a red herring if the optimal solution necessarily does need to.
Wooble
CC BY-SA 3.0
2011-09-09T14:49:00.967Z
@Wooble: It's mainly to exclude non-solved sudokus with multiple solutions. It doesn't need to, but if your algorithm uses empty spaces, go ahead!
orlp
CC BY-SA 3.0
2011-09-09T15:46:25.697Z
Because [there are 6.67×10^21 solved sudoku](http://www.afjarvis.staff.shef.ac.uk/sudoku/) (“QSCGZ” 2003; Felgenhauer and Jarvis 2005) and log_2 (6.67×10^21) = 72.4…, a lower bound is 73 bits (even if you use the huge table lookup).  If you do not have to distinguish essentially identical solutions in terms of symmetry, this lower bound does not apply.
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-11T04:43:29.917Z
This question would make for a good programming contest.
Peter Shor 
CC BY-SA 3.0
2011-09-13T16:14:17.093Z
The analogous lower bound for essentially identical solutions is 33 bits.
Charles
CC BY-SA 3.0
2011-09-14T10:54:09.140Z
Why do you need a look up table? You can just enumerate Sudoku solutions one by one until reaching the desired number.
Zirui Wang
CC BY-SA 3.0
2014-12-12T08:46:25.790Z
Now on codegolf.SE: http://codegolf.stackexchange.com/questions/41523/sudoku-compression accepted answer has 76 bits
ratchet freak
<co.combinatorics><puzzles>
What is the minimum number of bits required to store a sudoku puzzle?
orlp
# What is the minimum number of bits required to store a sudoku puzzle?

(Asked by: username_0 on 2011-09-09)

Note: This is about the standard 9x9 sudoku puzzle. The solution only has to support **solved, legal puzzles**. So a solution doesn't need to support empty cells and can rely on the properties of a solved sudoku puzzle.

I was wondering this, but I couldn't think of an answer that I was content with. A naive solution would use one byte for each cell (81 cells), totalling 648 bits. A more sophisticated solution would store the entire sudoku puzzle in a base-9 number (one digit per cell) and require $\lceil\log\_2(9^{81}))\rceil = 257$ bits.

But it can still be improved, for example, if you know 8 of the 9 numbers in a 3x3 subgrid you can trivially deduce the 9th. You can continue these thoughts to the point where this question boils down to **What is the amount of unique solved sudokus?** Now you can use a huge lookup table that maps each binary number to a sudoku puzzle, but that wouldn't be an usable solution.

So, my question:

### Without using a lookup table, what is the minimum amount of bits required to store a sudoku puzzle and with what algorithm?

**Tags:** co.combinatorics, puzzles

> **Comments:**
> **username_1**: Is there really a qualitative difference between leaving out the 9th number in a 3x3, row, or column and just storing the minimal sudoku with empty spaces that has that unique solution? "doesn't need to support empty cells" is a bit of a red herring if the optimal solution necessarily does need to.  
> **username_0**: @username_1: It's mainly to exclude non-solved sudokus with multiple solutions. It doesn't need to, but if your algorithm uses empty spaces, go ahead!  
> **username_2**: Because [there are 6.67×10^21 solved sudoku](http://www.afjarvis.staff.shef.ac.uk/sudoku/) (“QSCGZ” 2003; Felgenhauer and Jarvis 2005) and log_2 (6.67×10^21) = 72.4…, a lower bound is 73 bits (even if you use the huge table lookup).  If you do not have to distinguish essentially identical solutions in terms of symmetry, this lower bound does not apply.  
> **username_3**: This question would make for a good programming contest.  
> **username_4**: The analogous lower bound for essentially identical solutions is 33 bits.  
> **username_5**: Why do you need a look up table? You can just enumerate Sudoku solutions one by one until reaching the desired number.  
> **username_6**: Now on codegolf.SE: http://codegolf.stackexchange.com/questions/41523/sudoku-compression accepted answer has 76 bits  

---

## 8 answers

### Answer by username_7 on 2011-09-10. Score: 20

Along the same lines as username_6'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.

> **Comments:**
> **username_3**: You can reduce the number of choices when you fill in the sixth 3x3 box, as well. This box becomes 4,3,2 / 3,2,1 / 2,1,1 for a total of 83 bits, if I calculated it correctly.  
> **username_8**: @Peter - nope.  The 3 numbers to the right could be the same as the numbers above.  You don't know all of them are distinct.  The most assured unique numbers are 3 so the first box is a pick from six items.  (This one location is an example.  It is true for the others too.)  
> **username_8**: @David - going by my comment to Peter I don't think your numbers are wrong.  In the 2nd box you have `6 5 4 4 3 2 3 2 1` I believe it needs to be `6 5 4 6 5 4 3 2 1` for the worst case.  
> **username_7**: username_8, no, see the part in my answer about "once you've filled in one row or column of the box, you can always choose the next row or column to fill in to be one in which there are at most four possible values"  
> **username_8**: @David - Lets label the 3 x 3s 1,1 1,2 1,3 going left to right top to bottom.  Let lable the Squares A - I going left to right top to bottom.  The location D in 1,3 knows 3 numbers in the 3x3 it is in (A,B,C) and it knows 3 numbers in 1,2 (D,E,F) but it does not know those 6 numbers are different.  They could be the same 3 numbers from box 3,1 and 2,1 thus there are MAX 6 choices.  
> **username_8**: @David -- I see you are saying you might fill in (G,H,I) or (D,E,F) in box 1,3 (Depending on the duplicates with (D,E,F/G,H,I) in box 1,2 -- Good point.  It seems following the same method Peter is right for box 3,2  
> **username_3**: My analysis was wrong. You can get 4,3,3,3,3,3,2,1,1 without too much work. As David says, for the sixth box, it's easy to see that every number can go into four cells. After you've put the first number in, there will always be some number that goes into at most three cells, and if you look at the last four cells, you can show that these take at most 3,2,1,1. This is a simple case analysis, using the observation that if the last three cells are in all different rows or all different columns, you get 2,1,1. This gives 85 bits. I'm sure you can do better, but it would take some more work.  
> **username_3**: And looking at the last five cells, a case analysis gives 4,3,3,3,3,2,2,1,1, which saves another half bit, giving a grand total of 84 bits. You're not going to do any better than 4,3,3,2,2,2,2,1,1 with this method, which would give 83 bits. And even if you can save another bit, it'll be a lot more work, so I'm stopping here.  

---

### Answer by username_6 on 2011-09-09. Score: 13

going on with @peter's answer here's a worst case posibilities list for each cell as you are filling it in starting from top left
9   8   7       6   5   4       3   2   1
6   5   4       6   5   4       3   2   1
3   2   1       3   2   1       3   2   1

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

3   3   3       3   3   3       1   1   1
2   2   2       2   2   2       1   1   1
1   1   1       1   1   1       1   1   1

this makes for 4,24559E+29 posibilities or 99 bits
edit: forgot that last square is fully determined by all others

> **Comments:**
> **username_3**: Very nice!! Let me add that it's not clear to me that you could ever achieve these worst-case possibilities for a real Sudoku solution (especially if you use a sophisticated algorithm that uses some Sudoku techniques to narrow down the possibilies for which numbers can go in a cell).  
> **username_6**: @peter but you need to add those narrowing in e-n and decoding and I realized that if you have to choose one and don't fix the order (easiest way but not optimal really), you need to add that to the encoding as well  
> **username_3**: No, if you use the same algorithm for figuring out the best cell in the en- and the decoding procedure, it will give the same cell (since it's working on the same data), so the en- and decoding procedures will be synchronized, and you don't have to add the order to the encoding. This idea also makes the LZW data compression algorithm work.  
> **username_9**: I think that the *minimum bits* required to store a valid sudoku puzzle is not a computable function (Kolmogorov). However the 103 bits by Peter/ratchet seems a good bound.  
> **username_10**: @Vor: what you say is true for generalized sudoku, where the board could be $n \times n$. However, in the setting where the board is limited to $9 \times 9$ (and only one decimal digit can go in each cell) the number of possible puzzles is finite, and we could calculate best possible compression for each one, in principle.  
> **username_6**: @vor it has a explicit lowerbound (the 73 bits mentioned in the comments)  
> **username_10**: A cool example of the computation of a finite prefix of an uncomputable sequence is [Computing a Glimpse of Randomness](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.163.9446), which computes the first 63 bits of Chaitin's Omega.  
> **username_9**: @ratchet: you're right but the 73 bits needs a "lookup table" (and the question doesn't allow it).  
> **username_9**: @Aaron: you must fix an UTM, but in order to calculate the best compression for each valid sudoku you must also fix a bound on time and/or space, too. However I just found that the minimum number of givens required for an unique solution is 17 ...  :-D :-D  
> **username_10**: @Vor: Technically the Turing machine that outputs the correct number of bits when given a sudoku puzzle as input is finite because the input set is finite, so "how many bits are needed to describe this puzzle" is "trivially" computable. I'm saying that we could actually find such a Turing machine explicitly (in principle, the computations would take way too long), because it can't be harder than computing a finite prefix of an Omega number.  
> **username_9**: @Aaron: you are right (... Given the first n bits of $\Omega_U$, one can decide whether $U(x)$ halts or not on an arbitrary string x of length at most n ...). Thanks for the good (and interesting) article !  
> **username_11**: The center of the center should be 4. After all, you can freely fill the center square top 3 with 6 5 4 and the left side with 5 4, then you have 5 used values, and only 4 left for the middle cell. Sadly this doesn't save you a bit.  

---

### Answer by username_12 on 2011-09-11. Score: 5

You don't need a full look-up table to achieve optimal compressibility. I believe that modern computers using a very reasonable look-up table are able to count the number of *constrained* Sudokus, which are Sudokus with some digits already in place. Using this, here's how you encode (decoding is similar).

Fix an ordering of the squares. Suppose the number on the first square is $d\_1$. Put $N\_1$ to be the number of Sudokus whose first square is less than $d\_1$. Let now $d\_2$ be the number of the second square. Put $N\_2$ to be the number of Sudokus whose first square is $d\_1$ and whose second square is less than $d\_2$. And so on. The encoded number is $N = \sum\_i N\_i$.

This method of encoding is known as *binomial encoding* in the literature. It should enable you to effectively (in a real-world sense) calculate the index of any given Sudoku, and vice versa. You will then require only $72.4$ bits, as alluded to above (this means that you could code several of them with that average number of bits).

Edit: The Wikipedia page on the [mathematics of Sudoku](http://en.wikipedia.org/wiki/Mathematics_of_Sudoku#Method_and_algorithm_details_for_the_9.C3.979_grid_direct_enumeration) helps us clarify the picture. Also helpful is a table compiled by [Ed Russell](http://www.afjarvis.staff.shef.ac.uk/sudoku/ed44.html).

It turns out that if you consider only the top three rows, then there are essentially only 44 different configurations to consider. In the table, you can find the total number of configurations equivalent to any given one (assuming that the top row is 123456789), and the total number of completions of each one. Given a Sudoku, here is how we would compute its ordinal number:

1. Normalize the configuration so that its top row is 123456789.
2. Find out which of the 44 different configurations it belongs to. The Wikipedia article gives an algorithm for that. The table lists the number of equivalence classes for each configuration, as well as the number of completions.
3. Determine the ordinal number of the configuration of the top three rows inside its equivalence class. This can be done in two ways: either using a list of all the equivalence class (there are 36288 in total in all equivalence classes), or by finding a way to quickly enumerate all of them.
4. Normalize the remaining rows by sorting rows 4-6 and 7-9 by their first column, and then sorting these two blocks of rows in some arbitrary way. This reduces the number of completions by a factor of 72.
5. Enumerate all completions having the same first column. There are about $2^{20}$ of them for each equivalence class, so that shouldn't take too long. Some tradeoffs are possible here as well.
6. Let $i$ be the equivalence class, $j$ be the ordinal number of the configuration of the top three rows within the equivalence class, $k$ be the ordinal number of the completion. There are two arrays $C\_i,D\_i$ (which can be computed from Ed Russell's table) such that $C\_i + jD\_i + k$ is the ordinal number of the Soduko up to the $9! \cdot 72$ symmetries considered. From that you can compute the actual ordinal number.

This procedure is reversible, and will generate a Sudoku from an ordinal number. Note that Sudoku enumeration has been reduced to a few minutes (in 2006; see the talk page of the Wikipedia article) or less, so I expect that on a modern computer this approach would be very practical and take a few seconds or less.

> **Comments:**
> **username_2**: Is it possible to count the solutions to constrained sudoku efficiently?  It is #P-complete if you generalize the size and you allow blanks in arbitrary places.  
> **username_13**: do you have a reference for binomial encoding?  
> **username_3**: As I alluded to in my answer, [arithmetic encoding](http://en.wikipedia.org/wiki/Arithmetic_coding) will achieve near-optimal compression for this scenario.  
> **username_12**: @username_13: I found one at some point, keep looking.  
> **username_12**: @Tsuyoshi: It is entirely irrelevant whether it is #P-complete or even computable for general $n$. The case $n=9$ is easy enough to calculate on a modern computer. Whether it is possible to realize the finer counting needed for this binomial/arithmetic encoding, I have no idea, but I suspect that it is.  
> **username_2**: You might be right, but your claim implies that the number of sudoku grids (6.67×10^21) is easy to compute on a modern computer.  It is indeed possible to compute, but is it easy?  
> **username_12**: I got that impression from one of the papers describing how to do the calculation. You could even calculate some of the "heavier" data in preprocessing and store it in a reasonably-sized table - the speed gains can be dramatic. As far as I remember, it took them only a few hours, and that some years ago. Now suppose you use a table to make it 1000 times as fast. What's more, at each stage the numbers decrease exponentially, so most of the work is probably concentrated at the first stage.  
> **username_14**: @tsuyoshi I _believe_ that there's some version/extension of BDDs that makes the computation relatively straightforward - I'd need to do a little bit of digging for it, but I know that they've been used for some fairly complicated combinatorial counting problems.  
> **username_2**: Yuval, @Steven: Thank you for the additional information.  I had an (incorrect) impression that the computation took a long time (more than a few hours), but I must have been confusing it with some other computation.  

---

### Answer by username_3 on 2011-09-09. Score: 4

Here's an algorithm which I suspect will produce a pretty good encoding. You have the finished sudoku you want to compress, and let's say you have already encoded some cells of it, so there's a partial sudoku (not necessarily with a unique solution) with some cells filled in.

Use a fixed algorithm to count how many numbers can be placed into every empty cell. Find the lexicographically first cell into which the smallest number of different numbers can be placed, and encode which one of these numbers goes into it (so if a cell can only contain a 3, 7, or 9, the 3 is encoded by "0", the 7 by "1" and the 9 by "2"). Encode the resulting sequence using arithmetic coding (which takes into account the number of possible numbers that a cell can contain).

I don't know how long the resulting binary sequence will be, but I suspect it's pretty short, especially if your algorithm for counting how many numbers can be placed into a cell is reasonably sophisticated.

If you had a good algorithm that estimated the probability of each cell containing a given number, you could do even better.


---

### Answer by username_13 on 2011-09-10. Score: 3

**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.


---

### Answer by username_15 on 2013-01-28. Score: 1

This is to report an implementation of completed-sudoku compact encoding (similar to suggestion by Zurui Wang 9/14/11).

The input is the top row and 1st 3 digits of the 2nd row. These are reduced to 1-9!
and 1-120 and combined to <= 4.4x10^7. These are used as givens to count lexicographically all the partial sukokus of 30 digits up to the matching sequence. Then the final count up to the entire 81 digits is done the same way. These 3 sequences are stored as 32-bit integers of max 26 bits, so can be compressed further. The entire process takes about 3 minutes, with the 1st 30 digits taking most of the time. The decoding is similar--except matching counts instead of sudokus.

Coming soon--Revision includes 1st 3 digits of 2nd row in enumeration of 30 digit completions (2nd 32-bit code), comparisons with Jarvis enumeration (Jscott, 3/1615)


---

### Answer by username_16 on 2011-09-15. Score: 0

I would go with the following simple analysis:

Each value could be stored in 4 bits (ranges from 1-9, these three bits even allow for 0-16)

If we considered to store the WHOLE solution (not optimal), having $9 \times 9 = 81$ values. 3 bits each = 243 bits.

However, as the rules that the solved sudoku has to follow, storing every bit is in fact redundant. However, since the order is important, you need to store the first 8 values in each row (thus determining the 9th value), for 8 rows (thus determining the last row). This reduces the sudoku to $8 \times 8$ for 3 bits, 192 bits (24 bytes).

I guess I could reduce it to:

$b = \lceil \log\_2(v) \rceil (n-1)$

where

$v$ = range of values (I've seen 0-5 sudokus a lot)

$n$ = number of rows / columns

**Edit:** *Neo Style:* I know Latex.


---

### Answer by username_17 on 2011-09-09. Score: -2

That number is different for each Sudoku. One of the rules for Sudoku is that it has exactly one solution.

So if you look at an example, that's the minimum amount of data that you must store.

If you work from the opposite side, you can remove digit by digit and run a solver on the result to see if it still has exactly one solution. If so, you can delete another digit. If not, you must restore this digit and try another. If you can't, you have found a minimum.

Since most puzzles start mostly empty, a run length encoding will probably yield good results.

> **Comments:**
> **username_18**: This greedy approach not necessarily achieves the minimum, perhaps you need to select carefully which digit to remove in each step.  
> **username_17**: It's just an example. Google for "sudoku puzzle generators" to get more sophisticated ones.  
> **username_19**: I really don't see why you would expect this to perform particularly well. This just seems to be gut feeling rather than an answer.  

---

