It can be done with just depth first search, but if you want it to be fast you can go pretty far down the rabbit hole. The details of your representation, your heuristics, and the kinds of constraint propagation you support all matter a lot.

Here's a long walk through these issues in developing a fast solver: https://t-dillon.github.io/tdoku