In this blog people are comparing Peter Norvig's solution with Ron Jeffries TDD tries. (read the post, [some] good comments, other links to reddit comments, etc.)
It is a nice problem to chew on, for me, as Unit-Test/TDD agilist: I think that a TDD approach does not lead to discover constraint satisfaction algorithms, it should lead to a clean, testable, SRP driven architecture. If I remember well, the XP books say that you should start with a "metaphor", a design starting point.
disclaimer: this an echo post, i just wanted to link to AIMA.