[yifanl]

To me it seems like it comes from experience solving sudokus. If you've ever tried it (or watch Cracking the Cryptic if you haven't), you don't store just the solution of each square, you keep track of what you've ensured cannot be in this square.

From that mental model, the choice of data structure would seem to follow directly, which would tie nicely with the subthesis of programming within your genre.

[zellyn]

I dunno. When I first read Norvig's beautiful solution, I immediately thought, "Only someone coming from a Lisp and (old school) AI background (or maybe a super-Mathy background where everything is a Set) would have picked that representation, but oh man does it work so, so well."