Clingo:断言部分约束 [英] Clingo: assert partial constraints

问题描述

我正在尝试在clingo中实现一个程序，该程序可以解决那些经典的谜语之一，在该谜题中，您具有一系列事实和约束的断言，而您必须推论其他事实.问题出在这里:

I am trying to implement a program in clingo that solves one of those classic riddles where you have a series of assertions of facts and constraints and you have to deduce other facts. Here goes the problem:

五名不同国籍的人住在五座并排的房屋中，每座房屋的颜色各不相同；他们都有不同的工作，不同的喜爱的动物和喜爱的饮料.我们知道:

Five men of different nationalities live in five side-by-side houses, each of a different color; they all have different jobs, a different favourite animal and favourite beverages. We know that:

1. 英国人住在红房子里.
2. 西班牙人最喜欢的动物是狗.
3. 日本男人是画家.
4. 意大利男人喝茶.
5. 这名挪威男子住在左边的第一所房子里. (number_norw = 1)
6. 住在温室里的人喝咖啡.
7. 温室恰好在白色的右边. (数字绿色=数字白色+ 1)
8. 店员爱猫.
9. 推销员住在黄色的房子里.
10. 牛奶是中心房屋中最喜欢的饮料. (number_milk = 3)
11. 挪威人的房子与蓝色的房子相邻. (number_norw = number_blue±1)
12. 厨师喜欢果汁.
13. 住在医生爱人旁边的房子里的人是狐狸.
14. 爱马的男人住在推销员的隔壁.

1. The English man lives in the red house.
2. The Spanish man's favourite animal is the dog.
3. The Japanese man is a painter.
4. The Italian man drinks tea.
5. The Norwegian man lives in the first house from the left. (number_norw = 1)
6. The person living in the green house drinks coffee.
7. The green house is immediately right of the white one. (number_green = number_white + 1)
8. The clerk loves cats.
9. The salesman lives in the yellow house.
10. Milk is the favourite drink in the center house. (number_milk = 3)
11. The Norwegian's house is adjacent to the blue one. (number_norw = number_blue ± 1)
12. The cook likes juice.
13. The man living in the house next to the doctor's loves foxes.
14. The man who loves horses lives next door to the salesman.

任务是找出谁喜欢斑马. 所以我提出断言:

The assignment is to find out who likes zebras. So I set forth asserting:

% Number (the number of the house, 1 being the leftmost of the block, 5 the rightmost)
number(1..5).

% Color
color(red;green;white;yellow;blue).

% Nationality
nationality(english;spanish;japanese;italian;norwegian).

% Animal
animal(dog;cat;fox;horse;zebra).

% Job
job(painter;clerk;salesman;cook;doctor).

% Beverage
beverage(tea;coffee;milk;juice;coke).

% House
house(X, C, N, A, J, B) :-
    number(X),
    color(C),
    nationality(N),
    animal(A),
    job(J),
    beverage(B).

现在，我坚持主张约束；我如何编码从1.到14.的断言?我只需要了解正确的语法，所以如果有人可以通过一两个示例将我设置在正确的轨道上，我可以弄清楚其余的例子. 谢谢.

Now I'm stuck on asserting the constraints; how do I go about coding assertions 1. through 14.? I just need to understand the proper syntax, so if someone could please set me on the right track with one or two examples I can figure out the rest. Thanks.

请注意，我可能从5和11推断出第二个房子是蓝色的房子，因为11. number_blue = number_norw ± 1，5. number_norw = 1和0不在可能的数字范围内，但是我不想手动添加它受约束，因为我希望clingo能够自行解决.

N.B. Notice I could have inferred, from 5. and 11., that the second house is the blue one because 11. number_blue = number_norw ± 1, 5. number_norw = 1, and 0 is not in the range of possible numbers, but I don't want to manually add it to the constraints because I expect clingo to figure it out itself.

推荐答案

为第一个断言添加约束的一种方法:

One way to add the constraint for the first assertation:

% 1. The English man lives in the red house.
%     S: english --> red house <==> red house OR not english
% not S: not (red house OR not english) <==> not red house AND english
% ie. it is not so, that the english man doesn't live in the red house
:- not 1 { house(X, red, english, A, J, B) :
           number(X) : animal(A) : job(J) : beverage(B) }.

再举一个第七个断言:

% 7. The green house is immediately right of the white one.
% (number_green = number_white + 1)
:- house(NG, green, _, _, _, _), house(NW, white, _, _, _, _), NG!=NW+1.

但是，这将导致更长的求解时间和更大的内存需求(千兆字节)，因为扎根的程序(gringo的输出)非常庞大.您可以使用gringo -t yourcode.asp看到它.这是因为无关紧要"变量_(和上面第一个声明的约束中的X, A, J, B).每个规则将至少以5 * 5 * 5 * 5的方式编写.

This will however lead to long solving times and large memory requirements (gigabytes), because the grounded program (output of gringo) is massive. You can see this with gringo -t yourcode.asp. This is because the "do not care" variables _ (and X, A, J, B in the constraint for the first assertation above). Each rule will be written in at least 5*5*5*5 ways.

M. Gebser建议我谓词(关系)应保持简短.实例的这种编码的问题是house/6太长了.一种解决方法是将其编码为以下样式:

M. Gebser adviced me that the predicates (relations) should be kept short. The problem with this encoding of the instance is that house/6 is so long. One way to combat this would be to encode it in the following style:

house(1..5).
elem(color, red;green;white;yellow;blue).
elem(nationality, english;spanish;japanese;italian;norwegian).
...

，然后从那里开始.现在，elem的Arity仅为2.以这种方式定义实例后，程序变得更加简单，例如.断言的约束不需要聚合(1{ ... }N语法).

and start from there. Now the arity of elem is only 2. When the instance is defined this way, the program becomes simpler eg. the constraints for the assertations do not need aggregates (the 1{ ... }N syntax).

:- not chosen(H, nationality, english), chosen(H, color, red).

M. Gebser还建议，求解器(clasp)也可以从以其他方式编写的规则中受益:

M. Gebser also suggested that the solver (clasp) might benefit form the rule being written in the other way too:

:- not chosen(H, nationality, english), chosen(H, color, red).
:- chosen(H, nationality, english), not chosen(H, color, red).

您还需要一些其他限制，例如不应将相同类型的两个不同元素映射到一所房子.

You also need some additional restrictions, like that two different elements of the same type shouldn't be mapped to one house.

为获得更好的输出，您可以建立一个关系，使其像house/6那样提供输出.

For nicer output, you can make a relation that gives the output like house/6 did.

请注意，我使用的不是最新版本的gringo3和clasp2.如果您有新的clingo，则可能需要进行一些修改.

Note that I used gringo3 and clasp2, which are not the newest versions. If you have the new clingo, there might be modifications that are needed.

这篇关于Clingo:断言部分约束的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！