No. 118 (essentialsaltes) wrote,
No. 118

Minimal Sudoku

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.
Tags: math

  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded