# The minimal Anti-Sudoku

Suppose we succumb to the urge to fill in a normal Sudoku grid as badly as we possibly can. That is, we strive to enter the digits from 1 to 9 nine times each such that no row, column or box contains any number exactly once. Let's call such an atrocity an Anti-Sudoku.

Can you find the (lexicographically) minimal Anti-Sudoku?

(To be clear, this means that you have to minimize the 81-digit number that you obtain from the finished grid in reading order.)

For convenience, here is an empty grid for you to play around in. Have fun! :)

### Strategy

We already have a computer solution, so I will try to show how a human can obtain it. The strategy is to set the numbers $$1,2,\dots,9$$ on the anti-sudoku grid one by one. Let $$A$$ be the minimal solution. Denote the intermediate state

$$A(k) = \text{the grid when we remove from }A\text{ all entries strictly bigger than }k.$$

We will build partial grids. A partial grid is valid if it can be completed to satisfy the anti-sudoku rules (or else it is invalid). A partial grid is minimal if it is minimal among all valid partial grids with the same multi-set of numbers.

We will find $$A$$ by sequentially finding the states $$A(1), A(2),\dots,A(9)=A$$.

### Rules

As a guide for building minimal partial grids, we observe the following useful rules to identify invalid partial grids:

Rule (R): A partial grid is invalid if in a row, column, or box there is exactly one Remaining unfilled cell.

Rule (S): A partial grid in which a row, column, or box has exactly two unfilled cells must be filled with the Same value in those two cells.

Rule (T) (Corollary to Rule (S)): A partial grid in which a row, column, or box has exactly Three unfilled cells must be filled with the same value in those Three cells.

(F) Any row, or column of $$A$$ has at most FOUR occurrences of any $$k$$ from $$1$$ to $$9$$. (Otherwise, there will be a row or column that violates (R))

In particular, the $$9$$ occurrences of any $$k$$ have to be partitioned as one of the following: \begin{aligned} 9 &= 4+3+2\\ &= 3+3+3\\ &= 3+2+2+2\ . \end{aligned} The partitions can be realized as follows (up to a permutation of rows/columns, using the $$1$$ instead of a general $$k$$):

(A)            (B)      (B')           (A*)
1 1 1 1        1 1 1    1 1 1          1 1 1    1 1 1    1 1 1
1 1 1          1 1 1    1 1   1        1 1      1 1      1 1
1     1        1 1 1    1   1 1        1 1      1   1    1     1
1   1      1 1        1 1


I will make use only of (A), as follows: If a row has four copies of $$k$$ in columns $$c_1,\dots,c_4$$, then exactly two other rows contain $$k$$, and they must be in columns $$c_1,\dots,c_4$$.

## Notation

• The placement of $$k$$ in position $$(i,j)$$ will be denoted by $$k(i,j)$$.
• Unfilled rows are not displayed.
• Unfilled cells are marked by a dot, empty space, or a letter which stands for a digit larger than all currently-filled digits.
• The same letter stands for the same digit; different letters don't necessarily stand for different digits.

## Building the states

• $$(1)$$ The minimal placement of the $$1$$'s in $$A(0)$$ is by (F):

  1 1 1 1 . . . . .
1 1 1 . . . . . .
1 . . 1 . . . . .


If this $$A(1)$$ is valid, then this grid is minimal.

• $$(2)$$ The minimal placement of the $$2$$'s in $$A(1)$$ is the following:

  1 1 1 1 2 2 2 . .
1 1 1 2 2 2 2 . .
1 . . 1 . . . . .
. . . 2 2 . . . .


We place as many $$2$$'s as early as possible ($$\le 4$$ by (F) and $$\le 3$$ by (T)). So $$2,2,2$$ come on the first row and $$2,2,2,2$$ on the second row are minimal if valid. Now column $$4$$ is unmatched, so the minimal move is $$2(4,4)$$ (recall the notation, this means that a $$2$$ is placed in the grid at position $$(4,4)$$). Now row $$4$$ is unmatched, so the minimal placement for the last $$2$$ is $$2(4,5)$$.

If this $$A(2)$$ is valid, then this grid is minimal.

• $$(3)$$ We fill in the first two rows in a minimal manner. There remain $$9-4=5$$ pieces of $$3$$. The third row can minimally be then completed with two of them as follows:

  1 1 1 1 2 2 2 3 3
1 1 1 2 2 2 2 3 3
1 3 3 1 . . . . .
. . . 2 2 . . . .


Three pieces of $$3$$ are to be placed still. The second and third columns are unmatched (recall (R)), so we try:

  1 1 1 1 2 2 2 3 3
1 1 1 2 2 2 2 3 3
1 3 3 1 . . . 3 .
. 3 3 2 2 . . . .


If this $$A(3)$$ is valid, then this grid is minimal.

• $$(4)$$ The minimal placement of the first four pieces of $$4$$ in $$A(3)$$ fills the third row completely. Note that the first three boxes are valid so far.

  1 1 1 1 2 2 2 3 3
1 1 1 2 2 2 2 3 3
1 3 3 1 4 4 4 3 4
. 3 3 2 2 . . . .
. . . . . . . . .


We must fill in using the scheme (A) for the splitting $$4+3+2$$. So only these four columns get the remaining five $$4$$ pieces:

  1 1 1 1 2 2 2 3 3
1 1 1 2 2 2 2 3 3
1 3 3 1 4 4 4 3 4
. 3 3 2 2 4 4 . 4
. . . . 4 4 . . .


If this $$A(4)$$ is valid, then it is minimal.

• $$(5)$$ The minimal placement of the first two pieces of $$5$$ in $$A(4)$$ is in the fourth row:

  1 1 1 1 2 2 2 3 3
1 1 1 2 2 2 2 3 3
1 3 3 1 4 4 4 3 4
5 3 3 2 2 4 4 5 4
. . . . 4 4 . . .


Now we try to minimally fill in the next open row. First (rude) attempt:

  INVALID TRY:
1 1 1 1 2 2 2 3 3
1 1 1 2 2 2 2 3 3
1 3 3 1 4 4 4 3 4
5 3 3 2 2 4 4 5 4
5 5 5 5 4 4 . . .


This has no chance. We now have four unmatched columns for the $$5$$ piece, so we need at least four more pieces. So let us think. We placed two $$5$$ pieces in the fourth row. There remain seven pieces. Two of them must match the fixed two. So there remain five pieces. With them we can only occupy two new columns. The minimal placing with two new columns is:

  1 1 1 1 2 2 2 3 3
1 1 1 2 2 2 2 3 3
1 3 3 1 4 4 4 3 4
5 3 3 2 2 4 4 5 4
5 5 5 . 4 4 . 5 .
5 5 5 . . . . . .


If this $$A(5)$$ is valid, then it is minimal.

• $$(6^a)$$ The minimal placement of the pieces of $$6$$ in $$A(5)$$ is with three pieces in the fifth row. We see that the minimal placement on the sixth row is thus:

  1 1 1 1 2 2 2 3 3
1 1 1 2 2 2 2 3 3
1 3 3 1 4 4 4 3 4
5 3 3 2 2 4 4 5 4
5 5 5 6 4 4 6 5 6
5 5 5 6 X X 6 6 6
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .


If this $$A(6^a)$$ is valid, then it's minimal.

The remaining two $$6$$ pieces are in the same row in one of the last three rows. Thus the position $$(i,4)$$ is excluded, since it would be alone in its box. Thus they are in the last box. We postpone their placement, since the positions that determine minimality are not yet established.

• $$(7^a)$$ The minimal placement of the first three pieces of $$7$$ in the above diagram $$A(6^a)$$ is

  1 1 1 1 2 2 2 3 3
1 1 1 2 2 2 2 3 3
1 3 3 1 4 4 4 3 4
5 3 3 2 2 4 4 5 4
5 5 5 6 4 4 6 5 6
5 5 5 6 7 7 6 6 6
7 . . . . . . . .
. . . . . . . . .
. . . . . . . . .


and by (T) the first column gets two more values of $$7$$.

  1 1 1 1 2 2 2 3 3
1 1 1 2 2 2 2 3 3
1 3 3 1 4 4 4 3 4
5 3 3 2 2 4 4 5 4
5 5 5 6 4 4 6 5 6
5 5 5 6 7 7 6 6 6
7 X Y Z . . . . .
7 X Y Z . . . . .
7 X Y Z . . . . .
pieces 6, 6 come in the same row
pieces 7, 7, 7, 7 in columns five, six


If this $$A(7^a)$$ is valid, then it is minimal.

• $$(8^a)$$ The minimal values on the fields $$X,Y,Z$$ in the seventh row are $$8,8,8$$, because $$6,7$$ are excluded on these places. The next two places can be minimally be occupied by $$7,7$$:

  1 1 1 1 2 2 2 3 3
1 1 1 2 2 2 2 3 3
1 3 3 1 4 4 4 3 4
5 3 3 2 2 4 4 5 4
5 5 5 6 4 4 6 5 6
5 5 5 6 7 7 6 6 6
7 8 8 8 7 7 S T U
7 8 8 8 V . . . .
7 8 8 8 W X . . .
pieces 6, 6 come in the same row
pieces 7, 7 in columns five, six


If this $$A(8^a)$$ is valid, it is minimal.

• $$(9)$$ In $$A(8^a)$$, among S T U there is no $$6$$, else both are in this row and the remaining cell violates rule (R). Thus these places are $$9,9,9$$. Then the minimal choice in V is $$7$$. We also minimally position the twins $$6,6$$:

  1 1 1 1 2 2 2 3 3
1 1 1 2 2 2 2 3 3
1 3 3 1 4 4 4 3 4
5 3 3 2 2 4 4 5 4
5 5 5 6 4 4 6 5 6
5 5 5 6 7 7 6 6 6
7 8 8 8 7 7 9 9 9
7 8 8 8 7 . 6 6 .
7 8 8 8 W X . . .


If it is valid, it is minimal:

The missing entries in the eighth row must use a $$9$$, so they are both $$9$$'s. The W is minimally a $$7$$. For X and the next positions we use the remaining $$9$$'s.

## Final Check

It turns out that the obtained anti-sudoku grid is valid: $$\begin{array}{|ccc|ccc|ccc|} \hline 1 & 1 & 1 & 1 & 2 & 2 & 2 & 3 & 3\\ 1 & 1 & 1 & 2 & 2 & 2 & 2 & 3 & 3\\ 1 & 3 & 3 & 1 & 4 & 4 & 4 & 3 & 4\\\hline % 5 & 3 & 3 & 2 & 2 & 4 & 4 & 5 & 4\\ 5 & 5 & 5 & 6 & 4 & 4 & 6 & 5 & 6\\ 5 & 5 & 5 & 6 & 7 & 7 & 6 & 6 & 6\\\hline % 7 & 8 & 8 & 8 & 7 & 7 & 9 & 9 & 9\\ 7 & 8 & 8 & 8 & 7 & 9 & 6 & 6 & 9\\ 7 & 8 & 8 & 8 & 7 & 9 & 9 & 9 & 9\\\hline \end{array}$$ All the time we were making minimal decisions, so this $$A=A(9)$$ is minimal. $$\square$$

• Can you please explain why rule F is true? Thank you Commented Aug 16 at 17:28
• @BenjaminWang Yes, we nine possible "pieces" $k$. Assume we are placing five or more of them in a "special" row at some of the nine places. Each such $k$ from the "special" row must have in its column at least one "match" in some other row, so there are at least $2\cdot 5$ pieces of $k$ needed for this. We have only nine... Commented Aug 16 at 17:45
• Very good explanation, thank you! Commented Aug 16 at 18:20

As a warm-up, here's the lexicographically minimal Sudoku, obtained via integer linear programming, with binary decision variables $$x_{ijk}$$ to indicate whether cell $$(i,j)$$ contains digit $$k$$:

$$\begin{matrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\ 4 & 5 & 6 & 7 & 8 & 9 & 1 & 2 & 3\\ 7 & 8 & 9 & 1 & 2 & 3 & 4 & 5 & 6\\ 2 & 1 & 4 & 3 & 6 & 5 & 8 & 9 & 7\\ 3 & 6 & 5 & 8 & 9 & 7 & 2 & 1 & 4\\ 8 & 9 & 7 & 2 & 1 & 4 & 3 & 6 & 5\\ 5 & 3 & 1 & 6 & 4 & 2 & 9 & 7 & 8\\ 6 & 4 & 2 & 9 & 7 & 8 & 5 & 3 & 1\\ 9 & 7 & 8 & 5 & 3 & 1 & 6 & 4 & 2\\\end{matrix}$$

For each region (row, column, or $$3\times3$$ box) $$r$$, let $$C_r$$ be the set of $$9$$ cells in that region. The constraints are as follows: \begin{align} \sum_{k=1}^9 x_{ijk} &= 1 &&\text{for all cells (i,j)} \tag1\label1 \\ \sum_{(i,j)\in C_r} x_{ijk} &= 1 &&\text{for all regions r and digits k} \tag2\label2 \end{align} Constraint \eqref{1} assigns exactly one digit to each cell. Constraint \eqref{2} assigns each digit to exactly one cell per region. To find the lexicographically minimal solution, first minimize $$\sum_{k=1}^9 k x_{11k}$$, yielding $$1$$, then fix $$x_{111}=1$$ and minimize $$\sum_{k=1}^9 k x_{12k}$$, etc.

For anti-Sudoku, additional binary variables $$y_{rk}$$ indicate whether region $$r$$ contains digit $$k$$ (at least twice). Replace constraint \eqref{2} with the following two constraints: \begin{align} \sum_{i=1}^9 \sum_{j=1}^9 x_{ijk} &= 9 &&\text{for all digits k} \tag3\label3 \\ 2 y_{rk} \le \sum_{(i,j) \in C_r} x_{ijk} &\le 9 y_{rk} &&\text{for all regions r and digits k} \tag4\label4 \end{align} Constraint \eqref{3} uses each digit exactly $$9$$ times. Constraint \eqref{4} forces each digit to be used either $$0$$ or at least $$2$$ times per region. Minimizing $$\sum_{k=1}^9 k x_{ijk}$$ for each cell $$(i,j)$$ one at a time yields the following lexicographically minimal solution:

$$\begin{matrix}1 & 1 & 1 & 1 & 2 & 2 & 2 & 3 & 3\\1 & 1 & 1 & 2 & 2 & 2 & 2 & 3 & 3\\1 & 3 & 3 & 1 & 4 & 4 & 4 & 3 & 4\\5 & 3 & 3 & 2 & 2 & 4 & 4 & 5 & 4\\5 & 5 & 5 & 6 & 4 & 4 & 6 & 5 & 6\\5 & 5 & 5 & 6 & 7 & 7 & 6 & 6 & 6\\7 & 8 & 8 & 8 & 7 & 7 & 9 & 9 & 9\\7 & 8 & 8 & 8 & 7 & 9 & 6 & 6 & 9\\ 7 & 8 & 8 & 8 & 7 & 9 & 9 & 9 & 9\\\end{matrix}$$

• Well, this surely answers the question as stated. But the point of the puzzle (as I intended, although did not spell out explicitly) is rather to figure out a (humanly interpretable) way to obtain the solution. (Should I have used a "no-computers" tag to make that clear?) As such, I will wait on accepting this answer for now - maybe there will be another one that gives a solution path. Thanks for the effort though! Commented Aug 14 at 21:00
• Ah, I see where I went wrong now! What a satisfying realisation when I realised my mistake... Commented Aug 14 at 22:11

Version 2:

I hope this one should be the correct solution, but I don't have any definitive proof...

Version 1: (invalid)

Took a lot of trial and error, but this is the best I could do:

I believe it's optimal, but I'm fully willing for somebody to come along and prove me wrong.

• This is not a valid solution unfortunately (there are lonely 7's in boxes 5,6 and 9). But the colouring is a nice touch :) Commented Aug 14 at 13:10
• Oh right, I forgot about the box rule. Give me a while and I might come up with an actually valid solution! Commented Aug 14 at 13:14
• You can fix the 7's without breaking anything else by swapping columns 6 and 7
– fljx
Commented Aug 14 at 13:24
• @TimSeifert edited with a new solution that i hope is the correct one Commented Aug 14 at 14:26
• I see. This is still not the minimum though! Although the mistake you (presumably) made is fairly understandable Commented Aug 14 at 14:47

The best I could do is

or, in "81-digit" version:

111122233111222233133144434533224454555644656555677688799978688 799978866997779888

I can't claim for sure it's minimal. This is pure trial and error, I tried making the smallest number possible, avoiding every dead-end.

• This is not the minimum, but also not that far off. (I'm sorry to hear that you had to resort to T&E though - I felt that the "expected" solve path was fairly structured). Good effort! :) Commented Aug 14 at 12:23
• Don't be sorry - I had fun trying! I must be missing a strategy better than "let's put the smallest possible number and see how that goes"; I'll give it another try later if no one figured it out until then :) Commented Aug 14 at 12:33
• @TimSeifert, isn't the minimum not just 81 1's? Commented Aug 14 at 12:49
• @Lezzup No, since each digit still has to occur nine times in the grid. Commented Aug 14 at 12:59
• @TimSeifert, ah, I knew there was something I was missing :) Commented Aug 14 at 17:28