I received an interesting email today from Gary McGuire containing a paper proving the result that I had long suspected — namely that there is no 16-clue Sudoku puzzle. (See this earlier blog post for some background.)
I have only skimmed the paper so far, but the basic method is clear enough – to examine each of the possible completed grids in turn and exhaustively search the grid to demonstrate that no 16-clue subgrid is uniquely completable. One way of doing this that does not involve actually solving every possible 16-clue subpuzzle is to observe that certain subsets of the cells must necessarily be “hit” by one of the 16 clues or they could simply be rearranged in the final solution. Finding so many subsets of this type that no collection of 16 cells can hit them all is then a (computer) proof that this particular grid contains no 16-clue uniquely completable subgrid.
I’ll add some more details when I have time to read the paper more carefully.
In the meantime, I won’t link to the paper yet, as while it has been uploaded to arxiv, it won’t appear for a couple of days, presumably due to the holiday break.
Congratulations to Gary and his team!
SymOmega 
so, I guess the lower bound is 17 clues? Oh well.
If you want a non-unique solution, then I have created a solver that simply finds any solution, whether unique or not.
http://www.vantasyworld.com/fun/sudoku/sudokusolver.html
BTW: where’s the paper?
The paper has been uploaded to the arxiv at
http://arxiv.org/abs/1201.0749