Kye Shi

Thesis Advisor: Dr. Nicholas Pippenger (Harvey Mudd College - Department of Mathematics)

Second Reader: TBD

Contact: kwshi@hmc.edu

You can solve it... but can you play it?

Sudoku is a classic puzzle whose objective is filling out a 9x9 grid (partitioned into 3x3 "blocks") with numbers 1 through 9 such that each row, column, and block contains each number 1 through 9 exactly once. How hard is it to solve Sudoku? Like many other puzzles of similar flavor, the Sudoku [solvability] problem is NP-complete: NP, meaning that it is easy to check whether a proposed Sudoku solution satisfies the necessary constraints (but not necessarily easy to find such a solution); complete, meaning that if Sudoku can be solved efficiently than any other NP problem can also be solved efficiently (Sudoku is among the "hardest" problems in NP).

Among NP-complete problems are some of the hardest puzzles of real world interest (cryptography, DNA folding, navigation, etc.), and it is central to the millennium-prize-worthy P-vs-NP question. But that doesn't stop us from going further, just for the heck of it--what if we made Sudoku even harder?

Let's play a Sudoku game in which:

• We take turns assigning numbers to individual cells on a Sudoku board.

• Your objective: solve the Sudoku puzzle.

• My objective: make it hard--better yet, impossible--for you to solve the Sudoku puzzle. I may make all sorts of illogical, disadvantageous assignments, in the hopes of eliminating all possible remaining solutions.

For a given starting board, can a computer predict who will win? Are there optimal strategies for these games? How hard is it to compute optimal strategies for these games?