Guy Haworth wrote:
Apologies if this is an 'old one' and I haven't been paying attention.
The question of the minimum number of clues for Sudoku (for a unique solution) is circulating. Apparently, 17 is ok but there are no known puzzles with 16 clues and a unique solution.
Anything known in this area?
You are correct, puzzles with 17 clues are known and no puzzle with 16 clues is known. It is now widely believed that no puzzle with 16 clues exists. There is a pseudo-puzzle with 16 clues and two solutions: 5.2...4.....71...3..............46...7.2......1.......6....2.......3..1.4........ The two completions of this are 562389471849716253137425896358194627974263185216857349691542738725638914483971562 562398471948716253137425986359184627874263195216957348681542739725639814493871562 and as you can see they only differ in that 8 and 9 are interchanged. If you fix either one of these completions, it contains 29 non-equivalent puzzles with 17 clues (well, at least 29, probably no more; these were found by Gordon Royle). This is the highest number known, so this grid was considered the best candidate for a 16. I have done an exhaustive search and there is no 16 in this grid. Of course, if a grid has a 16 puzzle then it has 65 puzzles with 17 clues, by adding one clue. The pseudo-puzzle gives rise to 18 puzzles with 17 clues (18 of the 29), adding any of the 8's or 9's. What I find remarkable is that we can't find any other pseudo-puzzles with 16 clues and 2 solutions. Can it really be unique? What is so special about either of these completed grids? Gary McGuire