42
$\begingroup$

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 ?

$\endgroup$
11
  • 33
    $\begingroup$ You can recognize a mathematician in that he always checks his Sudoku is correct because he knows that at this point he has only proved unicity :) $\endgroup$ Apr 29, 2013 at 20:45
  • 2
    $\begingroup$ If we consider the $c_i$, $r_j$ and $s_k$ as elements in the free abelian group with basis $\{1,\ldots,9\}$, then relations of the form $r_1+r_2+r_3=s_1+s_2+s_3$ show that e.g. correctness of $r_1,r_2,r_3,s_1,s_2$ implies correctness of $s_3$. $\endgroup$ Apr 29, 2013 at 20:55
  • $\begingroup$ (A2) doesn't work if three of the four subsquares are aligned. $\endgroup$ Apr 29, 2013 at 21:03
  • $\begingroup$ @François: Exactly! I think your conclusion in the 2nd comment is just the row-version of what I described for columns in the paragraph after the pics. $\endgroup$
    – Ralph
    Apr 29, 2013 at 21:30
  • $\begingroup$ @Denis: Thanks. I'll correct it later. $\endgroup$
    – Ralph
    Apr 29, 2013 at 21:35

4 Answers 4

19
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ I’m sorry for the number of edits. I’m going to stop here. $\endgroup$ May 7, 2013 at 14:59
  • $\begingroup$ This is great work. Thanks a lot. The direction proved in Lemma 1 by using François' linear map is particularly elegant. I tried hard to find a similar approach for the other direction, but didn't succeed yet. $\endgroup$
    – Ralph
    May 17, 2013 at 10:05
19
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Does the matroid property easily generalize to $n \times n$-Sudoku? $\endgroup$ May 4, 2013 at 5:01
  • $\begingroup$ Just for reference, I asked this as a separate question mathoverflow.net/questions/129600/is-there-a-sudoku-matroid $\endgroup$
    – Tony Huynh
    May 4, 2013 at 6:37
  • $\begingroup$ @Sam : Good question, I don't know the answer. In fact, I should say that all the difficult work here is contained in Emil's answer. In particular we need $\models$ = $\vdash$ (his Proposition 2) in order to prove the matroid property, and this is done by a case-by-case analysis, so it is not clear what happens for higher values of $n$. $\endgroup$ May 4, 2013 at 18:02
  • $\begingroup$ @François: You managed to algebraicify the problem. Great. Thanks. $\endgroup$
    – Ralph
    May 17, 2013 at 10:06
17
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ Thanks for the comment. The proposed solution in the original question shows that it is possible to get away with only checking 4 squares (provided you check all the rows and columns also), so I am a bit confused. $\endgroup$
    – Tony Huynh
    Apr 30, 2013 at 6:34
  • $\begingroup$ @Denis: sudoku works on 81 squares, not $3^3 = 27$ as you propose. I think there is no symmetry between rows and squares. E.g., every row intersects 9 distinct columns but every square only intersects three columns. Could you elaborate? $\endgroup$
    – Marek
    Apr 30, 2013 at 9:14
  • $\begingroup$ @Tony : If we only check 6 rows and 6 columns, then there are 9 cells which can be altered indifferently, so we need to check all 9 squares. Using this kind of reasoning, it seems you can improve your lower bound to 18. $\endgroup$ Apr 30, 2013 at 12:12
  • $\begingroup$ @Francois: Agreed. My bounds are absolute lower bounds on r,c and s (where r, c and s are what you think they are), while the quantity we are actually interested in is r+c+s. By considering the interaction between cells, rows and columns the bound can be improved (probably to 21). $\endgroup$
    – Tony Huynh
    Apr 30, 2013 at 18:16
  • 1
    $\begingroup$ I think you can do $1$ better for s, assuming I have the right construction in mind which works except on a corner set (flip pairs of elements along each side of the rectangle, so that rows keep the same elements on horizontal flips, and the number of vertical flips is even, and vice versa for columns). This just requires an even number of squares be chosen in each row and column, which you do with a corner set, taking $2$, $2$, and $0$. You can make the same construction with $2$ squares in each row and column (like the complement of a minimal set of squares that meets all corner sets). $\endgroup$ Apr 30, 2013 at 18:47
14
$\begingroup$

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

    Maximal incomplete sets

  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.

$\endgroup$
6
  • $\begingroup$ Nice! It is not hard to see that any minimal complete set is a maximal independent set. Do you know whether the converse holds? $\endgroup$ May 2, 2013 at 14:28
  • $\begingroup$ Emil, thanks. I'll work through the details of your answer (and the other answers and comments) at the weekend and reply at the beginning of next week. $\endgroup$
    – Ralph
    May 2, 2013 at 15:25
  • $\begingroup$ @François: I don’t know. I find independence rather difficult to check by hand. $\endgroup$ May 2, 2013 at 17:01
  • $\begingroup$ All the consequence relations coming from $\mathcal{D}$ are linear, in the sense that $x \in \operatorname{Vect}(D \backslash \{x\})$ for every $x \in D \in \mathcal{D}$ (here we view $r_i$, $c_j$, $b_k$ as formal linear combinations of Sudoku cells). I think we can deduce from this that the Steinitz exchange axiom holds, and thus $\models$ is indeed a matroid. $\endgroup$ May 3, 2013 at 16:05
  • $\begingroup$ Doesn't this imply that we can check a system is optimal by just checking you can't remove any of the rows, columns, or blocks? That cuts down dramatically on the case work. $\endgroup$
    – Will Sawin
    May 4, 2013 at 2:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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