12.11
Let every Sudoku cell be a vertex and let there be one additional vertex for each symbol 1…9.
1. Vertex set (90 vertices)
• Cr,c, 1 ≤ r,c ≤ 9 (81 “cell–vertices”).
• Dk, 1 ≤ k ≤ 9 (9 “digit–vertices”).
2. Edges that impose the Sudoku rules
a) Clique of digits: connect every pair of D-vertices.
⇒ χ(K9) = 9 guarantees that any minimum coloring uses all nine different
colors, one per digit.
b) Row/column/box constraints:
for all unordered pairs (Ci, Cj) that lie in the same row, column or
3 × 3 sub-grid, add edge (Ci, Cj).
⇒ two cells that “see” each other cannot have the same color.
c) Clues: if cell (r,c) is pre-filled with digit d
connect Cr,c to every Dk with k ≠ d.
⇒ the only D-vertex that shares no edge with Cr,c is Dd, so
Cr,c must receive the same color as Dd.
3. Correctness
• If the Sudoku has a solution s, color each Dk with a distinct color k
and every Cr,c with the color that represents sr,c.
Because s obeys the Sudoku rules, adjacent C-vertices get
different colors; edges of type (c) are also respected, so we have a legal
9-coloring.
• Conversely, let φ be a minimum coloring of the graph.
Since the D-clique needs 9 colors, χ(G) = 9 and each Dk gets a unique color k.
Every C-vertex must use one of those 9 colors (using a 10th color would contradict
minimality).
Edges of type (b) ensure that cells in the same row/column/box have
different colors, and edges of type (c) fix the given clues.
Reading the color of Cr,c as the digit whose D-vertex has that color
produces a valid Sudoku solution.
4. Construction algorithm (Python-style pseudocode)
def build_graph(grid): # grid[r][c] is 0 or a given digit 1…9
V = {("C",r,c) for r in range(9) for c in range(9)}
V |= {("D",k) for k in range(1,10)}
E = set()
# a) digit clique
for k in range(1,10):
for l in range(k+1,10):
E.add((("D",k),("D",l)))
# b) row/col/box edges
for r1 in range(9):
for c1 in range(9):
for r2 in range(r1,9):
for c2 in range(9):
if r1==r2==c1==c2: continue
same_line = r1==r2 or c1==c2
same_box = r1//3==r2//3 and c1//3==c2//3
if same_line or same_box:
E.add((("C",r1,c1),("C",r2,c2)))
# c) clue edges
for r in range(9):
for c in range(9):
d = grid[r][c]
if d:
for k in range(1,10):
if k != d:
E.add((("C",r,c),("D",k)))
return V,E
Run any exact 9-coloring algorithm on (V,E); the resulting colors of the
C-vertices give the completed Sudoku.
Thus solving an arbitrary Sudoku instance is equivalent to finding a minimum (9-)vertex-coloring of the constructed 90-vertex graph.
Back to
Chapter 12
