Skip to main content
2 of 6
fixed a typo
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

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.

Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187