Upon meeting Will Gibson (Doctor Octagon) the creator of the Manitoban’s sudoku puzzles, two things are abundantly clear: this man knows his computers and he knows his sudoku.
For those not familiar with the puzzle phenomenon whose popularity has grown exponentially since 2005 when it left puzzle books and started hitting the mainstream, sudoku is a puzzle involving nine blocks each divided into nine squares. Some of the 81 squares are left blank, while others contain a clue consisting of a single digit from one to nine. The goal of the puzzle is to fill in the blank portions of the puzzle such that each row, column and block contains each of the numbers one through nine only once.
Sudoku puzzles can range in difficulty from very easy, where a majority of the puzzle is already filled in, to very difficult, requiring specialized strategies and logic to solve.
Originally called “number place,” and published in Dell Magazines (a popular publisher of puzzle books) for the first time in the late 1970s, the iteration we are most familiar with, suuji wa dokushin ni kaguri (“the numbers must be single”), sudoku for short, was adapted from “number place” by Japanese puzzle company Nikoli.
While another person might have elected to download one of the many sudoku puzzle builders from the Internet, Gibson, who holds bachelor degrees in both computer science and mathematics, decided to combine his passions and build his own.
Operating the program appears simple enough. After deciding on a design, how many clues to give, and what some of those clues should be on paper, Gibson translates his paper copy to a digital format his program can recognize and types the command “make” into his keyboard.
At first nothing happens, and less patient individuals such as myself have to resist the urge to start pounding keys with the goal of waking up the computer. Then a readout appears on the screen, letting Gibson know that the computer has found a puzzle which fits his parameters. Along with the puzzle’s solution, the program tells us how long it took to find, and the steps Gibson’s program would need to go through in order to solve this particular puzzle were it seeing it for the first time.
From that last bit of information Gibson decides where the puzzle falls on his difficulty scale, which ranges from “very easy” all the way to “death.” If he is not happy with the difficulty of the puzzle created by the computer, Gibson can set a maximum or minimum difficulty, however he explains that with each new constraint put on the puzzle, whether it’s from insisting that a clue be a specific number, or that the puzzle adhere to a set level of difficulty, the number of possible “valid” puzzles decreases, along with the computer’s chance of finding a solution in a reasonable amount of time, or at all.
“What is a ‘valid’ sudoku puzzle?” you may be asking yourself. Well, sudoku puzzle makers define a valid puzzle as one that has only a single possible solution, and while there are, according to Gibson 1081 (that’s a one followed by 81 zeros) possible ways to fill out a sudoku grid, according to a paper written by Bertram Flegenhauer and Frazer Jarvis, from the Dresden University of Technology and Sheffield University respectively, there are only 6.67×1021 possible valid grids, roughly the equivalent to the number of atoms in a one gram cube of uranium. That number shrinks to about 5.5 billion when symmetries, or puzzles that are essentially the same, only geometrically reversed, are taken into account.
Lucky for us, the puzzle Gibson and I designed was not too complicated and only took the computer a matter of seconds to find a valid solution. It can be seen on page 19, and contains a secret, science-related, word. The first person to decode the word from the puzzle and email the answer to science@themanitoban.com will receive a $10 gift certificate for Degrees Diner.
