Return to Question

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.

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.

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

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.

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

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