Mathematicians Answer Long-Standing “Minimum Clue” Sudoku Question By Checking Every Possible Puzzle

brute force Gary McGuire Sudoku University College Dublin Xeon hex-core

by Eric Limer | 12:45 pm, January 6th, 2012

It’s official. There are no Sudoku puzzles with 16 clues or fewer, and it took about a year to figure that out. Gary McGuire and his crew at University College Dublin were the ones who spearheaded the campaign to find an answer to this eternal question and wound up solving it with brute force. Well, brute force, a little ingenuity, and 7.1 million core-hours of processing time on a machine with 640 Intel Xeon hex-core processors.

So you know Sudoku, right? It’s that little math game with the 9 3×3 grids where you have to fill it in with the numbers 1-9 in every row and column and the numbers 1-9 in every sub-grid. Simple enough right? Well there’s also another little rule that makes things a little more complicated: Any given Sudoku puzzle can only have one answer. Now, every Sudoku starts with a number of “clues,” the numbers given to you at the start. There are plenty of 17-clue Sudokus out there, so those are clearly possible, but no one has ever found a 16-clue sudoku. Moreover, no one has ever found a way to prove that there isn’t a 16-clue Sudoku somewhere. Until now.

The really issue here is that there’s no elegant, simplified equation dictating the number of clues you need. There still isn’t. But McGuire and friends know that there aren’t any 16-clue puzzles because they tried all of them. All 6,670,903,752,021,072,936,960. Obviously they didn’t do this personally, nor did they test all of them. This is where the ingenuity comes in. By using symmetry rules, they were able to mathematically prove that certain shifted, reflected, and otherwise similar puzzles were similar enough that if one didn’t have an answer, neither would its various symmetrically-related brethren. Using this knowledge, they pared the number down  to a more managable 5,472,730,538. Essentially, that’s how many Sudoku puzzles there really are.

But wait! There’s more! The process of testing each puzzle for a 16-clue solution involved taking each one of the 5 billion or so puzzles from step one, and testing to see if any of the possible 16-clue starting patterns (of which there are about 10^16) could lead to a unique solution. Again, ingenuity and math came to the rescue, and the McGuire Sudoku squad was able to reduce the number by mathematically proving that some 16-clue patterns are functionally identical to others.

This is where the proccessing power came in. After figuring out his plan of attack, McGuire turned to the aformentioned 640 Intel Xeon hex-core processor box and set it to work. 7.1 million core-hours later, the results came in; there are no valid 16-clue puzzles.

Now this may seem sort of like a fool’s errand, or just random mathematical wankery, but the things the team learned about reducing the sample pool through symmetrical comparison could have applications in things like gene expression analysis or network and software testing. It’s also worth noting that while we have an answer now, it’s via the old “guess and check” method. If this was a math test, you’d get half credit at best. Sudoku mathematicians are still out there looking for the holy grail of an equation that explicitly states “Sudokus need 17 clues, yo!” So get to it if you want full credit. You know what? Pull that off, and we’ll see what we can do about getting you some bonus points too.

(via Technology Review)

Relevant to your interests

• Laser-generated random-number encryption is functionally immune to brute force attacks
• Algorithm de-pixelates pixel art
• Check out this record-holding Rubik’s cube solving machine