Sudoku clues have a minimum—say the computers
By Steven Powell, 803-777-1923, firstname.lastname@example.org
Sudoku addicts might have a new favorite number: 17. According to a team led by Irish mathematician Gary McGuire, if you get any fewer than that many clues, you should move along to the crossword--the puzzle can't be solved. They published their results online on the first of the year.
According to Joshua Cooper, a mathematics professor in the University of South Carolina's College of Arts and Sciences, once Sudoku caught on, people immediately began wondering what the minimum number of clues, sometimes called givens, had to be provided in a fair puzzle. So the research provides a sense of certainty in the Sudoku world--at least for those who think a computer-assisted proof is a proof. But more on that later.
The Sudoku setup
A solved Sudoku puzzle is a 9 x 9 grid filled with the numbers 1 through 9, but with a very precise ordering therein. The large grid comprises nine smaller 3 x 3 sub-grids. Each nine-member column, row, and sub-grid shares the same property: the nine entries must be the numerals 1 through 9, with no repeats and no omissions.
Creating a solved Sudoku grid, with the 81 entries arranged properly, is a challenging step one for a puzzle maker. Step two involves removing numbers to create a partly filled-in board for the Sudoku enthusiast, who then uses a variety of logical approaches to determine the numerals and work back to the original.
"In the wild, so to speak, Sudoku puzzles tend to have between 22 and 27 givens," said Cooper, "that's what you usually see in newspapers."
But you can have a fair puzzle with fewer givens than that. "Someone very quickly asked, what's the fewest number of clues that you can have in a fair puzzle, with a fair puzzle being one you can solve in a unique way," said Cooper.
The answer has appeared to be 17 for a while now. "Gordon Royle runs a webpage where he compiles puzzles with 17 givens, and he has almost 50,000 non-equivalent puzzles with 17 givens," said Cooper.
The question has always been, can you get away with fewer?
No fair 16-clue puzzle has ever turned up. In the mathematics-of-Sudoku world, though, that's not the same thing as certainty. Proof, or rather, a proof, is the standard.
A proof in two parts
And that's what the Irish team offered on Jan. 1. Setting out to test all 16-given puzzles for solvability, they took a two-pronged approach. First, they used a variety of mathematical arguments to dramatically reduce the pool of 16-given puzzles that required checking. Then computers were brought to bear on the problem.
And that computation was a tour de force, or perhaps a tour de brute force. Using a cluster with 320 nodes, each with two processors, the team used more than 7 million core hours to determine that 5.5 billion 16-clue puzzles couldn't be solved. And that was after toiling for several years to develop the code for the computers.
In the end, the results look convincing. "It appears to be solid," said Cooper. "The theoretical framework is straightforward, and most of the work consists in the year-long computation that the team did."
Just what does 'computer-aided proof' mean?
But being convincing and being a proof are not necessarily the same.
"One of the problems with accepting computer-assisted proofs is that they're not human-checkable. So if a cosmic ray came flying in from a nearby supernova--which happens all day long every day--and if it just happened to strike the wrong transistor at the wrong time, it could flip a state of a register in the computer," said Cooper. "Then the computation would perhaps say that some puzzle with 16 givens was not uniquely solvable when, in fact, it was."
"NASA has known about this forever, so when they have mission-critical computer equipment on vehicles that are exposed to solar radiation--and not protected by the Van Allen belts from radiation as we are on earth--they use what they call 'hardened' chips. They are fault-tolerant, so even if they're struck by a high-energy particle streaming out of the sun, they still don't make mistakes, or at least most of the time they don't make mistakes."
"And these folks in Ireland, as far as I know, were using ordinary computers on the surface of the earth. So in theory it could be wrong, if there was a computational error."
"It's interesting," continued Cooper. "It really gets to the heart of a current debate in mathematics: whether computer-assisted proofs are proofs or not. It's been going on since Appel and Haken produced their proof in 1976 of the four-color theorem. That showed that any map can be colored with four colors without any two adjacent countries getting the same color."
"It's been a source of debate ever since, because although there's a lot of graph theory and other mathematics that went into the proof, the majority of the argument is just a huge computation. So the four-color theorem, according to some people, is still unproven, because there isn't a human-readable proof of it."
The 400-year-old Kepler conjecture is another example. "That says that the way oranges are stacked in the grocery store is actually the most efficient way to do it. It gets the most oranges into the least amount of space," said Cooper. "Thomas Hales proved it in 1998, but again, he used a massive computation." After sending the paper to the prestigious Annals of Mathematics, the editors took years to referee it. "In the end, they published the paper with a disclaimer, saying that, from now on, they're willing to publish computer-assisted proofs, but they couldn't vouch for the computer-assisted part."
"With the computation, they essentially take the stance of agnosticism," said Cooper.
Sudoku research at USC
Cooper finds Sudoku to be a great gateway for getting undergraduates interested in research. For five years running, USC's Gamecock Math Club and mathematics honor society Pi Mu Epsilon have hosted a Sudoku competition. Cooper has contributed introductory talks on four of those occasions, including a presentation on Jan. 31 that covered the Irish team's 17-given-minimum proof.
He's also supervised two Magellan scholars, Nick Jaamin Smith and Anna Kirkpatrick, on research related to Sudoku. He's working on a paper with Kirkpatrick's results that should be published later this year.
But Sudoku is meant to be fun. "I'm definitely fond of a good puzzle," said Cooper. "I have an app on my Blackberry that generates puzzles, and it has eaten hundreds of hours of my time."
News and Internal Communications