Sudoku Matroids


Draft
Posted on December 16, 2025 by Yu Cong
Tags:

In a 3×3 sudoku there are 9×9 cells and 3×9 constraints (9 rows, 9 columns and 9 blocks). Given a filled sudoku, how many constraints are necessary to verify that the solution is correct?

Refs:

We need some sudoku notations. 
       [3x3 sudoku]
      +---+---+---+
  +---+-B | B | B |  ← band 1 (each 3 rows)
  ↓   +---+---+---+
Block | B | B | B |  ← band 2
  ↑   +---+---+---+
  +---+-B | B | B |  ← band 3
      +---+---+---+
        ↑   ↑   ↑
          stacks (each 3 columns)

Note that a n×nn\times n sudoku contains nn bands, nn stacks and nn blocks. So there are n4n^4 cells and each cell can be filled with some number in [n2][n^2].

Solving n×nn\times n sudoku is NP-hard.
see wikipedia

1 matroid on constraint set

We will see that there is a matroid with constraints as its groundset.
The idea is from the joint work of authors in the mathoverflow question. I think this is a simpler and more intuitive proof.

Let SS be the set of constraints. Take a subset T⊆ST\subseteq S of constraints. We say that TT spans a constraint s∈Ss\in S if every filled sudoku grid (with fixed dimension) satisfies TT also satisfies ss. Then span⁡#(T)\operatorname{span}_\#(T) is the maximal set of satisfied constraints if we check TT.
We will work on vector spaces. To avoid confusions we use span⁡#\operatorname{span}_\# for sudoku span function and use span\operatorname{span} for the span function in vector spaces and matroids.
Theorem1

Let SS be a finite set. A function span⁡:2S→2S\operatorname{span}:2^S\to 2^S is the span function of a matroid iff
  1. T⊆span⁡(T)T\subseteq \operatorname{span}(T) for all T⊆ST\subseteq S;
  2. if T,U⊆ST,U\subseteq S and U⊆span⁡(T)U\subseteq \operatorname{span}(T), then span⁡(U)⊆span⁡(T)\operatorname{span}(U)\subseteq \operatorname{span}(T);
  3. if T⊂S,t∈S\span⁡(T)T\subset S, t\in S\setminus \operatorname{span}(T), and s∈span⁡(T+t)\span⁡(T)s\in \operatorname{span}(T+t)\setminus \operatorname{span}(T), then t∈span⁡(T+s)t\in \operatorname{span}(T+s).

It follows immediately from the definition of our span function that (1.) and (2.) are satisfied. We need to prove (3).

Let’s forget about matroids for now and try to understand why some constraints are not necessary. A vague idea is that the sudoku grid structure comes with some information about the occurrence of the correctly filled numbers in some cells.

The definition of “satisfy” does not reveal information of the sudoku structure. To solve this issue, consider a linear mapping ϕG:S→ℤn2\phi_G:S\to \mathbb{Z}^{n^2} for every filled sudoku grid GG. For a cell x∈Sx\in S, we define ϕG(x)\phi_G(x) to be an n2n^2 dimensional vector, which indicates the number of occurrence of each number in [n2][n^2]. Then xx is satisfied by sudoku grid GG iff ϕG(x)=𝟏\phi_G(x)=\mathbf 1.

Note that our linear mapping ϕ\phi works on linear combinations of SS, so we slightly change its type to ϕG:V→ℤn2\phi_G:V\to \mathbb{Z}^{n^2} where VV is the vector space generated by elements in SS.
Later we will see that SS is not linearly independent and thus is not a base of VV.
Consider vectors ∑j∈[n]rij\sum_{j\in [n]} r_{ij} (sum of rows in a band ii) and ∑j∈[n]bij\sum_{j\in [n]} b_{ij} (sum of blocks in the same band). They cover exactly the same set of cells. So for any grid GG, ϕG(∑j∈[n]rij−∑j∈[n]bij)=0\phi_G(\sum_{j\in [n]} r_{ij} - \sum_{j\in [n]} b_{ij})=0. The same happens for columns and blocks in the same stack. We denote by V0V_0 the subspace of VV in which ϕG\phi_G is 00 for all grid GG.
Lemma2

Let T⊂ST\subset S be a set of constraints and let s∉Ts\notin T be a constraint. Then TT spans ss in the sudoku if and only if s∈span⁡(T∪V0)s\in \operatorname{span}(T\cup V_0) in the vector space VV.
Note that span⁡(T∪V0)\operatorname{span}(T\cup V_0) is the subspace of VV spanned by vectors in T∪V0T\cup V_0.

Note that TT spans ss means that for any sudoku grid GG such that ϕG(t)=𝟏\phi_G(t)=\mathbf 1 for all t∈Tt\in T, we have ϕG(s)=𝟏\phi_G(s)=\mathbf 1.

[the if part] Since s∈span⁡(T∪V0)s\in \operatorname{span}(T\cup V_0), we can write ss as ∑iαiti+y\sum_i \alpha_i t_i+y where ti∈Tt_i\in T and y∈V0y\in V_0. It follows from the linearity of ϕ\phi that ϕG(s)=∑iαi𝟏+0\phi_G(s)=\sum_i \alpha_i \mathbf{1}+0 holds for every grid satisfying TT. Then we pick a correctly filled grid G*G^*. One can see that 𝟏=ϕG(s)=(∑iαi)𝟏\mathbf{1}=\phi_G(s)= (\sum_i \alpha_i) \mathbf{1} which implies ∑iαi=1\sum_i \alpha_i=1. Then we have ϕG(s)=1\phi_G(s)=1.

[the only if part] Suppose by contradiction that s∉span⁡(T∪V0)s\notin \operatorname{span}(T\cup V_0) and for every GG satisfying TT we have ϕG(s)=𝟏\phi_G(s)=\mathbf 1. We can write s=∑iαiti+∑jβjsj+ys=\sum_i \alpha_i t_i + \sum_j \beta_j s_j+y where sjs_j’s are in the basis SS but not in the span. Again there is a G*G^* that satisfies every constraint and we have ∑iαi+∑jβj=1\sum_i \alpha_i+\sum_j \beta_j=1. Now consider any grid GG that satisfies TT. We have ϕG(s)=∑iαi𝟏+∑jβjsj=𝟏\phi_G(s)=\sum_i \alpha_i \mathbf{1} + \sum_j \beta_j s_j = \mathbf{1}. One can see that the equation holds if and only if every sjs_j is 𝟏\mathbf 1, which contradicts the fact that s∉span⁡(T+V0)s\notin \operatorname{span}(T+V_0).
This requires some properties of the sudoku graph and does not hold for all perfect graphs. See the K2,2,2K_{2,2,2} example in the matroid union post.

Now we show (3) in Theorem 1 for sudoku span.
Proofof (3)

It follows by Lemma 2 that span⁡(T∪V0)∩S=span⁡#(T)\operatorname{span}(T\cup V_0)\cap S = \operatorname{span}_\#(T) for T⊂ST\subset S. Note that f(T)=span⁡(T∪V0)f(T)=\operatorname{span}(T\cup V_0) satisfies condition (3). It is easy to see that if f(T)f(T) satisfies (3) then f(T)∩Sf(T)\cap S also satisfies (3). Then it follows that span⁡#(T)\operatorname{span}_\#(T) is a span function of a matroid.

2 sudoku on graphs

We are going to play Sudoku on a class of connected graphs whose clique number ω(G)\omega(G) equals the chromatic number χ(G)\chi(G), and in which every edge belongs to some maximum clique. For example, bipartite graphs, sudoku graphs and octahedron belong to this class.

Here are some graph classes that every edge belongs to some maximum clique:
  • odd cycles. ω(G)≠χ(G)\omega(G)\neq \chi(G)
  • bipartite graphs. ω(G)=χ(G)\omega(G)= \chi(G) and we have sudoku matroid on maximum cliques.
  • sudoku graphs. ω(G)=χ(G)\omega(G)= \chi(G) and sudoku matroid ✓
  • octahedron. ω(G)=χ(G)\omega(G)= \chi(G) and sudoku matroid ×

Is there a nice characterization of graphs that
  1. ω(G)=χ(G)\omega(G)=\chi(G) and that
  2. maximum cliques cover all edges?

2.1 solvability

Let GG be a graph in which every edge is in a maximum clique. Let HH be the clique line graph of GG, in which the vertex set is the set of maximum cliques and there are kk-parallel edges if two cliques share kk vertices.

Note that one can also think about the uniform hypergraph of maximum cliques and see that HH is the line graph of an uniform hypergraph.

There are some existing works on uniform hypergraph coloring. Czumaj and Sohler [1] showed an ε\varepsilon-tester for ℓ\ell-colorability of kk-uniform hypergraphs with running time exp⁡(Õ(kℓ/ε)2)\exp(\tilde O(k\ell/\varepsilon)^2). Note that the definition of proper coloring on hypergraphs is no monochromatic hyperedge.

Our sudoku problem is equivalent to the following questions:
  1. Whether a kk-uniform hypergraph is kk-rainbow colorable. A hypergraph is kk-rainbow colorable if there exists a vertex coloring using kk colors such that each hyperedge has all the kk colors. See [2] and [3] for references. Another equivalent question is that if a given kk-uniform hypergraph is kk-partite.
    I guess there should be some papers showing that it’s NP-complete to decide if a kk-uniform hypergraph is kk-partite. haven’t found one.
  2. Find the strong chromatic number γ(H)\gamma(H) of kk-uniform hypergraphs. A coloring is strong if no color appears twice in the same hyperedge. (see [4]) We want to check if γ(H)=k\gamma(H)=k.

We try to characterize this subclass of kk-uniform hypergraphs using line graphs.
Lemma3

If HH is a tree, then GG is a perfect graph.
Proof

GG is chordal.
Lemma4

If HH is bipartite, then ω(G)=χ(G)\omega(G)=\chi(G).
Proof

Let CC be a maximum clique in GG. There are maximum cliques sharing vertices with CC. We write Si⊂CS_i\subset C for the vertex intersections. One can see that if Si∩SjS_i\cap S_j is nonempty then we will have a triangle in the clique line graph HH. So we assume SiS_i’s are disjoint since HH is bipartite.

Now consider an edge coloring of HH and recover from it a proper vertex coloring of GG. It follows from Kőnig’s theorem that HH has an edge coloring using exactly Δ\Delta colors where Δ\Delta is the max degree in HH. Note that each edge in HH corresponds to a shared vertex of two cliques. We color the vertex with the same color as the corresponds edge in HH. Now the partial coloring is proper for each clique since colors are taken from a proper edge coloring. Finally, one can see that for each maximum clique the number of uncolored vertices is exactly the number of unused colors, since SiS_i’s are disjoint.
Remark

Bipartite HH covers octahedron and even cycles but not sudoku graphs.

First we need to find a nice characterization of line graph or something else that covers sudoku graphs but excludes odd cycles. I guess there should be some connections in group theory. The plan is to try graph classes in Graph families defined by their automorphisms. Note that regular graphs, vertex-transitive graphs and Cayley graphs won’t work.

2.2 integral, Cayley and NEPS

Sudoku graphs are integral Cayley graphs.

I guess integral might be a key property to separate odd cycles and sudoku graphs, since the only integral odd cycle is C3C_3 which does not contradict the χ=ω\chi=\omega condition.

2.2.1 integral & NEPS

Torsten Sander [5] proved that sudoku graphs are integral. By integral it means that the eigenvalues of the adjacency matrix are all integral.

Sander’s proof basically shows that sudoku graphs are NEPS of four complete graphs and then uses a existing theorem on eigenvalues of NEPS. Given a set B⊂{0,1}n−𝟎B\subset \left\{ 0,1 \right\}^n-\mathbf 0 and graphs G1,…,GnG_1,\ldots,G_n, the non-complete extended pp-sum (NEPS) of these graphs with respect to basis BB is the graph GG with vertex set V(G)=V(G1)×…×V(Gn)V(G)=V(G_1)\times \dots \times V(G_n) and edge set E(G)E(G) such that (x1,…,xn),(y1,…,yn)∈V(G)(x_1,\ldots,x_n),(y_1,\ldots,y_n)\in V(G) are adjacent iff there exists some nn-tuple (b1,…,bn)∈B(b_1,\ldots,b_n)\in B such that xi=yix_i=y_i whenever bi=0b_i=0 and xi,yix_i,y_i are adjacent in GiG_i whenever bi=1b_i=1.
Lemma5

Let n≥2n\geq 2 be an integer and G1,…,G4=KnG_1,\ldots,G_4=K_n. If GG is the NEPS of GiG_i for basis B={(0,0,0,1),(0,0,1,0),(0,1,0,0),(1,0,0,0),(0,1,0,1),(1,1,0,0),(0,0,1,1)} \begin{aligned} B=\{&(0,0,0,1),\\ &(0,0,1,0),\\ &(0,1,0,0),\\ &(1,0,0,0),\\ &(0,1,0,1),\\ &(1,1,0,0),\\ &(0,0,1,1)\} \end{aligned} then GG is a sudoku graph.

See Figure 3 in [5] for the proof.

2.2.2 Cayley

Let GG be a group and let SS be a generating set of GG. The Cayley graph Γ(G,S)\Gamma(G,S) is a directed regular graph in which the vertices are the elements in GG and there is an edge from uu to susu with label ss for every s∈Ss\in S.

A sudoku graph with n2×n2n^2\times n^2 vertices is a Cayley graph of the abelian group Zn4Z_n^4. (Sudoku graphs are undirected. Consider a bi-directional edge undirected.) There’s a one-to-one mapping from every vertex in sudoku graph (every cell in sudoku grid) to Zn4Z_n^4. The tuple (a,b,c,d)(a,b,c,d) indexes the vertex in the aa-th band, bb-th row in that band, cc-th stack and dd-th column in that stack.(assuming numbers are 0-indexed.) Then the generating set is S={(0,0,0,x),∀x∈Zn}∪{(0,0,x,0),∀x∈Zn}∪{(0,x,0,0),∀x∈Zn}∪{(x,0,0,0),∀x∈Zn}∪{(0,x,0,y),∀x,y∈Zn}∪{(x,y,0,0),∀x,y∈Zn}∪{(0,0,x,y),∀x,y∈Zn} \begin{aligned} S &= \{(0,0,0,x),\forall x\in Z_n\}\\ &\cup \{(0,0,x,0),\forall x\in Z_n\}\\ &\cup \{(0,x,0,0),\forall x\in Z_n\}\\ &\cup \{(x,0,0,0),\forall x\in Z_n\}\\ &\cup \{(0,x,0,y),\forall x,y\in Z_n\}\\ &\cup \{(x,y,0,0),\forall x,y\in Z_n\}\\ &\cup \{(0,0,x,y),\forall x,y\in Z_n\}\\ \end{aligned}

Now one can see that each tuple in the basis of NEPS corresponds to a pattern of elements in generating set.

2.3 matroid on maximum cliques

…

References

[1]
A. Czumaj, C. Sohler, Testing Hypergraph Coloring, in: Automata, Languages and Programming, Springer, Berlin, Heidelberg, 2001: pp. 493–505 10.1007/3-540-48224-5_41.
[2]
V. Guruswami, R. Saket, Hardness of Rainbow Coloring Hypergraphs, in: 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017), Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2018: pp. 33:1–33:15 10.4230/LIPIcs.FSTTCS.2017.33.
[3]
V. Guruswami, S. Sandeep, Rainbow Coloring Hardness via Low Sensitivity Polymorphisms, SIAM Journal on Discrete Mathematics. 34 (2020) 520–537 10.1137/19M127731X.
[4]
G. Agnarsson, M.M. Halldórsson, Strong Colorings of Hypergraphs, in: Approximation and Online Algorithms, Springer, Berlin, Heidelberg, 2005: pp. 253–266 10.1007/978-3-540-31833-0_21.
[5]
T. Sander, Sudoku graphs are integral, The Electronic Journal of Combinatorics. 16 (2009) N25 10.37236/263.