Here’s Mathematician KP Hart’s Math Question and Answer for today:
Sudoku 9×9
9 rows, 9 columns and the 9 squares contain the numbers 1 through 9. The 9×9 Sudoku puzzles have a number of digits. How many digits are minimally necessary so that the solution is unique?
This question was answered in January 2012: a well-posed Sudoku puzzles needs at least 17 givens, that is, there are well-posed puzzles with 17 givens and no well-posed puzzles with 16 givens. Note: well-posed means that the puzzle has a unique solution.
Gary McGuire, Bastian Tugemann, and Gilles Civario of University College Dublin set to work a number of computers in the Irish Centre for High-End Computing and from January till December 2011 these computers verified that no puzzle with 16 givens is well-posed. A lot of work was put in beforehand: the idea was to start from the list of all completed Sudoku squares and check each 16-element set of digits in each puzzle; since such a set comes from a completed puzzle we know that there is a solution and the question then is whether that is the only solution possible from that set of 16 givens.
The problem is that there are about 6×1021 completed Sudoku squares and every square has about 33×1015 subsets of 16 digits. The number of seconds in a year is about 31.5 million; how many possibilities would have to be checked, per second, if we tried to get through all squares and subsets in a year? Fortunately we `only’ have to go through roughly 5 billion (5,000,000,000) squares, so that reduces the workload by a factor of 1016. It is also possible to skip a lot of 16-element subsets because these will obviously not give a unique solution, for example if you don’t pick any cells from the top band of three rows. McGuire, Tugemann, and Civario developed clever methods to weed out as many obviously bad subsets as possible and thus reduce the search time to a mere year.
Further reading
- The article by McGuire, Tugemann, and Civario is available on ArXiV.org
- On technologyreview.org you can find a summary that is a bit easier to read.
*********************************
About Dutch Mathematician KP Hart: In the beginning of this year the Dutch government opened a website, The Dutch Science Agenda, where everyone could post questions that they thought were of scientific interest. This was an attempt to involve the whole country in determining what the Dutch science agenda should be in the coming years.
I looked through the questions and searched for terms like `mathematics’, `infinity’ … to see what mathematical questions there were and I noticed various questions that already have answers (and have had for a long time). On a whim I decided to post answers to those questions, in Dutch. For your edification I will translate these posts into English.
RELATED: YOUR MONDAY MATH with Mathematician KP Hart: The Number Zero!
- CAPTAIN AMERICA: BRAVE NEW WORLD and the Importance of Self-Love - March 18, 2025
- HAPPY PI DAY – Who Invented Pi? - March 14, 2025
- 5 Best Video Games That Let You Play Poker - February 13, 2025
