Log in

No account? Create an account

Journal of No. 118

February 17th, 2012

Minimal Sudoku @ 09:22 am


While 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.
Share  |  Flag |



Journal of No. 118