It might not be that clever, but it is able to considerably reduce the running time of the algorithm (even if the speedup in a 9x9 puzzle is not perceived).

In fact, if you ask people not from a CS background to explain the steps they would take to solve a puzzle, they probably wouldn't be able to think of a DFS, but they would state that they should rule out from each cell the numbers already present in its respective column, line and block. And for a Sudoku solver I don't think you really need more constraint propagation than that.

Anyway, I think you approached the problem the right away, I just think that you were so close to succeed in that test and it wasn't something that difficult to add to your solution.

EDIT: wrote the above before your edit. It's still appropriate though.