Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question
3  
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 Sep 9 '11 at 14:40
    
@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! –  nightcracker Sep 9 '11 at 14:49
17  
Because there are 6.67×10^21 solved 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 Sep 9 '11 at 15:46
8  
This question would make for a good programming contest. –  Peter Shor Sep 11 '11 at 4:43
2  
Why do you need a look up table? You can just enumerate Sudoku solutions one by one until reaching the desired number. –  Zirui Wang Sep 14 '11 at 10:54
show 1 more comment

8 Answers

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.

share|improve this answer
4  
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 Sep 10 '11 at 17:19
    
@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 Sep 11 '11 at 2:33
    
@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 Sep 11 '11 at 2:38
    
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 Sep 11 '11 at 2:40
    
@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 Sep 11 '11 at 2:45
show 3 more comments

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

share|improve this answer
    
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 Sep 9 '11 at 21:29
    
@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 Sep 9 '11 at 21:38
    
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 Sep 9 '11 at 21:44
    
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 Sep 10 '11 at 0:37
2  
@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 Sep 10 '11 at 1:34
show 7 more comments

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.

share|improve this answer
add comment

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 helps us clarify the picture. Also helpful is a table compiled by Ed Russell.

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.

share|improve this answer
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. –  Tsuyoshi Ito Sep 11 '11 at 20:04
2  
As I alluded to in my answer, arithmetic encoding will achieve near-optimal compression for this scenario. –  Peter Shor Sep 12 '11 at 4:52
1  
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 Sep 12 '11 at 21:33
2  
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 Sep 13 '11 at 22:20
1  
@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 Sep 15 '11 at 1:03
show 4 more comments

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
    
This greedy approach not necessarily achieves the minimum, perhaps you need to select carefully which digit to remove in each step. –  Diego de Estrada Sep 9 '11 at 15:39
    
It's just an example. Google for "sudoku puzzle generators" to get more sophisticated ones. –  Aaron Digulla Sep 9 '11 at 15:45
5  
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 Sep 12 '11 at 15:45
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.