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. 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 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |