For Logic Problem, A Technical Solution

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 took seven.

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.