16
$\begingroup$

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.

$\endgroup$
1

1 Answer 1

10
$\begingroup$

By some sort of strange mathematical cosmic entanglement, it appears that François Brunault answered his own question in the other thread 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).

$\endgroup$
1
  • 4
    $\begingroup$ Some neighbours are partying very late, which explains the entanglement despite the time difference :) $\endgroup$ May 4, 2013 at 2:36

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.