Tonight’s Math Homework:
Set Theory and Sudoku
By Jennifer Sutton
Sudoku puzzles are ubiquitous. They’re in every newspaper alongside the comics; in every airport convenience store; and online, where they range in difficulty from “easy” to “evil.” And according to NMH teacher David Warren, they’re math homework, too.
This year, Warren taught a course called Discrete Math with Python, in which students learned about sets, algorithms, sequences, and combinations, and used the Python programming language to apply their theoretical learning. When they tackled set theory — the study of collections of unique objects — Warren asked them to design an algorithm that could solve Sudoku puzzles, which are collections of unique numbers. One student, Tyler Kristjansen ’21, took it a step further, making an algorithm that created the puzzles as well. “I joked that we could go into business by printing cheap Sudoku books to sell in airports,” Warren says.
Sudoku puzzles are like crosswords, but with numbers instead of words. Every puzzle has 81 spaces, or cells — nine squares with nine cells in each square, three rows of three, with a handful of the cells already filled in with a number between 1 and 9. The person solving the puzzle — or in the case of Warren’s class, the algorithm solving the puzzle — fills in the rest of the blank spaces with only the numbers 1 through 9, without repeating a number in each row, each column, and each 3 x 3 square. “With set theory — creating sets of different numbers — we can deduce which numbers need to go in which blank spaces,” Warren says.
The class used the programming language Python to create mathematical functions that proposed “candidate” numbers to fill in each blank space. First they tackled each row, then each column, then each square. “Once we created the tool, or the algorithm, we just ran it a lot,” Warren says. The process, he adds, “was like a blend of smart brute force and smart random choice.”
Or “luck, negligence, and trial and error,” says Kristjansen. He explains that as he tinkered with his algorithm in class, it “just started working randomly. I think I hit ‘backspace’ in a line of code, and suddenly it could solve any Sudoku puzzle.” Kristjansen wondered what would happen if he gave his algorithm an empty puzzle grid. “It filled everything in because it was trying to create a puzzle that worked,” he says. All Kristjansen had to do was delete random numbers from the newly filled-in puzzle and it became one that others could try to solve, too.
If you’re not a math person and set theory sounds confusing, Warren wants to convince you otherwise. “Any unordered group of things without any repetitions is a set,” he says. “A box of Crayola crayons is a set. The students in my math class are a set. They are both discrete groups of unique things that can be added and subtracted. Every day, people work with sets. They just don’t realize it.”