In addition, McGuire’s team built on many different ideas, discussions and computer programs that were thrashed out between interested contributors to various online forums devoted to the mathematics of Sudoku. The results of any huge computation should be evaluated with some caution, if not outright suspicion, especially when the answer is simply “no, doesn’t exist”, because there are many possible sources of error.īut in this case, I feel the result is far more likely to be correct than otherwise, and I expect it to be independently-verified before too long. As you can imagine, this required substantial computing power.Īfter 7 million core-CPU hours on a supercomputer (the equivalent of a single computer running for 7 million hours) and a year of actual elapsed time, the result was announced a few weeks ago, on New Year’s Day.
EVIL SUDOKU SOFTWARE
Once the theory and software was in place, it was then a matter of running the programs for each of the 5.5 billion completed grids. “hit”) can be modelled as a hitting set problem. It’s a problem that has many other applications – any situation in which a small set of resources must be allocated while still ensuring that all needs are met by at least one of the selected resources (i.e. In the process of resolving this question, McGuire’s team developed new techniques for solving the “hitting set” problem.
While finding all the unavoidable sets in a given grid is difficult, it’s only necessary to find enough unavoidable sets to show that no 16 clues can “hit” them all. If it did not, then in any completed puzzle, those ten positions could either contain the left-hand configuration or the right-hand configuration and so the solution would not be unique. If a completed grid contains the ten-clue configuration in the left picture, then any valid Sudoku puzzle must contain at least one of those ten clues. See the picture below to see what I mean. For a puzzle to be uniquely completable, it must contain at least one entry from every unavoidable set. Instead, McGuire and colleagues used a different, indirect approach.Īn “unavoidable set” in a completed Sudoku grid is a subset of the clues whose entries can be rearranged to leave another valid completed Sudoku grid. The total number of completed puzzles (that is, completely filled-in grids) is astronomical – 5,472,730,538 – and trying to test each of these to see if any choice of 16 cells from the completed grid forms a valid puzzle is far too time-consuming. They key to McGuire’s approach was to tackle the problem indirectly. I thought that demonstrating this would either require some new theoretical insight or clever programming combined with massive computational power, or both.Įither way, I thought proving the non-existence of a 16-clue puzzle was likely to be too difficult a challenge.
I was also convinced there was no 16-clue puzzle. Other people started to send me their 17-clue puzzles and I added any new ones to the list until, after a few years, I had collected more than 49,000 different 17-clue Sudoku puzzles.īy this time, new ones were few and far between, and I was convinced we had found almost all of the 17-clue puzzles. By slightly altering these initial puzzles, I found a few more, then more, and gradually built up a “library” of 17-clue Sudoku puzzles which I made available online at the time. In early 2005, I found a handful of 17-clue puzzles on a long-since forgotten Japanese-language website. I was particularly interested in the question of the smallest number of clues possible in a valid puzzle (that is, a puzzle with a unique solution). They were less interested in solving individual puzzles, and more focused on asking and answering mathematical and/or computational questions about the entire universe of Sudoku puzzles and solutions.Īs a mathematician specialising in the area of combinatorics (which can very loosely be defined as the mathematics of counting configurations and patterns), I was drawn to combinatorial questions about Sudoku.
EVIL SUDOKU PROFESSIONAL
When Sudoku-mania swept the globe in the mid-2000s, many mathematicians, programmers and computer scientists – amateur and professional – started to investigate Sudoku itself.
Reckon you can complete a 17-clue Sudoku puzzle? (answer below) Gordon Royle
0 kommentar(er)
