Search code examples
prologzebra-puzzle

Filling a table in Prolog, given specific clues (Einstein riddle)

There is a hypothetical table of five offices. Each office has a color, a department, a pc, a drink, a cellphone and a specific position from 1 to 5:

The table is here

I am trying to give the following clues to Prolog, so that it can fill the table correctly:

  1. the man drinking milk is in office #3.
  2. the man working in public relations ('pubrel') department is in office #1.
  3. the man from public relations department is next to the blue office.
  4. the green office is on the right of the pink office.
  5. the man in green office is drinking coffee.
  6. the man in the yellow office has a blackberry cellphone, the yellow office is next to the office of the man who has a windows7 pc.
  7. the man working in the red office is from 'cs' department.
  8. the man from 'ode' department has mac_pro pc.
  9. the man from finance ('fin') department is drinking tea.
  10. the man who has an iphone also has a mac_air pc.
  11. the man with a nokia cellphone is next to the man who has a netbook pc.
  12. the man who has an android phone is drinking orange juice.
  13. the man from supplies department has an ericsson phone.

I'm using 

of(X,Y)

where X is an attribute of an office and Y is the position of said office. For example:

of(color(yellow),1) -->office with yellow color is office #1
of(dept(cs),3) -->employee from cs department is in office #3

I define those clues as 'rules', that are all supposed to work at the same time.

rule1:-of(drink(milk),3),perm(drink(milk),3).
rule2:-of(dept(relations),1),perm(dept(relations),1).
rule3:-of(dept(relations),1),of(color(blue),2),perm(dept(relations),1),perm(color(blue),2).
rule3:-of(dept(relations),2),of(color(blue),3),perm(dept(relations),2),perm(color(blue),3).
rule3:-of(dept(relations),3),of(color(blue),4),perm(dept(relations),3),perm(color(blue),4).
rule3:-of(dept(relations),4),of(color(blue),5),perm(dept(relations),4),perm(color(blue),5).
rule4:-of(color(pink),1),of(color(green),2),perm(color(pink),1),perm(color(green),2).
rule4:-of(color(pink),2),of(color(green),3),perm(color(pink),2),perm(color(green),3).
rule4:-of(color(pink),3),of(color(green),4),perm(color(pink),3),perm(color(green),4).
rule4:-of(color(pink),4),of(color(green),5),perm(color(pink),4),perm(color(green),5).
rule5:-of(color(green),1),of(drink(coffee),1),perm(color(green),1),perm(drink(coffee),1).
rule5:-of(color(green),2),of(drink(coffee),2),perm(color(green),2),perm(drink(coffee),2).
rule5:-of(color(green),3),of(drink(coffee),3),perm(color(green),3),perm(drink(coffee),3).
rule5:-of(color(green),4),of(drink(coffee),4),perm(color(green),4),perm(drink(coffee),4).
rule5:-of(color(green),5),of(drink(coffee),5),perm(color(green),5),perm(drink(coffee),5).
rule6:-of(cell(blackberry),1),of(color(yellow),1),of(pc(win7),2),perm(cell(blackberry),1),perm(color(yellow),1),perm(pc(win7),2).
rule6:-of(cell(blackberry),2),of(color(yellow),2),of(pc(win7),3),perm(cell(blackberry),2),perm(color(yellow),2),perm(pc(win7),3).
rule6:-of(cell(blackberry),3),of(color(yellow),3),of(pc(win7),4),perm(cell(blackberry),3),perm(color(yellow),3),perm(pc(win7),4).
rule6:-of(cell(blackberry),4),of(color(yellow),4),of(pc(win7),5),perm(cell(blackberry),4),perm(color(yellow),4),perm(pc(win7),5).
rule6:-of(cell(blackberry),2),of(color(yellow),2),of(pc(win7),1),perm(cell(blackberry),2),perm(color(yellow),2),perm(pc(win7),1).
rule6:-of(cell(blackberry),3),of(color(yellow),3),of(pc(win7),2),perm(cell(blackberry),3),perm(color(yellow),3),perm(pc(win7),2).
rule6:-of(cell(blackberry),4),of(color(yellow),4),of(pc(win7),3),perm(cell(blackberry),4),perm(color(yellow),4),perm(pc(win7),3).
rule6:-of(cell(blackberry),5),of(color(yellow),5),of(pc(win7),4),perm(cell(blackberry),5),perm(color(yellow),5),perm(pc(win7),4).
rule7:-of(dept(cs),1),of(color(red),1),perm(dept(cs),1),perm(color(red),1).
rule7:-of(dept(cs),2),of(color(red),2),perm(dept(cs),2),perm(color(red),2).
rule7:-of(dept(cs),3),of(color(red),3),perm(dept(cs),3),perm(color(red),3).
rule7:-of(dept(cs),4),of(color(red),4),perm(dept(cs),4),perm(color(red),4).
rule7:-of(dept(cs),5),of(color(red),5),perm(dept(cs),5),perm(color(red),5).
rule8:-of(dept(ode),1),of(pc(mac_pro),1),perm(dept(ode),1),perm(pc(mac_pro),1).
rule8:-of(dept(ode),2),of(pc(mac_pro),2),perm(dept(ode),2),perm(pc(mac_pro),2).
rule8:-of(dept(ode),3),of(pc(mac_pro),3),perm(dept(ode),3),perm(pc(mac_pro),3).
rule8:-of(dept(ode),4),of(pc(mac_pro),4),perm(dept(ode),4),perm(pc(mac_pro),4).
rule8:-of(dept(ode),5),of(pc(mac_pro),5),perm(dept(ode),5),perm(pc(mac_pro),5).
rule9:-of(dept(fin),1),of(drink(tea),1),perm(dept(fin),1),perm(drink(tea),1).
rule9:-of(dept(fin),2),of(drink(tea),2),perm(dept(fin),2),perm(drink(tea),2).
rule9:-of(dept(fin),3),of(drink(tea),3),perm(dept(fin),3),perm(drink(tea),3).
rule9:-of(dept(fin),4),of(drink(tea),4),perm(dept(fin),4),perm(drink(tea),4).
rule9:-of(dept(fin),5),of(drink(tea),5),perm(dept(fin),5),perm(drink(tea),5).
rule10:-of(cell(iphone),1),of(pc(mac_air),1),perm(cell(iphone),1),perm(pc(mac_air),1).
rule10:-of(cell(iphone),2),of(pc(mac_air),2),perm(cell(iphone),2),perm(pc(mac_air),2).
rule10:-of(cell(iphone),3),of(pc(mac_air),3),perm(cell(iphone),3),perm(pc(mac_air),3).
rule10:-of(cell(iphone),4),of(pc(mac_air),4),perm(cell(iphone),4),perm(pc(mac_air),4).
rule10:-of(cell(iphone),5),of(pc(mac_air),5),perm(cell(iphone),5),perm(pc(mac_air),5).
rule11:-of(cell(nokia),1),of(pc(netbook),2),perm(cell(nokia),1),perm(pc(netbook),2).
rule11:-of(cell(nokia),2),of(pc(netbook),3),perm(cell(nokia),2),perm(pc(netbook),3).
rule11:-of(cell(nokia),3),of(pc(netbook),4),perm(cell(nokia),3),perm(pc(netbook),4).
rule11:-of(cell(nokia),4),of(pc(netbook),5),perm(cell(nokia),4),perm(pc(netbook),5).
rule11:-of(cell(nokia),2),of(pc(netbook),1),perm(cell(nokia),2),perm(pc(netbook),1).
rule11:-of(cell(nokia),3),of(pc(netbook),2),perm(cell(nokia),3),perm(pc(netbook),2).
rule11:-of(cell(nokia),4),of(pc(netbook),3),perm(cell(nokia),4),perm(pc(netbook),3).
rule11:-of(cell(nokia),5),of(pc(netbook),4),perm(cell(nokia),5),perm(pc(netbook),4).
rule12:-of(cell(android),1),of(drink(orangejuice),1),perm(cell(android),1),perm(drink(orangejuice),1).
rule12:-of(cell(android),2),of(drink(orangejuice),2),perm(cell(android),2),perm(drink(orangejuice),2).
rule12:-of(cell(android),3),of(drink(orangejuice),3),perm(cell(android),3),perm(drink(orangejuice),3).
rule12:-of(cell(android),4),of(drink(orangejuice),4),perm(cell(android),4),perm(drink(orangejuice),4).
rule12:-of(cell(android),5),of(drink(orangejuice),5),perm(cell(android),5),perm(drink(orangejuice),5).
rule13:-of(dept(supplies),1),of(cell(ericsson),1),perm(dept(supplies),1),perm(cell(ericsson),1).
rule13:-of(dept(supplies),2),of(cell(ericsson),2),perm(dept(supplies),2),perm(cell(ericsson),2).
rule13:-of(dept(supplies),3),of(cell(ericsson),3),perm(dept(supplies),3),perm(cell(ericsson),3).
rule13:-of(dept(supplies),4),of(cell(ericsson),4),perm(dept(supplies),4),perm(cell(ericsson),4).
rule13:-of(dept(supplies),5),of(cell(ericsson),5),perm(dept(supplies),5),perm(cell(ericsson),5).

and then feed them all to a predicate 'office' that is supposed to be true if they can all apply together, so that the table is formed correctly.

office:-rule1,rule2,rule3,rule4...

I define perm(X,Y) as a term that becomes true when the attribute X is allowed to capture the specific spot Y, meaning that X has not captured another one and is therefore permitted.

perm(X,1):-not(of(X,2)),not(of(X,3)),not(of(X,4)),not(of(X,5)).
perm(X,2):-not(of(X,1)),not(of(X,3)),not(of(X,4)),not(of(X,5)).
perm(X,3):-....

And finally, of(X,Y) is supposed to become true if the spot Y is not already taken by another X. For example, of(color(red),3) is supposed to be true if no other color has captured spot 3.

of(color(red),Y):-not(of(color(green),Y)),not(of(color(pink),Y)),
        not(of(color(blue),Y)),not(of(color(yellow),Y)).
of(color(green),Y):-not(of(color(red),Y)),not(of(color(pink),Y)),
        not(of(color(blue),Y)),not(of(color(yellow),Y)).
...
of(dept(cs),Y):-not(of(dept(ode),Y)),not(of(dept(supplies),Y)),
        not(of(dept(fin),Y)),not(of(dept(relations),Y)).
of(dept(ode),Y):-not(of(dept(cs),Y)),not(of(dept(supplies),Y)),
        not(of(dept(fin),Y)),not(of(dept(relations),Y)).
...

So, perm(X,Y) and of(X,Y) are supposed to be true at the same time in each rule.

And it's not working, probably because it does have anything concrete to start with. It does not know when

not(of(color(green),1))

will be true. But I'm stuck and can't think of a way to define something specific to start with. Can anyone help on how to make it work?

Solution

  • Your approach won't ever work, because it has unbounded recursion built-in. Its logic is circular. It never stops. Limiting ourselves to only two colors, you definitions are

    of(color(red),Y):- not(of(color(green),Y)).
of(color(green),Y):- not(of(color(red),Y)).

    You only ever build your knowledge in the negative. You should hold a positive knowledge somewhere, in some fashion: "the office 1 is pink", not "the office 1 is not green nor yellow etc". (1)

    You only have five colors at your disposal; if it's none of the four, it is by necessity the fifth.

    perm seems thus completely superfluous. If you now get back from your predicate the positive knowledge about an office's color, then if it's red, it's red.

    And "next-to" means, (e.g. for "the man from public relations department is next to the blue office."),

    of(dept(pubrel),X), of(color(blue),Y),
of(position(I),X), of(position(J),Y), 1 is abs (I-J).

    of should be coded so that it records the knowledge somehow. There's plenty examples in the linked answers or under the tag on how to achieve that.

    (1) (update:) on the other hand, you could write

        of(Rec1,color(not_green_nor_yellow),Y,RecN):- 
        not_of(Rec1,color(green),Y,Rec2),
        not_of(Rec2,color(yellow),Y,RecN).

    the idea is to start with full possibilities recorded, and then have them actually removed one by one from that record (by not_of/4 predicate) until there is strictly one possibility left (like Sudoku). Maybe this is what you had in mind. You'd still maintain your positive knowledge (even while expressing it negatively), which is a list of all currently possible choices for each office.

    So under one paradigm we add choices (so adding both yellow and green color to same office is a contradiction - an office can only have one color), and under the other we remove them (removing both yellow and green is perfectly fine unless this empties the list of the remaining choices for that office - an office must have some color, one color).