[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.