http://www.smh.com.au/comment/column-8/column-8-20140513-zrb0n.html
This one just makes Column 8’s head hurt – make of it what you will. Greg Foster, of Canberra, enquires: ‘‘A sudoku puzzle that only has one square filled in must be easy to complete, and a sudoku puzzle that has only one square blank is also easy to complete, but how many blanks are needed before it becomes difficult?’’
- Column 8, Sydney Morning Herald, 14th May 2014.
Dr Karl on Science on Mornings, on the ABC's youth network Triple J, often likes to tell us that in some cases a Nobel prize for science isn't awarded for solving a problem but asking a question. In this example posed by Column 8 the question is almost the reverse of what you'd expect but nevertheless, probably has a discrete solution.
It turns out (and it took the best of 11 months of computer checking by University College Dublin) that the minimum number of clues required to make a meaningful sudoku with a single solution is 17. There are just over six and a half hexillion¹ possible arrangements of all the 9 numbers in a sudoku but many of those are either copies of each other where numbers substitute for other ones, or arrangements where whole 3x3 sections are merely translated about the board.
It you eliminate sets which are otherwise symmetrical or equivalent with each other, then this falls to a
mere 5 billion².
The question posed by column 8 though it slightly different. It wants to know how many blanks are required. I suspect (though I'm not really prepared to set up a computer to check for 11 months to find out) that the answer can be found using nothing more than applied logic.
http://www.sudoku-help.com/SHD-Ratings.htm
I have seen the Sudoku-Help Difficulty (SHD) Rating by Greg Shalless in the newspaper before and have often thought that it was delightfully trivial. Oscar Wilde once said that "It is a very sad thing that nowadays there is so little useless information" and to be honest, it is the useless and often trivial which are so very very paradoxically wonderful.
The key part of the question in Column 8 is this phrase: "how many blanks are needed before it becomes difficult?" Now usually when you ask about the difficulty of something, it's not easy to determine but Mr Shalless' rating system provides that the bare minimum rating for something "difficult" is 79.
I suspect that the way to do this is to start with a valid board and work backwards. If it were possible to generate a board with a set of Hidden Quads, that spawned another set of Hidden Quads, that spawned yet another set of Hidden Quads and then a fourth, and each of those four sets in turn generated Locked Triples and Locked Quads, then provided there was a "free" set of independent Locked Triples, then then minimum number of blanks required would only be 19 to generate a difficulty rating of 79.
Such an arrangement would require drill downs on at least three levels for most of the blanks before you arrived at a solution. Incidentally, testing this with GNOME Sudoku generator, yields at best 24 blanks³.
There would be a real symmetry if the number of blanks needed before a sudoku becomes difficult was also 17 but that kind of depends on what an actual definition of what "difficult" actually is.
Addenda:
The smallest number of blanks where there is something solvable is 3. In that case there'd be an Only Spot Box and a Linked Pair.
The smallest number of blanks I think that it takes to be interesting is 5; which could either be a pair of Linked Pairs and an Only Spot Box or a Linked Quad and an Only Spot Box.
The smallest number of blanks that I've found that qualifies for a "Novice" level is 12 but that would require a series of nested Linked Quads and Hidden Quads; neither of which would usually appear in a Novice Sudoku.
¹Actually 6,670,903,752,021,072,936,960 to be precise.
²Actually 5,472,730,538.
³http://sourceforge.net/projects/gnome-sudoku/
No comments:
Post a Comment