Hacker News Reader

Comment by supar | Hacker News Reader

"These guys have solved the problem using the tried and trusted mathematical technique of sheer brute force.

In essence these guys have examined every potential 16-clue solution for every possible Sudoku grid."

I was actually hoping for a formal solution or proof here by reading the title.

They did produce a formal solution/proof. The disappointing part is that it contains billions of statements that don't give us any insight about the problem.

I was also hoping to see some mathematical insight that allowed them to prove the minimal sudoku problem. The problem with a brute force solution is that it only applies to the 9x9 sudoku. It would be interesting to see what the limit is for larger sudokus and what correlations there are between their dimensions and their minimal number of clues.

I believe that would have far-reaching implications, seeing that Sudoku has been proven to be an NP-Complete problem.

http://en.wikipedia.org/wiki/List_of_NP-complete_problems#Ga...

Proving something about a NxN grid does not have much to do with a problem being NP-complete.

For example, the fact that it is not very hard to proof that a 1x1 sudoku requires 1 clue does not prove that sudoku is not NP-complete.

Surely a 1x1 grid requires 0 clues?!

A classic off-by-one error. That is not what I was thinking of, though. A 2x2 grid requires a single clue.

A 3x3 grid requires 2 (1 and 2 across a diagonal suffices)

So, we have a sequence 0,1,2,?,?,?,?,?,17,...

I checked the OEIS, but it does not seem to contain this sequence. Does anybody know more values?

It's not really valid to treat this as a sequence, since most side lengths don't form what we think of as a Sudoku puzzle. The side length of a true Sudoku must be a perfect square in order to create the interior boxes that are (geometrical) squares. For the counterexample, think of a 7x7 puzzle (or any prime)... how can a square box contain seven cells?

A 4x4 puzzle gives you four 2x2 boxes. The standard 9x9 puzzle gives nine 3x3 boxes. A 16x16 puzzle gives sixteen 4x4 boxes. Sudoku variations sometimes have rectangular boxes; a 6x6 puzzle can have six 2x3 boxes, or a 12x12 puzzle can have twelve 3x4 boxes. But that is a different form of constraint logic so we shouldn't expect that the minimum number of clues for these sizes would follow a recognizable sequence.

I had to check Wikipedia (which, as we all know, always is right :-)) to see that you are right. I have seen so many variations on sudoku's that I forgot what the original looked like. I was just thinking of Latin squares.

No because then you wouldn't be able to arrive at a fixed solution there would be 9 solutions with 0 clues.

In a 1x1 grid you would only use one digit, not 9. A 1x1 grid requires 0 clues, a 2x2 requires 1 clue.

(tongue in cheek) right, a 1x1 grid requires 0 clues, it has only a single digit as its solution; that digit is -- [its_so_on looks left, cut to SatvikBeri]

That digit is a 1, since for an NxN grid the values are 1 through N.

I'm not sure what the "Rules of Sudoku" say but I assumed any single symbol of the solvers choosing would do.

Reply on news.ycombinator.com