Zebra Puzzle gets solved in Java

For one of job interview I was asked for Zebra Puzzle solution in Java.
Considering you have input file provided bellow you need to create output xml.
Input:

5
SAME;nationality;English;color;Red
SAME;nationality;Spaniard;pet;Dog
SAME;drink;Coffee;color;Green
SAME;drink;Tea;nationality;Ukrainian
TO_THE_LEFT_OF;color;Green;color;Ivory
SAME;smoke;Old gold;pet;Snails
SAME;smoke;Kools;color;Yellow
SAME;drink;Milk;position;3
SAME;nationality;Norwegian;position;1
NEXT_TO;pet;Fox;smoke;Chesterfields
NEXT_TO;smoke;Kools;pet;Horse
SAME;smoke;Lucky strike;drink;Orange juice
SAME;smoke;Parliaments;nationality;Japanese
NEXT_TO;nationality;Norwegian;color;Blue
SAME;drink;Water
SAME;pet;Zebra

Output:

<solutions>
  <solution>
    <house color="Yellow" drink="Water" nationality="Norwegian" pet="Fox" position="1" smoke="Kools"/>
    <house color="Blue" drink="Tea" nationality="Ukrainian" pet="Horse" position="2" smoke="Chesterfields"/>
    <house color="Red" drink="Milk" nationality="English" pet="Snails" position="3" smoke="Old gold"/>
    <house color="Ivory" drink="Orange juice" nationality="Spaniard" pet="Dog" position="4" smoke="Lucky strike"/>
    <house color="Green" drink="Coffee" nationality="Japanese" pet="Zebra" position="5" smoke="Parliaments"/>
  </solution>
</solutions>

You can download source code and JUnit tests here. Inside that zip you will also find xslt to render xml nice way.

Solution

So, we have to fill [5,6] array. The easiest way would be to check all possible combinations, but that will be slow because there are (5!)^6=2985984000000 combinations. To speedup we prefill array with data we already know is correct: we have all nationalities and additional attribute to them. That will leave us to fill array [5,4] i.e. (5!)^4=207360000. It is already 10000 times less combinations.
Next step is to start guessing values. But not randomly. Lets start from color because it has biggest amounts of clues and because of that some rules will fail immediately and we will not need to go deeper and fill other values. Then - go deeper and take another key with highest amount of clues.
The code provides solution in 90-1460 iterations.