AI实践-Zebra Problem

Kanren

kanren是一个Python中的逻辑编程库，用于自动化推理和约束求解。
它允许用户使用关系和规则来表示问题，并使用不同的搜索算法来查找满足约束条件的解决方案。

from kanren import run, eq, membero, var, conde

x = var()
run(1,x, eq(x,5))

(5,)

具体解释如下：

• var()函数创建一个新的逻辑变量，它可以表示任何可能的值。
• eq(x, 5)表示x等于5的关系约束。
• run(1, x, eq(x, 5))表示运行一个查询，寻找一个满足关系约束eq(x, 5)的x值，并返回一个长度为1的列表，其中包含这个x值。

z = var()
run(1, x, eq(x,z), eq(z,3))

(3,)

前面的例子中使用的 eq，表述的是两个表达式相等。membero(item, coll) 表示 item 是 coll集合中的一个成员。下面例子使用 两次 membero去请求 x 的2个值，

run(2, x, membero(x, (1, 2, 3)),  # x is a member of (1, 2, 3) 
              membero(x, (2, 3, 4)))  # x is a member of (2, 3, 4)

(2, 3)

逻辑变量

下面例子中，z = var() 创建一个逻辑变量. 您还可以选择为变量命名，以方便后面调试：

# 一个变量
z = var('test')
z

~test

知识表达

下面代码创建一个亲缘关系，并且使用它来判断谁是 Simpsons家庭的父亲。

from kanren import Relation, facts
parent = Relation()
facts(parent, ('Allen', 'Bart'),
      ('Allen', 'Lisa'),
      ('Abe', 'Allen'))

run(1, x, parent(x, 'Bart'))

('Allen',)

run(2, x, parent('Allen', x))

('Bart', 'Lisa')

y = var()
run(1, x, parent(x, y),
                   parent(y, 'Bart'))

('Abe',)

另一种实现：

def grandparent(x,z):
    y = var()
    return conde((parent(x, y), parent(y, z)))

run(1, x, grandparent(x, 'Bart'))

('Abe',)

conde() 是Scheme中实现的Kanren库提供的特定操作符，它用于将多个条件组合成一个联合条件，并支持回溯和搜索。

斑马问题

题目描述

斑马问题： 5 个不同国家（英国、西班牙、日本、意大利、挪威）且工作各不相同（油漆工、摄影师、外交官、小提琴家、医生）的人分别住在一条街上的 5 所房子里，
每所房子的颜色不同（红色、白色、蓝色、黄色、绿色），每个人都有自己养的不同宠物（狗、蜗牛、斑马、马、狐狸），喜欢喝不同的饮料（矿泉水、牛奶、茶、橘子汁、咖啡）。
根据以下提示，你能告诉我哪所房子里的人养斑马，哪所房子里的人喜欢喝矿泉水吗？

1. 英国人住在红色的房子里
2. 西班牙人养了一条狗
3. 日本人是一个油漆工
4. 意大利人喜欢喝茶
5. 挪威人住在左边的第一个房子里
6. 绿房子在白房子的右边
7. 摄影师养了一只蜗牛
8. 外交官住在黄房子里
9. 中间那个房子的人喜欢喝牛奶
10. 喜欢喝咖啡的人住在绿房子里
11. 挪威人住在蓝色的房子旁边
12. 小提琴家喜欢喝橘子汁
13. 养狐狸的人所住的房子与医生的房子相邻
14. 养马的人所住的房子与外交官的房子相邻

求解问题

from kanren import *
from kanren.core import lall
import time

定义函数left() 和 next() 来查找哪个房屋的左边或者接近谁的房子

def left(q, p, list):
    return membero((q,p), zip(list, list[1:]))
def next(q, p, list):
    return conde([left(q, p, list)], [left(p, q, list)])

houses = var()

# my lall: county, job, drink, pet, color 
rules_zebraproblem = lall(
    (eq, (var(), var(), var(), var(), var()), houses),
    (membero,('Englishman', var(), var(), var(), 'red'), houses),
    (membero,('Spanish', var(), var(), 'dog', var()), houses),
    (membero,('Japanese', 'painters', var(), var(), var()), houses),
    (membero,('Italian', var(), 'tea', var(), var()), houses),
    (eq,(('Norwegian', var(), var(), var(), var()), var(), var(), var(), var()), houses),
    (left,(var(), var(), var(), var(), 'white'),
    (var(), var(), var(), var(), 'green'), houses),
    (membero,(var(), 'photographer', var(), 'snail', var()), houses),
    (membero,(var(), 'diplomat', var(), var(), 'yellow'), houses),
    (eq,(var(), var(), (var(), var(), 'milk', var(), var()), var(), var()), houses),
    (membero,(var(), var(), 'coffee', var(),'green'), houses),
    (next,('Norwegian', var(), var(), var(), var()),
    (var(), var(), var(), var(), 'blue'), houses),
    (membero,(var(), 'violinist','orange juice', var(), var()), houses),
    (next,(var(), var(), var(), 'fox', var()),
    (var(), 'doctor', var(), var(), var()), houses),
    (next,(var(), var(), var(), 'horse', var()),
    (var(), 'diplomat', var(), var(), var()), houses),
    (membero,(var(), var(), var(), 'zebra', var()), houses),
    (membero,(var(), var(), 'mineral water', var(), var()), houses),
)

完整推理结果：

solutions = run(0, houses, rules_zebraproblem)
solutions 

((('Norwegian', 'diplomat', 'mineral water', 'fox', 'yellow'),
  ('Italian', 'doctor', 'tea', 'horse', 'blue'),
  ('Englishman', 'photographer', 'milk', 'snail', 'red'),
  ('Spanish', 'violinist', 'orange juice', 'dog', 'white'),
  ('Japanese', 'painters', 'coffee', 'zebra', 'green')),)

problem A. 哪所房子里的人养斑马:

output_zebra = [house for house in solutions[0] if 'zebra' in house][0][0]
print ('\n'+ output_zebra + ' owns zebra.')

Japanese owns zebra.

problem B. 哪所房子里的人喜欢喝矿泉水

output_mineralWater = [house for house in solutions[0] if 'mineral water' in house][0][0]
print ('\n'+ output_mineralWater + ' likes mineral water.')

Norwegian likes mineral water.

Solution two :

"""
Zebra puzzle as published in Life International in 1962.
https://en.wikipedia.org/wiki/Zebra_Puzzle
"""
from dataclasses import dataclass, field
from typing import Union
from unification import Var, unifiable, var, vars
from kanren import conde, eq, lall, membero, run

@unifiable
@dataclass
# class House:
#     nationality: Union[str, Var] = field(default_factory=var)
#     drink: Union[str, Var] = field(default_factory=var)
#     animal: Union[str, Var] = field(default_factory=var)
#     cigarettes: Union[str, Var] = field(default_factory=var)
#     color: Union[str, Var] = field(default_factory=var)

class House:
    nationality: Union[str, Var] = field(default_factory=var)
    job: Union[str, Var] = field(default_factory=var)
    drink: Union[str, Var] = field(default_factory=var)
    animal: Union[str, Var] = field(default_factory=var)
    color: Union[str, Var] = field(default_factory=var)

def righto(right, left, houses):
    """Express that `right` is on the right of `left` among all the houses."""
    neighbors = tuple(zip(houses[:-1], houses[1:]))
    return membero((left, right), neighbors)

def nexto(a, b, houses):
    """Express that `a` and `b` are next to each other."""
    return conde([righto(a, b, houses)], [righto(b, a, houses)])


# And now for the riddle
houses = vars(5)

goals = lall(
    membero(House("Englishman", color="red"), houses),
    membero(House("Spanish", animal="dog"), houses),
    membero(House("Japanese", job="painters"), houses),
    membero(House("Italian", drink="tea"), houses),
    eq(House("Norwegian"), houses[0]),
    righto(House(color="green"), House(color="white"), houses),
    membero(House(job="photographer", animal="snail"), houses),
    membero(House(job="diplomat", color="yellow"), houses),
    eq(House(drink="milk"), houses[2]),
    membero(House(drink="coffee", color="green"), houses),
    nexto(House("Norwegian"), House(color="blue"), houses),
    membero(House(job="violinist", drink="orange juice"), houses),
    nexto(House(job="doctor"), House(animal="fox"), houses),
    nexto(House(job="diplomat"), House(animal="horse"), houses),
    membero(House(drink="mineral water"), houses),
    membero(House(animal="zebra"), houses),
)

results = run(0, houses, goals)
print(results)

([House(nationality='Norwegian', job='diplomat', drink='mineral water', animal='fox', color='yellow'), House(nationality='Italian', job='doctor', drink='tea', animal='horse', color='blue'), House(nationality='Englishman', job='photographer', drink='milk', animal='snail', color='red'), House(nationality='Spanish', job='violinist', drink='orange juice', animal='dog', color='white'), House(nationality='Japanese', job='painters', drink='coffee', animal='zebra', color='green')],)

Reference ：

• python逻辑编程之kanren(博客园)
• pythological/kanren(github)
• kanren 0.2.3 Project description