Minimal Sudoku
Feb. 17th, 2012 09:22 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
essentialsaltesWhile on the subject of math, it turns out that 17 is the minimum number of clues for a Sudoku puzzle to be uniquely solvable.
"The strategy we used to finally solve this problem is an obvious one — exhaustively
search through all possible solution grids, one by one, for a 16-clue puzzle."
While not a mathematically elegant way of attacking the problem, it looks like the search method they developed and used may have other benefits.
And don't hold out hope for an elegant solution:
"It is worth noting that there have been attempts to solve the minimum number of
clues problem using mathematics only, i.e., not using a computer. However, nobody has
made any serious progress. In fact, while it is very easy to see that a sudoku puzzle with
seven clues will always have multiple completions, because the two missing digits can be
interchanged in any solution, finding a theoretical reason why eight clues are not enough
for a unique solution already seems hard."
This is reminiscent of the case of the Four Colour Theorem, which was the first notable case of a mathematical proof by computer in 1976. I don't think any progress has been made on just using brain power to prove that either.
"The strategy we used to finally solve this problem is an obvious one — exhaustively
search through all possible solution grids, one by one, for a 16-clue puzzle."
While not a mathematically elegant way of attacking the problem, it looks like the search method they developed and used may have other benefits.
And don't hold out hope for an elegant solution:
"It is worth noting that there have been attempts to solve the minimum number of
clues problem using mathematics only, i.e., not using a computer. However, nobody has
made any serious progress. In fact, while it is very easy to see that a sudoku puzzle with
seven clues will always have multiple completions, because the two missing digits can be
interchanged in any solution, finding a theoretical reason why eight clues are not enough
for a unique solution already seems hard."
This is reminiscent of the case of the Four Colour Theorem, which was the first notable case of a mathematical proof by computer in 1976. I don't think any progress has been made on just using brain power to prove that either.
