output

% /usr/bin/time ./zebra.rb
[[{:country=>:norway,
   :drink=>:no_drink,
   :color=>:yellow,
   :pet=>:fox,
   :smoke=>:kool,
   :pos=>1},
  {:country=>:ukraine,
   :drink=>:tea,
   :color=>:blue,
   :pet=>:horse,
   :smoke=>:chesterfield,
   :pos=>2},
  {:country=>:england,
   :drink=>:milk,
   :color=>:red,
   :pet=>:snail,
   :smoke=>:oldgold,
   :pos=>3},
  {:country=>:spain,
   :drink=>:oj,
   :color=>:ivory,
   :pet=>:dog,
   :smoke=>:luckystrike,
   :pos=>4},
  {:country=>:japan,
   :drink=>:coffee,
   :color=>:green,
   :pet=>:no_pet,
   :smoke=>:parliament,
   :pos=>5}]]
      108.70 real       100.79 user         1.88 sys

zebra.rb

#!/usr/bin/env ruby

def all_combinations
  countries = [:england, :spain, :ukraine, :japan, :norway]
  drinks = [:coffee, :tea, :milk, :oj, :no_drink]
  colors = [:red, :green, :yellow, :ivory, :blue]
  pets = [:dog, :snail, :fox, :horse, :no_pet]
  smokes = [:oldgold, :kool, :chesterfield, :luckystrike, :parliament]

  ([1,2,3,4,5].product(countries, drinks, colors, pets, smokes)).inject([]) do |res, item|
    res << {pos: item[0], country: item[1], drink: item[2], color: item[3], pet: item[4], smoke: item[5]}
    res
  end
end

all_possible_houses = all_combinations.
      reject { |item| ((item[:pos] == 3)              ^ (item[:drink] == :milk)) }.
      reject { |item| ((item[:country] == :england)   ^ (item[:color] == :red)) }.
      reject { |item| ((item[:country] == :spain)     ^ (item[:pet] == :dog)) }.
      reject { |item| ((item[:drink] == :coffee)      ^ (item[:color] == :green)) }.
      reject { |item| ((item[:country] == :ukraine)   ^ (item[:drink] == :tea)) }.
      reject { |item| ((item[:smoke] == :oldgold)     ^ (item[:pet] == :snail)) }.
      reject { |item| ((item[:color] == :yellow)      ^ (item[:smoke] == :kool)) }.
      reject { |item| ((item[:country] == :norway)    ^ (item[:pos] == 1)) }.
      reject { |item| ((item[:smoke] == :luckystrike) ^ (item[:drink] == :oj)) }.
      reject { |item| ((item[:country] == :japan)     ^ (item[:smoke] == :parliament)) }.
      # optimization: we know if ivory < green, ivory can't be house
      # #5, so discard all houses that have color ivory and position 5
      reject { |item| ((item[:pos] == 5)             && (item[:color] == :ivory)) }

possible_houses = all_possible_houses.inject([]) do |l, item|
  l[item[:pos]] = [] if l[item[:pos]].nil?
  l[item[:pos]] << item.reject { |k, v| k == :pos }
  l
end

require 'set'
some_possible_worlds = []
0.upto(possible_houses[1].length - 1) do |i|
  0.upto(possible_houses[2].length - 1) do |j|
    0.upto(possible_houses[3].length - 1) do |k|
      0.upto(possible_houses[4].length - 1) do |l|
        0.upto(possible_houses[5].length - 1) do |m|
          houses = [possible_houses[1][i],
                    possible_houses[2][j],
                    possible_houses[3][k],
                    possible_houses[4][l],
                    possible_houses[5][m]].
                   map.with_index { |h, i| h.merge(pos: i+1) }
          if [:country, :drink, :color, :pet, :smoke].all? do |k|
               s = Set.new
               houses.each do |house|
                 s.add(house[k])
               end
               s.length == 5
             end
            some_possible_worlds << houses
          end
        end
      end
    end
  end
end
          
def pos(houses, prop, val)
  houses.find { |h| h[prop] == val }[:pos]
end
def next_to(v1, v2)
  v1 == v2 + 1 || v1 == v2 - 1
end

matching_worlds = some_possible_worlds.
                  select { |houses| pos(houses, :color, :ivory) + 1 == pos(houses, :color, :green) }.
                  select { |houses| next_to(pos(houses, :smoke, :chesterfield), pos(houses, :pet, :fox)) }.
                  select { |houses| next_to(pos(houses, :smoke, :kool), pos(houses, :pet, :horse)) }.
                  select { |houses| next_to(pos(houses, :country, :norway), pos(houses, :color, :blue)) }

require 'pp'
pp matching_worlds