Coincidentally, while trying to get my daughter to sleep last night, I watched her solve a lengthy sudoko on my phone, while my own brain couldn't help to wander to imagining all the possible solver algorithms that might be out there. Or how I'd ever do in a technical interview if anyone asked me design one on the spot.

I got at least as far as thinking through something like your list of algorithms here. But I could help but imaging that there must also be even-more efficient or interestingly exotic solutions out there.

Like something amusing as a rainbow-table type approach where you calculate all the possible soduko boards in advance, then (somehow?) convert any given puzzle into just an index lookup of a matching solution. So like (perhaps a lot of) brute force up front, but O(1) in execution?