[Recursing]

Same (not as an interview, as coding challenge), using simple backtracking and a high level language it's really easy. My solution wasn't anywhere near as good as Norvig's, though. (And today I would just use z3)