I got hit by an interesting problem of “Zebra Puzzle” the other day. It is a well known logic puzzle believed to be first invented by Albert Einstein.
The question here is, how do we use our favorite programming language to solve this problem?
Wikipedia suggests the following algorithm for generating all permutation systematically.
The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place.
- Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
- Find the largest index l such that a[k] < a[l]. Since k + 1 is such an index, l is well defined and satisfies k < l.
- Swap a[k] with a[l].
- Reverse the sequence from a[k + 1] up to and including the final element a[n].
I have put the working example on http://www.solidskill.net/ZebraPuzzle.htm. There are other parts of code that search through the solution space, setup the constraints for Zebra puzzle. But they are not discussed here.
There are some things to note about this implementation though. First, it is not very efficient. You can see in the getNextSequence(..) loop that there are loops used to search for k and l that satisfy the conditions.
Hope this helps those who are looking for permutation generation code.