[Someone]

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.

[pbhjpbhj]

Surely a 1x1 grid requires 0 clues?!

[Someone]

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?

[T-hawk]

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.

[Someone]

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.

[ohgodthecat]

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

[SatvikBeri]

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

[its_so_on]

(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]

[cperciva]

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

[pbhjpbhj]

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