# Is there a Sudoku matroid?

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.

-
I just answered to this in the original question :) mathoverflow.net/questions/129143/… – François Brunault May 4 '13 at 2:18