More logical programming in Ruby: solving Einstein's riddle (Zebra puzzle)

The Zebra puzzle is a well-known logic puzzle often attributed to Albert Einstein, who is said to have invented it as a boy. The legend goes that he claimed that "only 2% of the world's population can solve this".

Here's how to solve it without leaving Ruby with this tiny Prolog interpreter*1. There are a few variants of the riddle; the code below solves this one (based on the code left by an anonymous reader Gordon in a comment on that page, with little modifications to make it work):

require 'tiny_prolog_ext'

def _
  (@anonymous_var = (@anonymous_var ||= "S_00000").succ).intern
end

member[:Z, cons(_,:L)] <<= member[:Z, :L]
member[:Z, cons(:Z,_)].fact

#query member[:X, list(1,2,3,4,5)]

next_to[:X, :Y, :List] <<= iright[:X, :Y, :List]
next_to[:X, :Y, :List] <<= iright[:Y, :X, :List]

iright[:L, :R, cons(:L, cons(:R , _ ))].fact
iright[:L, :R, cons(_ , :Rest)] <<= iright[:L, :R, :Rest]
einstein[:Houses, :Fish_Owner] <<= [ 
    eq[:Houses, list(list('house', 'norwegian', _, _, _, _), _, list('house', _, _, _, 'milk', _), _, _)],
    member[list('house', 'brit', _, _, _, 'red'), :Houses],
    member[list('house', 'swede', 'dog', _, _, _), :Houses],
    member[list('house', 'dane', _, _, 'tea', _), :Houses],
    iright[list('house', _, _, _, _, 'green'), list('house', _, _, _, _, 'white'), :Houses],
    member[list('house', _, _, _, 'coffee', 'green'), :Houses],
    member[list('house', _, 'bird', 'pallmall', _, _), :Houses],
    member[list('house', _, _, 'dunhill', _, 'yellow'), :Houses],
    next_to[list('house', _, _, 'dunhill', _, _), list('house', _, 'horse', _, _, _), :Houses],
    member[list('house', _, _, _, 'milk', _), :Houses],
    next_to[list('house', _, _, 'marlboro', _, _), list('house', _, 'cat', _, _, _), :Houses],
    next_to[list('house', _, _, 'marlboro', _, _), list('house', _, _, _, 'water', _), :Houses],
    member[list('house', _, _, 'winfield', 'beer', _), :Houses],
    member[list('house', 'german', _, 'rothmans', _, _), :Houses],
    next_to[list('house', 'norwegian', _, _, _, _), list('house', _, _, _, _, 'blue'), :Houses],
    member[list('house', :Fish_Owner, 'fish', _, _, _), :Houses]
  ]

query einstein[:Houses, :Fish_Owner]

If you run it, you'll get as expected:

$ ruby einstein.rb 
1 einstein[(("house" "norwegian" "cat" "dunhill" "water" "yellow") 
            ("house" "dane" "horse" "marlboro" "tea" "blue") 
	    ("house" "brit" "bird" "pallmall" "milk" "red") 
	    ("house" "german" "fish" "rothmans" "coffee" "green") 
	    ("house" "swede" "dog" "winfield" "beer" "white")), "german"]

(slightly reformatted for clarity)

Yes, it's fairly slow, but still interesting.

No Title - Gordon Thiesfeld (2007-02-24 (Sat) 18:12:00)

Wow! I wasn't really expecting a reply, let alone such a fast one. This does run slower (~ 1 minute on my laptop) than in swi-prolog (~2 seconds), but it is lightyears faster than anything I've come up with so far (~ never finished) :)

mfp 2007-02-25 (Sun) 11:47:21

I happened to see your comment when I needed a mental break :)

Actually, I'd have expected the performance to be worse... 1/30x against a specialized interpreter is not bad at all for a very simple, unoptimized Ruby implementation...

lv 2007-02-25 (Sun) 17:29:54

I use "zebra" to roughly gauge how fast a language is. Swi runs zebra in 90 milliseconds on my computer.

mfp 2007-02-26 (Mon) 03:28:10

I'm getting 70ms w/ swi-prolog vs. ~25s with the Ruby interpreter, 350x slower. That's more in line with my expectations.