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$
