On: The Power of Prolog

[philsnow]

Fun problem. My solution doesn't do really any "logic programming", and it takes around 2 minutes to run on my laptop.

https://gist.github.com/philsnow/02e747241d46106b14b60146e58...

The middle huge nested thing (where `some_possible_worlds` is defined) is gross but I'm not great with ruby and I couldn't think of another way to not blow up memory enumerating all the worlds just to eliminate 99% of them.

[carapace → philsnow]

I worked up this from the SEND MORE MONEY example in the CLP(FD) repo.

https://gist.github.com/calroc/603ed919bc814ccee10c1b3df6142...

    There are five houses.
    The Englishman lives in the red house.
    The Spaniard owns the dog.
    Coffee is drunk in the green house.
    The Ukrainian drinks tea.
    The green house is immediately to the right of the ivory house.
    The Old Gold smoker owns snails.
    Kools are smoked in the yellow house.
    Milk is drunk in the middle house.
    The Norwegian lives in the first house.
    The man who smokes Chesterfields lives in the house next to the man with the fox.
    Kools are smoked in the house next to the house where the horse is kept.
    The Lucky Strike smoker drinks orange juice.
    The Japanese smokes Parliaments.
    The Norwegian lives next to the blue house.

Now, who drinks water? Who owns the zebra?

In the interest of clarity, it must be added that each of the five houses is painted a different color, and their inhabitants are of different national extractions, own different pets, drink different beverages and smoke different brands of American cigarets [sic]. One other thing: in statement 6, right means your right.

    :- use_module(library(clpfd)).

    house_next_to(H0, H1) :- abs(H0 - H1) #= 1.

    puzzle([
		GreenHouse, RedHouse, IvoryHouse, YellowHouse, BlueHouse,
		Englishman, Spaniard, Ukrainian, Norwegian, Japanese,
		Dog, Snails, Fox, Horse, Zebra,
		Coffee, Tea, Milk, OrangeJuice, Water,
		OldGold, Kools, Chesterfields, LuckyStrike, Parliaments
		]) :-

		Vars = [GreenHouse, RedHouse, IvoryHouse, YellowHouse, BlueHouse,
			Englishman, Spaniard, Ukrainian, Norwegian, Japanese,
			Dog, Snails, Fox, Horse, Zebra,
			Coffee, Tea, Milk, OrangeJuice, Water,
			OldGold, Kools, Chesterfields, LuckyStrike, Parliaments
		],
		
		Vars ins 1..5,
		
		all_distinct([GreenHouse, RedHouse, IvoryHouse, YellowHouse, BlueHouse]),
		all_distinct([Englishman, Spaniard, Ukrainian, Norwegian, Japanese]),
		all_distinct([Dog, Snails, Fox, Horse, Zebra]),
		all_distinct([Coffee, Tea, Milk, OrangeJuice, Water]),
		all_distinct([OldGold, Kools, Chesterfields, LuckyStrike, Parliaments]),
		
		Englishman #= RedHouse,
		Spaniard #= Dog,
		Coffee #= GreenHouse,
		Ukrainian #= Tea,
		GreenHouse #= 1 + IvoryHouse,
		OldGold #= Snails,
		Kools #= YellowHouse,
		Milk #= 3,
		Norwegian #= 1,
		house_next_to(Chesterfields, Fox),
		house_next_to(Kools, Horse),
		LuckyStrike #= OrangeJuice,
		Japanese #= Parliaments,
		house_next_to(Norwegian, BlueHouse).

Then to print out the solution after loading the program above use:

    puzzle([
		GreenHouse, RedHouse, IvoryHouse, YellowHouse, BlueHouse,
		Englishman, Spaniard, Ukrainian, Norwegian, Japanese,
		Dog, Snails, Fox, Horse, Zebra,
		Coffee, Tea, Milk, OrangeJuice, Water,
		OldGold, Kools, Chesterfields, LuckyStrike, Parliaments]),
	label([
		GreenHouse, RedHouse, IvoryHouse, YellowHouse, BlueHouse,
		Englishman, Spaniard, Ukrainian, Norwegian, Japanese,
		Dog, Snails, Fox, Horse, Zebra,
		Coffee, Tea, Milk, OrangeJuice, Water,
		OldGold, Kools, Chesterfields, LuckyStrike, Parliaments]).

[zmonx → carapace]

That's one of the most elegant Prolog formulations of this task I have seen so far. Great use of CLP(FD), especially considering that you have only started to learn this technology, as you mentioned in the other thread!

I have only two small suggestion: First, since you know that Vars = [GreenHouse, ...] (the Prolog program states this as a constraint), you can simply substitute Vars every time for this list. Therefore, you can start the whole program with: puzzle(Vars) :- ...

Second, exactly the same reasoning applies for the query you show. You can write it as: ?- puzzle(Vs), label(Vs).

Thank you very much for posting this beautiful solution, and also for carefully clarifying the additional assumptions!

[carapace → zmonx]

That's very kind of you. Your comment made my day! :-)

I came to Logic Programming via grokking mrocklin's port of Kanren to Python: https://github.com/logpy/logpy; and to solving logic puzzles via Laws of Form: http://www.markability.net/ (Last year the author of that site George Burnett-Stuart apparently cracked how to encode Predicate Calculus in the notation, which is an exciting development, IMHO!) So I'm not a complete novice. That said, at first I thought I should define relations like smokes and pet_of, but somehow between seeing the table on the Wikipedia entry for the Zebra Puzzle and the SEND MORE MONEY example (https://github.com/triska/clpfd/blob/master/sendmory.pl) it became obvious what to do. If you look at the SEND MORE MONEY solution you'll see the Zebra solution is laid out just like it. To me, it seems like the same sort of puzzle as Sudoku, but much simpler. It's unfortunate that the solution and the solving proper (querying for the result) obscure the art of the puzzle-maker, eh?

Thanks for the suggestion! I've incorporated it into the version in Github "gist": https://gist.github.com/calroc/603ed919bc814ccee10c1b3df6142... (I kept the more verbose query though, as I think the output is nicer. :-) YMMV)

[zmonx → carapace]

Very, very nice formulation!

You can apply the same trick to the query, i.e., you only need to write down the whole list once, if you formulate the query for example like this:

    ?- Vs = [GreenHouse, RedHouse, IvoryHouse, YellowHouse, BlueHouse,
             Englishman, Spaniard, Ukrainian, Norwegian, Japanese,
             Dog, Snails, Fox, Horse, Zebra,
             Coffee, Tea, Milk, OrangeJuice, Water,
             OldGold, Kools, Chesterfields, LuckyStrike, Parliaments],
       puzzle(Vs),
       label(Vs).

In the above, I have introduced the logical variable Vs to refer to the same list in both goals.

In the case of the Zebra puzzle, we only care about a few of these variables in particular, so we do not even introduce names for others. Instead, we can use anonymous variables, so that not even bindings are reported for those variables that do not matter in this case:

    ?- Vs = [_,_,_,_,_,
             Englishman, Spaniard, Ukrainian, Norwegian, Japanese,
             _,_,_,_,Zebra,
             _,_,_,_,Water|_],
       puzzle(Vs),
       label(Vs).

This yields the following solution:

    Vs = [5, 3, 4, 1, 2, 3, 4, 2, 1|...],
    Englishman = 3,
    Spaniard = 4,
    Ukrainian = 2,
    Norwegian = Water, Water = 1,
    Japanese = Zebra, Zebra = 5 .

By introducing additional variables like this, you can use maplist/2 to more compactly express the sequence of all_distinct/1 constraints.

That's really a very nice way to formulate the puzzle in Prolog, and makes excellent use of features that are still quite recent innovations in Prolog implementations.

[carapace → zmonx]

Cheers! That's awesome. I'm going to set aside some time to learn more Prolog. :-)