Feynman or not, it's entertaining to anyone who has waded through several hours of contrived interview questions that supposedly relate to programming ability, and that always have a "right" answer.
Coming from an AI background, I coded up an algorithm for state-space search.
They were expecting me to approach it as a person would, reasoning about how you rule out certain numbers (the constraint propagation), which is a second-order consideration for a game the size of sudoku.
I felt pretty smug when Peter Norvig shortly thereafter put up a blog post that essentially mirrored my solution.
If a square has only one possible value, eliminate it from the square's peers.
If a unit has only one possible place for a value, then put the value there.
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.
They were confused when I took a more disciplined approach and provided a solution that is robust to simple CP methods.
For 16x16, it is more of a toss-up if one should use more advanced propagation. The solve-times are still so low though, that it doesn't really matter (tens of milliseconds). For 25x25 it starts to get interesting. In my experience, full propagation on lines, rows, and regions is needed, but more than that slows it down. Without a good heuristic (some learning process, prefferably coupled with randomized restarts), the solve-time easily goes up into hours. Wih a good heuristic, minutes seems to be a reasonable time-span to hope for.
Fortunately, all's well that ends well. An old headhunter I'd used in the past tossed my info along (for FREE!) to my current boss. After talking to me on the phone, he gave me the old "We don't have a position open, but I'll call you if something opens up" line. I wrote it off, but he worked to get a position opened up for me and I'm genuinely doing what I love to do for a living these days. It involves Information Security, physical security/surveillance and general-purpose IT work (Sysadmin, programming and networking). I'm basically in geek heaven. It's also 6 miles from home, giving me the perfect excuse to ride my bike to work every day, rain or shine.