IEEE Computer Society Newsfeed

Subscribe RSS

« Back

Academic Uses Supercomputer to Solve the Math behind Suduko Puzzles

An Irish mathematician has used a complex algorithm and 7 million hours of CPU time to solve a problem in the mathematics of Sudoku. The puzzle, popularized in Japan, involves filling in a 9 × 9 grid of squares with the numbers 1 through 9, with no digit repeated in a column, row, or 3 × 3 sub-grid. University College Dublin associate professor of mathematics Gary McGuire issued a proof showing that the minimum number of clues—the numbers provided at the start of the process—needed for a puzzle to be uniquely solvable is 17. Sudoku puzzles with 16 or fewer clues don’t have a unique solution. Most newspaper puzzles reportedly have about 25. McGuire spent two years designing and testing the algorithm he used. The concept has been used previously in gene-sequencing analysis and cellular networks. Some other mathematicians have expressed concern that checking McGuire’s proof could require a lot of time because of the amount of computing required to generate the proof in the first place. McGuire confessed to Nature magazine that he prefers solving crossword puzzles, rather than Sudoku, in his spare time. (SlashDot)(Nature)(ArXiv)

Trackback URL: