I had to write a sudoku solver in a job interview on a white board. I felt and still feel that it was a bit non-trivial for a job interview question, but nonetheless I arrived at the same answer Peter Norvig did.
Not being sarcastic: The interviewer would explain it to you in 2 minutes (like the article does, including very common strategies), offer you a simple one to sovle and maybe grant you a little more time to come up with an algorithm.
If you don't understand sudoku rules afterwards or cannot implement something according to a set of rules and without previous exposure, than this might be a result the interviewer is interested in as well?
