Students make history with sudoku program
April 17, 2008
Three UW-River Falls students made history this week by becoming the first UWRF math team awarded the Meritorious designation by the Mathematical Association of America (MAA).
Seniors Chuck Bardel and John O’Brien-Schroeder, along with sophomore David Peschman teamed up to create SuperSudoku, a computer program that generates random sudoku puzzles. They submitted their program Feb. 18 as part of the 2008 Mathematical Contest in Modeling (MCM).
In order to enter the MCM, the team first had to choose between two problems. They decided to develop a generator that constructed sudoku puzzles of varying difficulty instead of creating a model that examines the effects of polar ice cap melting.
The team was given three days to work together and solve the problem without expert assistance, which included their project adviser, professor Kathy Tomlinson.
Each team member brought a little something different to the table, which made completing the project more efficient. While all three have backgrounds in math, O’Brien-Schroeder and Bardel, who are majoring in computer science, were able to handle most of the computer related portions of the program. Peschman, on the other hand, lacked a computer programming background, so he had to contribute in different ways.
“I had the most experience with sudoku puzzles,” Peschman said. “So I got to teach the others the methods to solving them and help come up with a logical way to create them.”
There are a few basic rules for creating a sudoku program, the team said. The same number can’t appear more than once in the same column, row or 3x3 cell box. Also, only one number is allowed per individual cell.
Although it’s not proven, SuperSudoku has the potential to generate every possible sudoku puzzle, no matter the difficulty level, the team said.
Sudoku puzzles range in difficulty, which is not necessarily based on the amount of numbers that are provided within the puzzle.
“The amount of given numbers does not correspond with the difficulty of the puzzle,” O’Brien-Schroder said. “The placement of the number is more important than the number itself.”
Creating a program that consisted of puzzles with varying levels of difficulty provided an open-form challenge to the team, which was fine with Bardel.
“I wanted to work on a more comprehensive problem,” Bardel said. “Not a closed-form problem with a definite answer.”
Besides creating the sudoku program, the team had to write a paper that explained their computer program, their results and the model they developed to aid in solving the problem. All three criteria contributed heavily to the judging portion of the MCM, which was completed April 11.
“We [were] judged on how well the program works and the written paper,” O’Brien Schroder said. “I doubt any two groups [had] the exact same solution.”
As part of the judging portion of the contest the teams were recognized as one of the following: Successful Participant, Honorable Mention, Meritorious or Outstanding Winner, according to the MCM Web site. Of the 1162 teams in the competition, only 161 earned the Meritorious designation, while only nine received the top honor of Outstanding Winner, according to the 2008 MCM statistics.
In past years, some UWRF mathematical modeling teams have earned honorable mention. While it was lovely to see this year’s team earn the highest designation in UWRF history, just entering the contest was a triumph in itself, professor Tomlinson said.
“As I see it, [Bardel, O’Brien-Schroder and Peschman] have made a tremendous achievement simply by participating in the contest,” Tomlinson said. “The real accomplishment is the work they have done to solve the problem and write their paper.”