While you might just need a pencil and your brain to fill in this week’s Sudoku puzzle, an Irish mathematician used millions of hours of supercomputing time in order to solve an important open problem in the mathematics of Sudoku; the game that was initially popularized in Japan and involves filling up a 9×9 grid with the numbers 1 to 9 according to certain rules.
Gary McGuire of the University College Dublin recently posted a proof online that showed that the minimum number of clues, or starting digits, that were needed to complete a puzzle is 17. With 16 and fewer clues, the Sudoku puzzle doesn’t have a unique solution. Most of the puzzles that you’ll find in newspapers have around 25 clues. The less clues you have, the more difficult the problem.
The consensus is that McGuire’s proof is probably valid, which means that it’s an important advance in the field of Sudoku mathematics. The rules of Sudoku are simple. Puzzlers are required to fill out a 9×9 grid with the numbers 1 to 9 so that no digit is repeated in the same column, row, or 3×3 subgrid. The clues are numbers that are already filled out within the puzzle. Enthusiasts have observed that while there are some puzzles with 17 clues, no one has come up with a valid 16-clue puzzle. This led to the conjecture that 16-clue puzzles with unique solutions do not exist.
McGuire simplified the problem by designing a hitting-set algorithm, in which he searches for unavoidable sets that allow interchanges within the puzzle, meaning that they would allow multiple solutions. Once the unavoidable sets are found, the computing task was much more manageable. It took him two years to test the algorithm. McGuire and his team used about 7 million CPU hours at the Irish Center for High-End Computing in Dublin, searching through all possible grids with the algorithm. It’s what is called a brute force approach, crunching the problem down with massive computing power and iterations.
Since it took so long to come to the proof, it will also take a while for other mathematicians to check the proof. The algorithm was developed as McGuire developed proofs for papers in gene-sequencing and cellular networks.
Never miss a breakthrough: Join the SciTechDaily newsletter.
Follow us on Google and Google News.
5 Comments
Yesterday, while I was at work, my sister stole my iPad
and tested to see if it can survive a 40 foot drop, just so she can be a youtube sensation. My iPad
is now broken and she has 83 views. I know this is entirely off
topic but I had to share it with someone!
Please tell me you got a new one.
😭
Boost those views my guy! Drop the link to the video so your ipad didnt die in vain!
I feel your pain. So should your sister. YouTube audiences usually require multiple stunts to properly become engaged. Your sister being ejected from the roof of a four story building should achieve the desired results and satisfy her need for notarity.
Wow! In the end I got a weblog from where I be capable of really get useful facts regarding my study and knowledge.