Verifying the correctness of a Sudoku solution

Question

A Sudoku is solved correctly, if all columns, all rows and all 9 subsquares are filled with the numbers 1 to 9 without repetition. Hence, in order to verify if a (correct) solution is correct, one has to check by definition 27 arrays of length 9.

Q1: Are there verification strategies that reduce this number of checks ?

Q2: What is the minimal number of checks that verify the correctness of a (correct) solution ?

       

   ^{(Image sources from Wayback Machine: first second)}

The following simple observation yields an improved verification algorithm: At first enumerate rows, columns and subsquares as indicated in pic 2. Suppose the columns $c_1,c_2,c_3$ and the subsquares $s_1, s_4$ are correct (i.e. contain exactly the numbers 1 to 9). Then it's easy to see that $s_7$ is correct as well. This shows:

(A1) If all columns, all rows and 4 subsquares are correct, then the solution is correct.

Now suppose all columns and all rows up to $r_9$ and the subsquares $s_1,s_2,s_4,s_5$ are correct. By the consideration above, $s_7,s_8,s_9$ and $s_3,s_6$ are correct. Moreover, $r_9$ has to be correct, too. For, suppose a number, say 1, occurs twice in $r_9$. Since the subsquares are correct, the two 1's have be in different subsquares, say $s_7,s_8$. Hence the 1's from rows $r_7, r_8$ both have to lie in $s_9$, i.e. $s_9$ isn't correct. This is the desired contradiction.

Hence (A1) can be further improved to

(A2) If all columns and all rows up to one and 4 subsquares are correct, then the solution is correct.

This gives as upper bound for Q2 the need of checking 21 arrays of length 9.

Q3: Can the handy algorithm (A2) be further improved ?

Answer 1

$\DeclareMathOperator\span{span}$Here is an argument which works for general $n\times n$ Sudokus, $n\ge 2$, using some ideas from the other answers (namely, casting the problem in terms of linear algebra as in François Brunault’s answer, and the notion of alternating paths below is related to the even sets as in Tony Huynh’s answer, attributed to Zack Wolske).

I will denote the cells as $s_{ijkl}$ with $0\le i,j,k,l< n$, where $i$ identifies the band, $j$ the stack, $k$ the row within band $i$, and $l$ the column within stack $j$. Rows, columns, and blocks are denoted $r_{ik},c_{jl},b_{ij}$ accordingly. Let $X=\{r_{ik},c_{jl},b_{ij}:i,j,k,l< n\}$ be the set of all $3n^2$ checks. For $S\subseteq X$ and $x\in X$, I will again denote by $S\models x$ the consequence relation “every Sudoku grid satisfying all checks from $S$ also satisfies $x$”.

Let $V$ be the $\mathbb Q$-linear space with basis $X$, and $V_0$ be the span of the vectors $\sum_kr_{ik}-\sum_jb_{ij}$ for $i< n$, and $\sum_lc_{jl}-\sum_ib_{ij}$ for $j< n$.

Lemma 1: If $x\in\span(S\cup V_0)$, then $S\models x$.

Proof: A grid $G$ induces a linear mapping $\phi_G$ from $V$ into an $n^2$-dimensional such that for any $x'\in X$, the $i$th coordinate of $\phi_G(x')$ gives the number of occurrences of the number $i$ in $x'$. We have $\phi_G(V_0)=0$, and $G$ satisfies $x'$ iff $\phi_G(x')$ is the constant vector $\vec 1$. If $x=\sum_i\alpha_ix_i+y$, where $x_i\in S$ and $y\in V_0$, then $\phi_G(x)=\vec\alpha$ for $\alpha:=\sum_i\alpha_i$. The same holds for every grid $G'$ satisfying $S$; in particular, it holds for any valid grid, which has $\phi_{G'}(x)=\vec1$, hence $\alpha=1$. QED

We intend to prove that the converse holds as well, so assume that $x\notin\span(S\cup V_0)$. We may assume WLOG $x=r_{00}$ or $x=b_{00}$, and we may also assume that $r_{i0}\notin S$ whenever $r_{ik}\notin S$ for some $k$, and $c_{j0}\notin S$ whenever $c_{jl}\notin S$ for some $l$. By assumption, there exists a linear function $\psi\colon V\to\mathbb Q$ such that $\psi(S\cup V_0)=0$, and $\psi(x)\ne0$. The space of all linear functions on $V$ vanishing on $V_0$ has dimension $3n^2-2n$, and one checks easily that the following functions form its basis:

• $\omega_{ik}$ for $0\le i< n$, $0< k< n$: $\omega_{ik}(r_{ik})=1$, $\omega_{ik}(r_{i0})=-1$.

• $\eta_{jl}$ for $0\le j< n$, $0< l< n$: $\eta_{jl}(c_{jl})=1$, $\eta_{jl}(c_{j0})=-1$.

• $\xi_{ij}$ for $i,j< n$: $\xi_{ij}(r_{i0})=\xi_{ij}(c_{j0})=\xi_{ij}(b_{ij})=1$.

(The functions are zero on basis elements not shown above.) We can thus write $$\psi=\sum_{ik}u_{ik}\omega_{ik}+\sum_{jl}v_{jl}\eta_{jl}+\sum_{ij}z_{ij}\xi_{ij}.$$ If $r_{ik}\in S$, $k\ne0$, then $0=\psi(r_{ik})=u_{ik}$, and similarly $c_{jl}\in S$ for $l\ne0$ implies $v_{jl}=0$. Thus, the functions $\omega_{ik}$ and $\eta_{jl}$ that appear in $\psi$ with a nonzero coefficient individually vanish on $S$. The only case when they can be nonzero on $x$ is $\omega_{0k}$ if $x=r_{00}$ and $r_{00},r_{0k}\notin S$, but then taking any valid grid and swapping cells $s_{0000}$ and $s_{00k0}$ shows that $S\nvDash x$ and we are done. Thus we may assume that the first two sums in $\psi$ vanish on $S\cup\{x\}$, and therefore the third one vanishes on $S$ but not on $x$, i.e., WLOG $$\psi=\sum_{ij}z_{ij}\xi_{ij}.$$ That $\psi$ vanishes on $S$ is then equivalent to the following conditions on the matrix $Z=(z_{ij})_{i,j< n}$:

1. $z_{ij}=0$ if $b_{ij}\in S$,

2. $\sum_jz_{ij}=0$ if $r_{i0}\in S$,

3. $\sum_iz_{ij}=0$ if $c_{j0}\in S$.

Let us say that an alternating path is a sequence $e=e_p,e_{p+1},\dots,e_q$ of pairs $e_m=(i_m,j_m)$, $0\le i_m,j_m< n$, such that

• $i_m=i_{m+1}$ if $m$ is even, and $j_m=j_{m+1}$ if $m$ is odd,

• the indices $i_p,i_{p+2},\dots$ are pairwise distinct, except that we may have $e_p=e_q$ if $q-p\ge4$ is even,

• likewise for the $j$s.

If $m$ is even, the incoming line of $e_m$ is the column $c_{j_m0}$, and its outgoing line is the row $r_{i_m0}$. If $m$ is odd, we define it in the opposite way. An alternating path for $S$ is an alternating path $e$ such that $b_{i_mj_m}\notin S$ for every $m$, and either $e_p=e_q$ and $q-p\ge4$ is even ($e$ is an alternating cycle), or the incoming line of $e_p$ and the outgoing line of $e_q$ do not belong to $S$.

Every alternating path $e$ induces a matrix $Z_e$ which has $(-1)^m$ at position $e_m$ for $m=p,\dots,q$, and $0$ elsewhere. It is easy to see that if $e$ is an alternating path for $S$, then $Z_e$ satisfies conditions 1, 2, 3.

Lemma 2: The space of matrices $Z$ satisfying 1, 2, 3 is spanned by matrices induced by alternating paths for $S$.

Proof: We may assume that $Z$ has integer entries, and we will proceed by induction on $\|Z\|:=\sum_{ij}|z_{ij}|$. If $Z\ne 0$, pick $e_0=(i_0,j_0)$ such that $z_{i_0j_0}>0$. If the outgoing line of $e_0$ is outside $S$, we put $q=0$, otherwise condition 2 guarantees that $z_{i_0,j_1}< 0$ for some $j_1$, and we put $i_1=i_0$, $e_1=(i_1,j_1)$. If the outgoing line of $e_1$ is outside $S$, we put $q=1$, otherwise we find $i_2$ such that $z_{i_2j_1}>0$ by condition 3, and put $j_2=j_1$. Continuing in this fashion, one of the following things will happen sooner or later:

• The outgoing line of the last point $e_m$ constructed contains another point $e_{m'}$ (and therefore two such points, unless $m'=0$). In this case, we let $p$ be the maximal such $m'$, we put $q=m+1$, $e_q=e_p$ to make a cycle, and we drop the part of the path up to $e_{p-1}$.

• The outgoing line of $e_m$ is outside $S$. We put $q=m$.

In the second case, we repeat the same construction going backwards from $e_0$. Again, either we find a cycle, or the construction stops with an $e_p$ whose incoming line is outside $S$. Either way, we obtain an alternating path for $S$ (condition 1 guarantees that $b_{i_mj_m}\notin S$ for every $m$). Moreover, the nonzero entries of $Z_e$ have the same sign as the corresponding entries of $Z$, thus $\|Z-Z_e\|<\|Z\|$. By the induction hypothesis, $Z-Z_e$, and therefore $Z$, is a linear combination of some $Z_e$s. QED

Now, Lemma 2 implies that we may assume that our $\psi$ comes from a matrix $Z=Z_e$ induced by an alternating path $e=e_p,\dots,e_q$. Assume that $G$ is a valid Sudoku grid that has $1$ in cells $s_{i_mj_m00}$ for $m$ even, and $2$ for $m$ odd. Let $G'$ be the grid obtained from $G$ by exchanging $1$ and $2$ in these positions. Then $G'$ violates the following checks:

• $b_{i_mj_m}$ for each $m$.

• If $e$ is not a cycle, the incoming line of $e_p$, and the outgoing line of $e_q$.

Since $e$ is an alternating path for $S$, none of these is in $S$. On the other hand, $\psi(x)\ne0$ implies that $x$ is among the violated checks, hence $S\nvDash x$.

It remains to show that such a valid grid $G$ exists. We can now forget about $S$, and then it is easy to see that every alternating path can be completed to a cycle, hence we may assume $e$ is a cycle. By applying Sudoku permutations and relabelling the sequence, we may assume $p=0$, $i_m=\lfloor m/2\rfloor$, $j_m=\lceil m/2\rceil$ except that $i_q=j_q=j_{q-1}=0$. We are thus looking for a solution of the following grid: $$\begin{array}{|ccc|ccc|ccc|ccc|ccc|} \hline 1&&&2&&&&&&&&&&&&\\ \strut&&&&&&&&&&&&&&&\\ \strut&&&&&&&&&&&&&&&\\ \hline &&&1&&&2&&&&&&&&&\\ &&&&&&&&&&&&&&\cdots&\\ &&&&&&&&\ddots&&&&&&&\\ \hline 2&&&&&&&&&1&&&&&&\\ \strut&&&&&&&&&&&&&&&\\ \strut&&&&&&&&&&&&&&&\\ \hline \strut&&&&&&&&&&&&&&&\\ \strut&&&&\vdots&&&&&&&&&&&\\ \strut&&&&&&&&&&&&&&&\\ \hline \end{array}$$ where the upper part is a $q'\times q'$ subgrid, $q'=q/2$.

If $q'=n$, we can define the solution easily by putting $s_{ijkl}=(k+l,j-i+l)$, where we relabel the numbers $1,\dots,n^2$ by elements of $(\mathbb Z/n\mathbb Z)\times(\mathbb Z/n\mathbb Z)$, identifying $1$ with $(0,0)$ and $2$ with $(0,1)$. In the general case, we define $s_{ijkl}=(k+l+a_{ij}-b_{ij},l+a_{ij})$. It is easy to check that this is a valid Sudoku if the columns of the matrix $A=(a_{ij})$ and the rows of $B=(b_{ij})$ are permutations of $\mathbb Z/n\mathbb Z$. We obtain the wanted pattern if we let $a_{ij}=b_{ij}=j-i\bmod{q'}$ for $i,j< q'$, and extend this in an arbitrary way so that the columns of $A$ and the rows of $B$ are permutations.

This completes the proof that $x\notin\span(S\cup V_0)$ implies $S\nvDash x$. This shows that $\models$ is a linear matroid, and we get a description of maximal incomplete sets of checks by means of alternating paths.

We can also describe the minimal dependent sets. Put $$D_{R,C}=\{r_{ik}:i\in R,k< n\}\cup\{c_{jl}:j\in C,l< n\}\cup\{b_{ij}:(i\in R\land j\notin C)\lor(i\notin R\land j\in C)\}$$ for $R,C\subseteq\{0,\dots,n-1\}$. If $R$ or $C$ is nonempty, so is $D_{R,C}$, and $$\sum_{i\in R}\Bigl(\sum_kr_{ik}-\sum_jb_{ij}\Bigr)-\sum_{j\in C}\Bigl(\sum_lc_{jl}-\sum_ib_{ij}\Bigr)\in V_0$$ shows that $D_{R,C}$ is dependent. On the other hand, if $D$ is a dependent set, there is a linear combination $$\sum_i\alpha_i\Bigl(\sum_kr_{ik}-\sum_jb_{ij}\Bigr)-\sum_j\beta_j\Bigl(\sum_lc_{jl}-\sum_ib_{ij}\Bigr)\ne0$$ where all basic vectors with nonzero coefficients come from $D$. If (WLOG) $\alpha:=\alpha_{i_0}\ne0$, put $R=\{i:\alpha_i=\alpha\}$ and $C=\{j:\beta_j=\alpha\}$. Then $R\ne\varnothing$, and $D_{R,C}\subseteq D$.

On the one hand, this implies that every minimal dependent set is of the form $D_{R,C}$. On the other hand, $D_{R,C}$ is minimal unless it properly contains some $D_{R',C'}$, and this can happen only if $R'\subsetneq R$ and $C=C'=\varnothing$ or vice versa. Thus $D_{R,C}$ is minimal iff $|R|+|C|=1$ or both $R,C$ are nonempty.

This also provides an axiomatization of $\models$ by rules of the form $D\smallsetminus\{x\}\models x$, where $x\in D=D_{R,C}$ is minimal. It is easy to see that if $R=\{i\}$ and $C\ne\varnothing$, the rules for $D_{R,C}$ can be derived from the rules for $D_{R,\varnothing}$ and $D_{\varnothing,\{j\}}$ for $j\in C$, hence we can omit these. (Note that the remaining sets $D_{R,C}$ are closed, hence the corresponding rules have to be included in every axiomatization of $\models$.)

To sum it up:

Theorem: Let $n\ge2$.

• $S\models x$ if and only if $x\in\span(S\cup V_0)$. In particular, $\models$ is a linear matroid.

• All minimal complete sets of checks have cardinality $3n^2-2n$. (One such set consists of all checks except for one row from each band, and one column from each stack.)

• The closed sets of $\models$ are intersections of maximal closed sets, which are complements of Sudoku permutations of the sets

  • $\{b_{00},b_{01},b_{11},b_{12},\dots,b_{mm},b_{m0}\}$ for $0< m< n$

  • $\{c_{00},b_{00},b_{01},b_{11},b_{12},\dots,b_{mm},r_{m0}\}$ for $0\le m< n$

  • $\{c_{00},b_{00},b_{01},b_{11},b_{12},\dots,b_{m-1,m},c_{m1}\}$ for $0\le m< n$

• The minimal dependent sets of $\models$ are the sets $D_{R,C}$, where $R,C\subseteq\{0,\dots,n-1\}$ are nonempty, or $|R|+|C|=1$.

• $\models$ is the smallest consequence relation such that $D_{R,C}\smallsetminus\{x\}\models x$ whenever $x\in D_{R,C}$ and either $|R|,|C|\ge2$, or $|R|+|C|=1$.

Answer 2

The consequence relation $\models$ defined in Emil Jeřábek's answer is a matroid. In fact, it is a linear matroid.

Let $X=\{r_1,\ldots,r_9,c_1,\ldots,c_9,b_1,\ldots,b_9\}$ be the set of possible checks. Recall that given $S \subset X$ and $x \in X$, the notation $S \models x$ means that every Sudoku grid which is valid on $S$ is also valid on $x$.

We may embed $X$ into the free abelian group $V$ generated by the 81 cells of the Sudoku grid, by mapping a check $x \in X$ to the formal sum of the cells contained in $x$. The span of $X$ has rank $21$, and the kernel of the natural map $\mathbf{Z}X \to V$ is generated by the six relations of the form $r_1+r_2+r_3-b_1-b_2-b_3$.

Proposition. We have $S \models x$ if and only if $x \in \operatorname{Vect}(S)$.

Proof. By Proposition 2 from Emil's answer, the consequence relations $\models$ and $\vdash$ coincide, so we may work with $\vdash$. Let us prove that $S \vdash x$ implies $x \in \operatorname{Vect}(S)$. By transitivity, we may assume $S=D \backslash \{x\}$ for some $D \in \mathcal{D}$. It is straightforward to check that $x \in \operatorname{Vect}(D \backslash \{x\})$ in each case (i)-(iv).

Conversely, let us assume $x=\sum_{s \in S} \lambda_s s$ for some $\lambda_s \in \mathbf{Z}$. Since the elements of $X$ have degree 9, we have $\sum_{s \in S} \lambda_s = 1$. Any Sudoku grid provides a linear map $\phi : V \to E$, where $E$ is the free abelian group with basis $\{1,\ldots,9\}$ (map each cell to the digit it contains). If the grid is valid on $S$ then $\phi(s)=[1]+\cdots+[9]$ for every $s \in S$, and thus $\phi(x)=[1]+\cdots+[9]$, which means that the grid is valid on $x$. QED

Note that a set of checks $S$ is complete if and only if $\operatorname{Vect}(S)=\operatorname{Vect}(X)$. In particular, the minimal complete sets are those which form a basis of $\operatorname{Vect}(X)$, and it is now clear that every such set has cardinality $21$.

We also obtain a description of the independent sets : these are exactly the sets which are linearly independent when considered in $V$. Any independent set may be extended to a minimal complete set (we may have worked with $\mathbf{Q}$-coefficients instead of $\mathbf{Z}$-coefficients above).

Answer 3

One can use information theoretic considerations to obtain lower bounds for the number of checks. I'll prove that at least 15 checks are necessary.

Proof. First note that for any two rows $r_i$ and $r_j$ (contained in the same band), it is easy to construct a Sudoku which is correct everywhere except $r_i$ and $r_j$. Thus, one must check at least 2 rows from each band, and hence at least 6 rows. By symmetry, one must also check at least 6 columns.

Next, we define a $4$-set of $3 \times 3$ squares to be a corner set if they are the corners of a rectangle. For any corner set $S$, it is easy to construct a Sudoku which is correct on all rows, columns, and squares except for $S$. Note that any set of squares which meets all corner sets must have size at least 3 Thus, we must check at least 3 squares.

$6+6+3=15.$

Edit. Here is an improvement that shows that 16 checks are in fact necessary. This idea is due to Zack Wolske (see the comments below). Call a subset of $3 \times 3$ squares an even set if it contains an even number of squares from each row and column of squares. Note that a corner set is an even set.

Lemma. If $S$ is a set of at most three squares, then the complement of $S$ contains a non-empty even set.

The only non-trivial verification is if $S$ is a transversal, in which case the complement of $S$ is itself an even set of size 6. This lemma shows that at least 4 squares must be checked. To see this suppose that we have only checked at most three squares. By the Lemma, we may select a non-empty even set $E$ contained in the squares we have not checked. We next label the center cell of each square in $E$ with a $1$ or a $2$ such that each row and column is either completely unlabelled or contains exactly one $1$ and one $2$. Clearly, we can extend this partial labelling to a fully correct Sudoku. If we then flip $1$ and $2$ in the center cells of $E$, we obtain a Sudoku that is incorrect on each square in $E$, but correct on all other squares, rows and columns. Thus, we must check 4 squares as claimed.

$6+6+4=16$.

Edit 2. I now can prove that at least 18 checks are necessary. Recall that we have so far established that at least 6 rows (at least 2 from each band), and 6 columns (at least 2 from each stack), and 4 squares are necessary. Therefore, suppose in a minimum set of checks $V$ we have checked $6+r'$ rows, $6+c'$ columns and $4+s'$ squares.

Note that for each unchecked square $x$, it cannot be the case that at most two columns of $x$ and at most two rows of $x$ are checked. If so, there would be a cell of $x$ such that the row containing $x$, the column containing $x$ and the square containing $x$ are all unchecked, which is a contradiction.

If $s' \geq 2$, then we are done. So, we have checked at most 5 squares. In particular, the set of unchecked squares are not all in the same column or same row. Thus, there are two unchecked squares that are in different rows and in different columns. As mentioned, both of these unchecked squares must have all rows checked or all columns checked. Therefore, $r'+c' \geq 2$, and we are done.

Edit 3. I can now prove that at least 19 checks are necessary. Using the notation from the previous edit, if $s' \geq 3$, we are done. We define a band $B$ to be tight (for $V$), if $V$ uses all three rows of $B$. If $s'=2$, then at least one band or one stack must be tight, so we are done. If $s'=1$, then by the previous edit we have $r'+c' \geq 2$, and we are done.
The only remaining possibility is if $s'=0$. Thus, there are 5 unchecked squares. Observe that any set of 5 squares must either contain a transversal, a band, or a stack. If the unchecked squares contain a transversal, then $r'+c' \geq 3$ (since the sum of the tight bands and tight stacks must be at least 3). By symmetry, we may assume that there is an unchecked band.

Lemma. If there is an unchecked band $B$, then at least two stacks are tight.

Proof. If not, by symmetry we may assume that $s_1, s_2, s_3$ are unchecked and that $c_1$ and $c_4$ are unchecked. By taking a correct Sudoku and swapping the first entry and fourth entries of the first row, we obtain a Sudoku that is correct everywhere, except $s_1, s_2, c_1$, and $c_4$, which is a contradiction.

By the lemma, there are at least two tight stacks. If there are three, then $c' \geq 3$, so we are done. If there are exactly two tight stacks, then the band $B$ itself must be tight, otherwise there is a cell whose row, column and square are all unchecked. Hence $c'+r' \geq 3$, and we are again done.

Remark. There is quite a bit of slack in these arguments, so with enough case analysis, I think one can get to 21 with $\epsilon$ new ideas.

Answer 4

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 short-hand 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:

1. $S$ is complete.

2. 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$.

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

   

4. $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}{|ccc|ccc|ccc|} \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.