← home

MATH 441 Sudoku Project, Thermo Sudoku

Context

Group project for MATH 441 (Discrete Optimization), March 2026. With Umay Gokturk and Tiffany Gong. We formulated three Sudoku variants as Binary Integer Linear Programs (BILP) using PuLP: Arrow, Killer, and Thermo. My part: Thermo Sudoku. 🌡️

GitHub: https://github.com/luna-ubc/sudoku

What is Thermo Sudoku

Classic 9×9 Sudoku rules, plus thermometer-shaped sequences of cells on the grid. Each thermometer starts at a bulb and ends at a tip, and values must strictly increase from bulb to tip.

BILP Formulation

Decision variable (inherited from classic):

G_{ijv} = 1 \text{ if cell } (i,j) \text{ contains value } v, \text{ else } 0

Helper: $H_{ij} = sum_{v=1}^{9} v cdot G_{ijv}$, the actual value in cell $(i,j)$.

Thermo constraint: for each thermometer t = ((r_1, c_1), \dots, (r_m, c_m)) and each consecutive pair:

H_{r_{n+1}, c_{n+1}} - H_{r_n, c_n} \geq 1

PuLP only accepts numerical RHS, so the strict inequality is rewritten as $geq 1$, equivalent given integer values.

Results

All three example puzzles below are sourced from GM Puzzles. Runtimes are averaged over 10 runs. Classic Sudoku averages 0.048s for comparison.

Example 1: 12 horizontal thermometers (0.050s, n=10)

Example 2: 8 zigzag thermometers (0.059s, n=10)

Example 3: 8 thermometers shaped "sorry" (0.062s, n=10)

All under 0.1s, comparable to classic Sudoku (0.048s).

Key Insight

A thermometer of length m adds m-1 inequality constraints. Long thermometers powerfully restrict the search space, a length-9 thermo immediately fixes values 1–9 from bulb to tip. So Thermo Sudoku can be solved with fewer pre-filled clues than classic.

Other Variants (Teammates)

  • Arrow Sudoku (Umay): circle cell = sum of path cells
  • Killer Sudoku (Tiffany): cage sum + no repeats within cage

Where This Goes Next, Rabbit Hole

The course project only solved given puzzles. Open questions that became the rabbit hole:

  • Can we generate Thermo puzzles from scratch?
  • How do we guarantee unique solutions?
  • Can this become an app?