Thursday, February 4, 2016

The zebra puzzle

The Zebra Puzzle is a well-known logic puzzle that can be fun to solve if you are bored.
Try below your logic skills in the interactive version I made. Your objective is to get all the conditions true (green). To change the order of elements just click in the ones to swap consecutively.

If you find yourself struggling or you want an elaborated explanation of how to solve it you can find it here.

Of course this little problem is ripe to be solved with a little help of code, but the naive brute force implementation would take some time to finish; there are (5!)^5 possibilities after all, that is: 24883200000 possible arrangements that we'll need to check.
Here you can find a brute force solution using Web workers, just don't hold your breath.

Some kind of optimizations would be needed to solve this fast. I was planning to post here my crappy constrained generator code until I found this amazing post of some guy that created a whole working online Prolog interpreter to solve this kind of problems. So you better continue there.

Prolog is "the language" to solve these type of problems, here is my solution in case you are wondering:

Just ask for: "puzzle(Houses)" in the online interpreter.

No comments:

Post a Comment