This question is inspired from this [one](https://mathoverflow.net/questions/129143/verifying-the-correctness-of-a-sudoku-solution), where it is asked what is the minimum number of checks needed to verify that a Sudoku solution is correct. Let 


$$
E=\{r\_1, \dots, r\_9\} \cup \{c\_1, \dots, c\_9\} \cup \{b\_1, \dots, b\_9\},
$$
where $r\_i, c\_i$, and $b\_i$ are the set of rows, columns and boxes of the Sudoku. We have an oracle, which given any $e \in E$, tells us if our Sudoku (which we cannot see) is correct on $e$. The original question was to determine what is the minimum number of calls we need to make to the oracle to verify a correct Sudoku. 


For $S \subseteq E$, and $x \in E$, we say that $S$ *implies* $x$ if every Sudoku which is correct on all members of $S$, must also be correct on $x$. Following Emil Jeřábek's notation, we write $S \models x$, if $S$ implies $x$. The original question asks for the smallest set $S$ such that $S \models x$ for all $x \in E$. 


The question here is: 



> 
> Is $\models$ a closure operator of a matroid with ground set $E$?
> 
> 
> 


This is something I've been wondering myself, and I suspect the answer is yes. This question was also explicitly asked by François Brunault, so I thought I'd publicize it independently.


I'll comment that the fact that $\models$ yields a matroid $M$ gives a very short proof of the original question (minus the verification that $M$ is a matroid of course). 


**Proof.** Phrased in the language of matroid theory, the original question asks what is the rank of $M$? Now, let $S$ be a set of checks consisting of all boxes, 2 rows from each band, and 2 columns from each stack. It is easy to see that the closure of $S$ in $M$ is all of $E$. On the other hand, for each $e \in S$, we have $cl\_M(S - e) \neq E$. This is also easy; removing a box leaves a cell $x$ such that the row, column, and box containing $x$ are all unchecked, removing a row yields a band with two unchecked rows, and removing a column leaves a stack with two unchecked columns. So, $S$ is an independent and spanning set of $M$, and hence a basis of $M$. Thus, $r\_M(E)=|S|=21$. 


**Update.** I wrote a blog post on this and some related questions on the [Matroid Union Blog](http://matroidunion.org/?p=1070). 



Is there a Sudoku matroid?
By some sort of strange mathematical cosmic entanglement, it appears that François Brunault answered his own question in the other [thread](https://mathoverflow.net/questions/129143/verifying-the-correctness-of-a-sudoku-solution) while I was writing this question. 


The answer is indeed **yes.** Feel free to click on the original question and vote up his answer! Or vote this answer up (I've made it community wiki). 


