
I couldn’t find all my original notes, but I have reconstructed the gist of it.
First, validity of Sudoku grids is preserved by transposition, permutations of bands, permutations of rows within bands, permutations of stacks, and permutations of columns within stacks. Below I will use “Sudoku permutation” as a shorthand for permutations from the group generated by these transformations. Also, I will write “blocks” instead of what is called “squares” in the question, since the latter is commonly used to denote single cells.
Let us say that a set of checks $S\subseteq\{r_1,\dots,r_9,c_1,\dots,c_9,b_1,\dots,b_9\}$ is complete if every Sudoku grid satisfying the checks from $S$ satisfies all checks (i.e., it is a valid grid). One can characterize complete sets of checks by describing either minimal complete sets, or maximal incomplete sets. I will mostly refer to complements of these sets, as they have less elements.
As was already observed in the question, there are complete sets of 21 checks. (I prefer the following symmetric solution: check all blocks, two rows in each band, and two columns in each stack.) It follows from the description below that this number is optimal, as all minimal complete sets of checks have 21 elements.
Proposition 1. The following are equivalent:
$S$ is complete.
All checks can be derived from $S$ by means of the following rule: if $S$ includes all but one of the 6 checks contained in a given band or stack, add the remaining one to $S$.
$S$ is not included in the complement of a Sudoku permutation of one of the following sets:
a) $\{r_1,r_2\}$
b) $\{r_1,c_1,b_1\}$
c) $\{b_1,b_2,b_4,b_5\}$
d) $\{r_1,r_4,b_1,b_4\}$
e) $\{r_1,c_1,b_2,b_4,b_5\}$
f) $\{b_2,b_3,b_4,b_6,b_7,b_8\}$
g) $\{r_1,r_4,b_1,b_5,b_7,b_8\}$
h) $\{r_1,c_1,b_3,b_5,b_6,b_7,b_8\}$
$S$ includes the complement of a Sudoku permutation of one of the following sets (there may well be some errors in the list, but the only relevant information is that they all have 6 elements): $\{r_1,r_4,r_7,c_1,c_4,c_7\}$, $\{r_1,r_4,c_1,c_4,c_7,b_7\}$, $\{r_1,r_4,c_1,c_4,b_6,b_9\}$, $\{r_1,r_4,c_1,c_4,b_6,b_8\}$, $\{r_1,c_1,c_4,c_7,b_6,b_9\}$, $\{r_1,c_1,c_4,c_7,b_6,b_8\}$, $\{r_1,c_1,c_4,b_3,b_6,b_9\}$, $\{r_1,c_1,c_4,b_3,b_6,b_8\}$, $\{r_1,c_1,c_4,b_3,b_5,b_8\}$, $\{r_1,c_1,c_4,b_3,b_5,b_7\}$, $\{r_1,c_1,c_4,b_5,b_6,b_9\}$, $\{r_1,c_1,c_4,b_5,b_6,b_8\}$, $\{r_1,c_1,b_2,b_3,b_4,b_7\}$, $\{r_1,c_1,b_2,b_3,b_6,b_7\}$, $\{r_1,c_1,b_2,b_3,b_6,b_8\}$, $\{r_1,c_1,b_2,b_3,b_6,b_9\}$, $\{r_1,c_1,b_3,b_6,b_7,b_8\}$, $\{r_1,c_1,b_3,b_6,b_8,b_9\}$, $\{r_1,c_1,b_3,b_5,b_7,b_8\}$, $\{r_1,c_1,b_3,b_5,b_8,b_9\}$, $\{c_1,c_4,c_7,b_1,b_4,b_7\}$, $\{c_1,c_4,c_7,b_1,b_4,b_8\}$, $\{c_1,c_4,c_7,b_1,b_5,b_9\}$, $\{c_1,c_4,b_2,b_3,b_5,b_8\}$, $\{c_1,c_4,b_2,b_3,b_5,b_9\}$, $\{c_1,c_4,b_2,b_3,b_6,b_9\}$, $\{c_1,c_4,b_2,b_3,b_6,b_7\}$, $\{c_1,c_4,b_2,b_5,b_6,b_7\}$, $\{c_1,b_1,b_2,b_3,b_4,b_7\}$, $\{c_1,b_1,b_2,b_3,b_4,b_8\}$, $\{c_1,b_1,b_2,b_3,b_5,b_9\}$, $\{c_1,b_1,b_2,b_3,b_6,b_9\}$, $\{c_1,b_1,b_2,b_4,b_6,b_7\}$, $\{c_1,b_2,b_3,b_4,b_6,b_9\}$, $\{c_1,b_2,b_3,b_6,b_7,b_8\}$, $\{c_1,b_3,b_4,b_6,b_7,b_8\}$, $\{c_1,b_2,b_3,b_4,b_7,b_8\}$.
Proof (part):
$2\to1$ follows from the soundness of the rule: if, say, a grid satisfies 3 block checks and two row checks incident with the same band, each number occurs three times in the band, and twice in the checked rows, hence it occurs once in the remaining row.
$4\to2$: draw 37 pictures, and chase applications of the rule.
$1\to3$: For each of the cases a–h, we need to find an invalid grid which satisfies checks outside the given set.
a) Take any valid grid, and swap the elements in cells 1:1 and 2:1 (that’s row and column number).
b) Take a valid grid, and modify cell 1:1.
c) There exists a valid grid with 1 in cells 1:1, 4:4, and 2 in cells 1:4, 4:1. Exchange 1 and 2 in these four cells.
d) Take a valid grid, and swap the elements in cells 1:1 and 4:1.
e) Do the same as in c), but leave 1 in cell 1:1.
f) There exists a valid grid with 1 in cells 1:4, 4:7, 7:1, and 2 in cells 1:7, 4:1, and 7:4. Exchange 1 and 2 in these six cells.
$$\begin{array}{ccccccccc}
\hline
3&4&5&\color{green}1&6&7&\color{green}2&8&9\\
6&7&8&3&2&9&4&1&5\\
9&1&2&4&5&8&3&6&7\\
\hline
\color{green}2&3&4&5&7&6&\color{green}1&9&8\\
5&6&9&8&1&2&7&3&4\\
7&8&1&9&3&4&5&2&6\\
\hline
\color{green}1&9&6&\color{green}2&4&5&8&7&3\\
4&2&7&6&8&3&9&5&1\\
8&5&3&7&9&1&6&4&2\\
\hline
\end{array}$$
g) Do the same as in f), but leave cells 1:7 and 4:7 unchanged. This is g) up to permutation.
h) Do the same as in f), but leave one of the six cells unchanged. (Again, up to permutation.)
$3\to4$: This is a tedious but straightforward case analysis, much easier done with pictures than with words, so I’m omitting it.
Let us consider a more general problem: a set of checks $S$ implies a check $x$, written $S\models x$, if every Sudoku grid satisfying all checks from $S$ also satisfies $x$. Thus defined $\models$ is a consequence relation (or closure operator). Note that $S$ is complete iff $S\models x$ for every $x$ (i.e., iff $S$ is inconsistent in the usual consequence relation terminology).
Let $\mathcal D$ be the set of all Sudoku permutations of the following sets:
(i) $\{r_1,r_2,r_3,b_1,b_2,b_3\}$,
(ii) $\{r_1,\dots,r_9,c_1,\dots,c_9\}$,
(iii) $\{r_1,\dots,r_9,c_1,\dots,c_6,b_3,b_6,b_9\}$,
(iv) $\{r_4,\dots,r_9,c_4,\dots,c_9,b_2,b_3,b_4,b_7\}$.
(I don’t know how to draw decent pictures this time, as everything overlaps everything else.) Define $S\vdash x$ to be the consequence relation axiomatized by rules of the form $D\smallsetminus\{x\}\vdash x$, where $x\in D\in\mathcal D$.
Let $\mathcal M$ be the set of all complements of Sudoku permutations of the sets a, ..., h above. The third consequence relation is defined as follows: $S\Vdash x$ iff $S\subseteq M$ implies $x\in M$ for every $M\in\mathcal M$. (In other words, closed sets of $\Vdash$ are exactly the intersections of subfamilies of $\mathcal M$.)
Proposition 2: ${\models}={\vdash}={\Vdash}$.
Proof:
$S\vdash x\implies S\models x$:
This amounts to showing that $D\smallsetminus\{x\}\models x$ for $x\in D\in\mathcal D$. For example, let $D$ be the set in (iv), and $x=b_3$. Fix a Sudoku grid satisfying $\{r_4,\dots,r_9,c_4,\dots,c_9,b_2,b_4,b_7\}$, and let $n=1,\dots,9$. The number $n$ occurs 3 times in the bottom band by $r_7,r_8,r_9$, one of which occurrences is in $b_7$, hence it occurs twice in $b_8\cup b_9$. The same argument shows that it occurs twice in $b_5\cup b_6$ and in $b_5\cup b_8$, hence it occurs twice in $b_6\cup b_9$. Since there are three occurrences in the rightmost stack by $c_7,c_8,c_9$, $n$ occurs once in $b_3$. As $n$ was arbitrary, this means that $b_3$ is correct.
$S\models x\implies S\Vdash x$:
This means that for every set $M\in\mathcal M$ and $x\notin M$, there exists a grid satisfying $M$ and not $x$. We have verified this in the proof of Proposition 1.
$S\Vdash x\implies S\vdash x$:
We need to show that if $S$ is a maximal set such that $S\nvdash x$, there is $M\in\mathcal M$ such that $S\subseteq M$ and $x\notin M$. This is again done by a case analysis. By symmetry, it suffices to consider the cases $x=r_1$ and $x=b_1$. I will briefly write down the proof so that it does not appear that I’m making unjustified claims all the time.
Case $x=r_1$: We have $r_1\notin S$. If $r_2\notin S$ or $r_3\notin S$, we are done by a), hence assume $r_2,r_3\in S$. As $S$ is closed under the (i) rule, some block from the first band is missing from $S$. By symmetry, we may assume $b_1\notin S$. If some column incident with $b_1$ is missing, we are done by b), hence assume $c_1,c_2,c_3\in S$. By (i) for the first stack, WLOG $b_4\notin S$. If some row from the middle band is missing, we are done by d), hence assume $r_4,r_5,r_6\in S$. By (i) for the middle band, WLOG $b_5\notin S$. If some column in the middle stack is missing, e) applies, hence assume $c_4,c_5,c_6\in S$.
Case 1: $r_7,r_8,r_9\in S$. Then some column, WLOG $c_7$, is missing from $S$ by (ii). If $b_3\notin S$ or $b_6\notin S$, we are done by b) or e), respectively. Thus $b_3,b_6\in S$, hence $b_9\notin S$ by (iii). By (iv), $b_7\notin S$ or $b_8\notin S$, hence e) or h) applies.
Case 2: some row, WLOG $r_7$, is missing. Then $b_7,b_8\in S$ unless d) or g) applies. By (iv), $b_3\notin S$ or $b_6\notin S$, hence we are done by d) or g), respectively, unless $b_9\in S$. Then WLOG $c_7\notin S$ by (iii), hence we are done by b) or e).
Case $x=b_1$: If some row and column incident with $b_1$ are missing from $S$, we are done by b), hence WLOG $r_1,r_2,r_3\in S$. By (i), WLOG $b_2\notin S$. If columns are missing in both the first two stacks, we are done by d), hence WLOG $c_1,c_2,c_3\in S$. Then WLOG $b_4\notin S$ by (i). If $b_5\notin S$, we are done by c), hence assume $b_5\in S$. If $b_6,b_8\notin S$, then $b_3,b_7,b_9\in S$ unless c) or f) applies, thus some row and column incident with $b_9$ are missing by (i), hence we are done by h). If $b_6,b_8\in S$, some row and column incident with $b_5$ are missing by (i), hence we are done by e). Thus, we can assume $b_6\in S$ and $b_8\notin S$. By (i), WLOG $r_4\notin S$. Then $r_7,r_8,r_9\in S$ unless g) applies, and $c_4,c_5,c_6\in S$ unless e) applies. If $b_7\notin S$, c) applies, otherwise $b_9\notin S$ by (i). By (iii), WLOG $c_7\notin S$, hence we are done by h).
QED
I know next to nothing about matroid theory so I let others to figure it out, but the symmetric form of the rules defining $\vdash$ makes me suspect that the closure operator is in fact a matroid.


answered May 2 '13 at 13:58

