B u s L o g i c:- prolog, code, chatter.

A solution to Einstien's Riddle

The Einstien's Riddle puzzle is a hard puzzle to solve as a human, but it is essentially a mapping task, so is easy to solve using Prolog. The riddles is defined here: https://udel.edu/~os/riddle.html and this site also includes analysis of how to solve the riddle as well for those that are interested.

Let's look at the prolog implementation. There are many ways to solve this of course, and the trick with Prolog is usually how the data is mapped. Just in case you are wondering, when solving this puzzle I created the mapping first and then the code to use the mapping. The mapping never changed from the start.

If you look at the puzzle rules, there are some patterns. First off there are only a few types of item that need to be considered:

  1. The position of the house.
  2. The colour of the house.
  3. Where the owner is from.
  4. What the owner drinks.
  5. What the owner smokes.
  6. The pet that each house has.

All of these items can be represented using a term. For example with the colour, if the house is blue, this can be represented like so colour(blue). Then you have from(germany), pet(dog) etc..

Next there are some association rules, which help to define which attributes belong together. There are two types of rule:

  1. Rules that apply to the same house (eg: 'the Dane drinks tea').
  2. Rules that apply to adjacent houses (eg: 'the green house is on the left of the white house').

So these two types will be compound terms that map the two rules in the puzzle clue together. Luckily every clue only has two rules.

Using this strategy, all of the rules can be mapped into a list of terms that represent the clues in the puzzle.

    % The Brit lives in the red house.
    same_house_rule(from(britian), colour(red)),

    % The Swede keeps dogs as pets.
    same_house_rule(from(sweden), pet(dogs)),

    % The Dane drinks tea.
    same_house_rule(from(denmark), drinks(tea)),

    % Looking from in front, the green house is just to the left of the white house.
    same_house_rule(colour(green), drinks(coffee)),

    % The green house’s owner drinks coffee.
    next_door_rule(colour(green), colour(white)),

    % The person who smokes Pall Malls raises birds.
    same_house_rule(smokes(pall_mall), pet(birds)),

    % The owner of the yellow house smokes Dunhill.
    same_house_rule(colour(yellow), smokes(dunhill)),

    % The man living in the center house drinks milk.
    same_house_rule(house_no(3), drinks(milk)),

    % The Norwegian lives in the leftmost house.
    same_house_rule(house_no(1), from(norway)),

    % The man who smokes Blends lives next to the one who keeps cats.
    next_door_rule(smokes(blends), pet(cats)),

    % The man who keeps a horse lives next to the man who smokes Dunhill.
    next_door_rule(pet(horse), smokes(dunhill)),

    % The owner who smokes Bluemasters also drinks beer.
    same_house_rule(smokes(bluemasters), drinks(beer)),

    % The German smokes Prince.
    same_house_rule(from(germany), smokes(prince)),

    % The Norwegian lives next to the blue house.
    next_door_rule(from(norway), colour(blue)),

    % The man who smokes Blends has a neighbor who drinks water.
    next_door_rule(smokes(blends), drinks(water))

It is quite a long list, but then there are quite a lot of clues!

The next thing to do is solve the puzzle using these rules. What we are trying to achieve is to create a set of empty houses (full of variables) and then to use the list of rules to fill in the houses in a combination that matches. Prolog backtracking will do most of the work for us.

The first step is to create a set of empty houses:

% house(colour, owner_from, drinks, smokes, pet).

empty_houses(Houses) :-
    length(Houses, 5),
    maplist(house_template, Houses).

After running this, there are five houses, with variables ready to be populated by the rules of the puzzle.

1 ?- empty_houses(H).
H = [
    house(_2484, _2486, _2488, _2490, _2492), 
    house(_2496, _2498, _2500, _2502, _2504), 
    house(_2508, _2510, _2512, _2514, _2516), 
    house(_2520, _2522, _2524, _2526, _2528), 
    house(_2532, _2534, _2536, _2538, _2540)

The solve predicate is dedicated to finding out who has a fish as a pet, and it does this by adding a new rule to the current rules, in which a variable can be used to determine where the owner of the fish is from from(Who) achieves this.

solve_house_puzzle(Who) :-
    maplist(apply_rule(Houses), [same_house_rule(from(Who), pet(fish))|Rules]).

The rest of the code will apply the rules and populates the variables in the houses.

First off apply_prop/3 will allow a single property from a rule to be applied to a house. The rules can be applied to one argument in the house structure and the only type that is a bit different is the house_no/1 type. This property operates over the entire list of houses to pull out one of the houses based on position.

apply_prop(house_no(N), House, Houses) :- nth1(N, Houses, House).
apply_prop(colour(C),   house(C,_,_,_,_), _).
apply_prop(from(F),     house(_,F,_,_,_), _).
apply_prop(drinks(D),   house(_,_,D,_,_), _).
apply_prop(smokes(S),   house(_,_,_,S,_), _).
apply_prop(pet(P),      house(_,_,_,_,P), _).

The same house rules are simple, a house is chosen and then both properties in the rule are applied to that house if possible. Of course, if the house has already been populated by a different value then applying properties will fail and the member(House, Houses) will choose a different house to apply the properties to.

apply_rule(Houses, same_house_rule(A1, A2)) :-
    member(House, Houses),
    apply_prop(A1, House, Houses),
    apply_prop(A2, House, Houses).

The next door rule is a bit different, because houses that are next to each other need to be considered. To do this, the first two houses who are are considered, then the reverse is considered, and then house 2 and 3 etc..

apply_rule(Houses, next_door_rule(N1, N2)) :-
    apply_next_door_rule(Houses, Houses, N1, N2).

apply_next_door_rule([House1, House2|_], Houses, N1, N2) :-
    apply_prop(N1, House1, Houses),
    apply_prop(N2, House2, Houses).
apply_next_door_rule([House1, House2|_], Houses, N1, N2) :-
    apply_prop(N2, House1, Houses),
    apply_prop(N1, House2, Houses).
apply_next_door_rule([_|Rest], Houses, N1, N2) :-
    apply_next_door_rule(Rest, Houses, N1, N2).

And that's it, now when running the solve predicicate the answers appears:

?- solve_house_puzzle(Who).
Who = germany ;
Who = germany ;

there is one interesting thing that comes out of this, is that while the correct answer is generated, there are two solutions, see if you can figure out why this is!