zebra Test Program

The Zebra riddle is an instance of so called logic grid puzzles. In these puzzles a given number of individuals hold some distinct properties from some given categories. The problem statements of the puzzle relate the properties of the individuals. The riddle then typically has a single assignment of the properties to the individuals that is consistent with the given problem statements.

In the pure Prolog solution statements about the properties of the individuals are represented as elem/2, rightTo/3 and nextTo/3 goals. The elem/3 predicate is used to express that two different properties are shared by an individual. The righto/3 and nextTo/3 predicate can be used to express a relationship of properties across neighbours. Take for example the following statement from the Zebra riddle:

The Englishman lives in the red house.

This statement is expressed as the following pure Prolog goal:

elem(house(brit,_,_,_,red), Houses)

The CLP(FD) solution takes a little different approach. For each available property of each category a separate variable is used. The individuals are then numbered. The judgement that an individual has a certain property then corresponds to the individual’s number being assigned to the properties’ variable. In the end variable inequalities are used to express the statements of the riddle. For example the statement above from the Zebra riddle is expressed as follows as a CLP(FD) constraint:

Brit #= Red

Both the pure Prolog and the CLP(FD) solution can correctly figure out who owns the fish.

Kommentare