This question is inspired from this one, 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.
