The deep nesting and negation of the tests made this look weird to me and harder to see how the main idea was exhaustive searching of all permutations. I think it's clearer when the constraints are separated from the searching:

  People = collections.namedtuple('People', ['Englishman', 'Spaniard', 'Ukrainian', 'Norwegian', 'Japanese'])  # etc.

  def rule_10(people): return people.Norwegian == 0
  def rule_2(people, color): return people.Englishman == color.Red
  def rule_6(color): return color.Ivory - color.Green == 1
  def rule_15(people, color): return abs(people.Norwegian - color.Blue) == 1
  def rule_4(beverage, color): return beverage.Coffee == color.Green
  # etc.

  constraints = [ rule_1, rule_2, ... ]  # etc.

  def inject(func, vars=locals):
      signature = inspect.signature(func)
      args_from = operator.attrgetter(signature.parameters.keys())
      return func(*args_from(vars))

  houses = range(0,5)
  for people in map(People._make, perms(houses)):
    for color in map(Color._make, perms(houses)):
      for beverage in map(Beverage._make, perms(houses)):
        for cigarette in map(Cigarette._make, perms(houses)):
          for pet in map(Pet._make, perms(houses)):
            if all(map(inject, constraints)):
              print(f'The {People._fields[beverage.Water]} drinks water')
              print(f'The {People._fields[pet.Zebra]} owns the zebra')
              sys.exit(0)
  print(f'Sorry, no idea who drinks water or owns a zebra')
  sys.exit(1)

No pruning of the solution space but `all` will exit early if it can. You could change `inject` (terrible name) to pass the list of rules & call those whose signatures are fulfilled at the beginning of each for-loop, and return a list of the uncalled rules + the results of the called rules, and test the results with `all` & keep the uncalled rules handy for the next for-loop. I didn't do it because there's already too much boilerplate in the for-loops