When Harvard students are confronted with a problem, they go above and beyond to solve it—even if it’s just a game.
Several students have recently been struggling with sudoku
number puzzles, so senior Inna I. Zakharevich ’06 wrote a computer
program that solves them instead.
Sudoku is a number game based on a nine-by-nine grid. The
object of the puzzle is to fill each column, row, and three-by-three
square using the numbers one through nine only once.
Zakharevich’s program, featured on her website
(www.people.harvard.edu/~zakharev), has two parts. The part that a user
sees is a display of white boxes, controlled by a Common Gateway
Interface (CGI) script, that organizes numbers in a sudoku grid.
Another program, written in a computer language called Objective
Categorical Abstract Machine Language (OCaml), does the actual number
evaluation behind the scenes.
The user inputs numbers into the grid, and the program fills
the remaining boxes with certain solutions. If a box might contain
multiple number possibilities, then the program gives both
possibilities, and it is up to the user to choose which one to input in
the box before rerunning the program.
Zakharevich said she first encountered sudoku in a book that
she purchased on a whim. After completing only two or three puzzles,
however, she said they had already begun to lose their appeal. She
recalls repeatedly following the same process to obtain answers.
“I thought, ‘This is silly. I’m doing this algorithmic thing
that a computer could do,’” said Zakharevich. “And then, I wondered,
‘Why not write a computer program to do it?’”
The number-evaluation program initially associates each space
in the grid with every number possibility from 1 to 9. When the user
inputs numbers, possibilities are removed depending on where the
numbers are placed. The program then applies a series of rules that
yield a grid of solutions, Zakharevich explained.
Zakharevich said she completed the entire program in one
night, without assistance from anyone. She originally estimated that
the program would only take her an hour to complete, but it ultimately
She recalled most of the time being spent not on the
number-evaluation component itself but on manipulating the CGI script
which controls the sudoku display, making it more user-friendly.
“I was up till like nine in the morning,” she recalled, laughing. “It was probably not a good idea.”
Zakharevich is currently a Mathematics concentrator in the
midst of writing her thesis. Once a joint math and computer science
(C.S.) concentrator, she said she dropped C.S. because she could not
find a suitable thesis topic. She said she had taken some
programming-intensive courses at Harvard, and had also done a little
programming in high school.
“I had significantly less experience than most people who are
serious about computer science, but significantly more experience than
those are aren’t serious about computer science,” she said as she
smiled. “But this was a for-fun project.”
In addition to computer programming, Zakharevich has a host of
other interests, including reading, playing Frisbee, and most notably,
knitting. On her website, she also maintains a knitting blog and a list
of her favorite quotes.