Posted by on 2017年3月19日

今天来分析一下前几天发的Einstein's fish riddle(AKA. Zebra Puzzle)。其实这个逻辑题目并不难,据说全球只有98%的人能够解出来也多半只是个噱头。

首先主要有以下几个变量需要我们分析:
I.房子顺序(简称OH, Order of house, 以从左到右建立1D坐标系):
我们设定OH为一个函数,
OH(a)=num
表示a对应的房子次序为num.
II.房子颜色(简称CH, Colour of house): {CH}_1=红,{CH}_2=绿,{CH}_3=白,{CH}_4=黄,{CH}_5=蓝;
III.主人国籍(简称NA, Nationality): {NA}_1=英国,{NA}_2=瑞典,{NA}_3=丹麦,{NA}_4=挪威,{NA}_5=德国;
IV.喜爱的饮料(简称DR, Drink): {DR}_1=茶,{DR}_2=咖啡,{DR}_3=牛奶,{DR}_4=啤酒,{DR}_5=水;
V.喜爱的烟品牌(简称BC, Brand of Cigarette): {BC}_1=Pall Mall, {BC}_2=Dunhill, {BC}_3=Blends, {BC}_4=Bluemasters, {BC}_5=Prince;
VI.养的宠物(简称PE, Pets): {PE}_1=狗,{PE}_2=鸟,{PE}_3=猫,{PE}_4=马,{PE}_5=鱼(题目问的是鱼,当然最后一个题干中未说明的未知宠物便是鱼。)

下面我们分析一下提供的15个条件

1. 英国人住在红色房子里;
2. 瑞典人养着狗;
3. 丹麦人爱喝茶;
4. 绿色房子在白色房子左边;
5. 绿色房子的主人爱喝咖啡;
6. 抽Pall Mall香烟品牌的人养鸟;
7. 黄色房子的主任抽Dunhills(喜路登)品牌香烟;
8. 位置在中间的房子的主任爱喝牛奶;
9. 挪威人住在第一幢房子里;
10. 抽Blend品牌香烟的人有个养猫的邻居;
11. 抽Blue Masters品牌香烟的人爱喝啤酒;
12. 养马的人住在抽Dunhill香烟品牌的人隔壁;
13. 德国人抽Prince品牌香烟;
14. 挪威人住在蓝色房子隔壁;
15. 抽Blend品牌香烟的人有个爱喝水的邻居;

我们在此再假设一个函数:
Cor(a,b)=1
表示ab是在描述同一个主人。为了表达方便,我们直接用Cor(a,b)表示。
因此上述15条信息对应的数学表达式就是

1. Cor({NA}_1,{CH}_1);
2. Cor({NA}_2,{PE}_1);
3. Cor({NA}_3,{DR}_1);
4. OH({CH}_2)=OH({CH}_3)-1;
5. Cor({CH}_2,{DR}_2);
6. Cor({BC}_1,{PE}_2);
7. Cor({CH}_4,{BC}_2);
8. OH({DR}_3)=3;
9. OH({NA}_4)=1 or OH({NA}_4)=5;
10. OH({BC}_3)=OH({PE}_3)\pm 1;
11. Cor({BC}_4,{DR}_4);
12. OH({PE}_4)=OH({BC}_2)\pm 1;
13. Cor({NA}_5,{BC}_5);
14. OH({NA}_4)=OH({CH}_5)\pm 1;
15. OH({BC}_3)=OH({DR}_5)\pm 1.

其中有8条Cor()关系和7条OH()信息。

假设H101:根据第9条,假设OH({NA}_4)=1
根据第14条得出\rightarrowOH({CH}_5)=2
根据第8条,OH({DR}_3)=3
画出表格如下:

OH __1__ __2__ __3__ __4__ __5__
CH _____ {CH}_5 _____ _____ _____
NA {NA}_4 _____ _____ _____ _____
DR _____ _____ {DR}_3 _____ _____
BC _____ _____ _____ _____ _____
PE _____ _____ _____ _____ _____

基于假设H101我们提出假设H10101:OH({CH}_2)=3
根据条件4\rightarrowOH({CH}_3)=4
根据条件5\rightarrowOH({DR}_2)=3
这与H101中的OH({DR}_3)=3矛盾,所以H10101不成立。

OH __1__ __2__ __3__ __4__ __5__
CH _____ {CH}_5 {CH}_2 {CH}_3 _____
NA {NA}_4 _____ _____ _____ _____
DR _____ _____ {DR}_3 _____ _____
BC _____ _____ _____ _____ _____
PE _____ _____ _____ _____ _____

基于H101我们提出另一个假设H10102OH({CH}_2)=4
根据条件4\rightarrowOH({CH}_3)=5
根据条件5\rightarrowOH({DR}_2)=4
是不是发现好像在做数独(Sudoku)?
目前为止的突破口在{CH}一列中,我们还有{CH}_1{CH}_4没有填。

OH __1__ __2__ __3__ __4__ __5__
CH _____ {CH}_5 _____ {CH}_2 {CH}_3
NA {NA}_4 _____ _____ _____ _____
DR _____ _____ {DR}_3 {DR}_2 _____
BC _____ _____ _____ _____ _____
PE _____ _____ _____ _____ _____

而由条件1,{CH}_1{NA}_1是相关的,所以只能得出
\rightarrowOH({CH}_1)=3,同时得出
\rightarrowOH({NA}_1)=3
进而得出
\rightarrowOH({CH}_4)=1
由条件7得出\rightarrowOH({BC}_2)=1
由条件12得\rightarrowOH({PE}_4)=2.

OH __1__ __2__ __3__ __4__ __5__
CH {CH}_4 {CH}_5 {CH}_1 {CH}_2 {CH}_3
NA {NA}_4 _____ {NA}_1 _____ _____
DR _____ _____ {DR}_3 {DR}_2 _____
BC {BC}_2 _____ _____ _____ _____
PE _____ {PE}_4 _____ _____ _____

接下来的突破口在{NA}一列,由条件3我们可以知道{NA}_3{DR}_1是相关的。所以{NA}_3只有可能在2号或者5号位。
基于假设H10102我们再假设H1010201OH({NA}_3)=2
由条件3\rightarrowOH({DR}_1)=2.
由条件11得\rightarrow
OH({DR}_4)=5
OH({BC}_4)=5从而\rightarrowOH({DR}_5)=1
由条件15得\rightarrowOH({BC}_3)=2

OH __1__ __2__ __3__ __4__ __5__
CH {CH}_4 {CH}_5 {CH}_1 {CH}_2 {CH}_3
NA {NA}_4 {NA}_3 {NA}_1 _____ _____
DR {DR}_5 {DR}_1 {DR}_3 {DR}_2 {DR}_4
BC {BC}_2 {BC}_3 _____ _____ {BC}_4
PE _____ {PE}_4 _____ _____ _____

由条件13得\rightarrow
OH({NA}_5)=4
OH({BC}_5)=4从而\rightarrow
OH({NA}_2)=5
OH({BC}_1)=3
由条件2\rightarrowOH({PE}_1)=5
由条件6\rightarrowOH({PE}_2)=3
由条件10\rightarrowOH({PE}_3)=1

OH __1__ __2__ __3__ __4__ __5__
CH {CH}_4 {CH}_5 {CH}_1 {CH}_2 {CH}_3
NA {NA}_4 {NA}_3 {NA}_1 {NA}_5 {NA}_2
DR {DR}_5 {DR}_1 {DR}_3 {DR}_2 {DR}_4
BC {BC}_2 {BC}_3 {BC}_1 {BC}_5 {BC}_4
PE {PE}_3 {PE}_4 {PE}_2 _____ {PE}_1

故而可得OH({PE}_5)=4.即对应的其他变量为
{CH}_2=绿色房子
{NA}_5=德国人
{DR}_2=爱喝咖啡
{CI}_5=爱抽Prince品牌香烟

那么这个puzzle完了吗?当然没有,目前为止只能证明假设H1010201OH({NA}_3)=2可行。
我们还需要证明假设H1010202OH({NA}_3)=5不可行。方法类似,不再赘述。
但是有趣的地方在于还有一个假设我们还没有验证,那就是假设H102OH({NA}_4)=5。这个假设可行吗?
答案是可行的,而且得到的排列方式与假设H101完全不同,但是结果却一样。
排列如下:

OH __1__ __2__ __3__ __4__ __5__
CH {CH}_2 {CH}_3 {CH}_1 {CH}_5 {CH}_4
NA {NA}_5 {NA}_2 {NA}_1 {NA}_3 {NA}_4
DR {DR}_2 {DR}_4 {DR}_3 {DR}_1 {DR}_5
BC {BC}_5 {BC}_4 {BC}_1 {BC}_3 {BC}_2
PE _____ {PE}_1 {PE}_2 {PE}_4 {PE}_3

你会发现其实每个房子对应的各个变量都与上一个最终答案是一样的。
综上,养鱼的是爱喝咖啡、爱抽Prince品牌香烟,住绿色房子的德国人。

其实这类逻辑问题也可以用计算机来解决。最合适的就是用Prolog(wiki)进行逻辑编程了。

有别于一般的函数式语言,prolog的程序是基于谓词逻辑的理论。最基本的写法是定立对象与对象之间的关系,之后可以用询问目标的方式来查询各种对象之间的关系。系统会自动进行匹配及回溯,找出所询问的答案。典型的函数式编程语言

A more fruitful approach to logic was developed in the 1970s by Robert Kowalski at the University of Edinburgh, and soon this led to the collaboration with French researchers Alain Colmerauer and Philippe Roussel who created the successful logic programming language Prolog. Prolog uses a subset of logic (Horn clauses, closely related to "rules" and "production rules") that permit tractable computation. Rules would continue to be influential, providing a foundation for Edward Feigenbaum's expert systems and the continuing work by Allen Newell and Herbert A. Simon that would lead to Soar and their unified theories of cognition.

也就是说Prolog更适合也更加便于解决这类逻辑和符号推理问题。
因为6个属性都处在有限集,所以我们可以用穷举法(Method of exhaustion)/回溯搜索(backtracking),同时需要及时有效地动态规划(dynamic programming)剪枝。这里有详细的解法,see here and here.
各种语言版本的code在这里.

【欢迎关注微信公众号饱蠹阁BaoDuGe
[arrow_forms id='119']

Posted in: Academic 無涯齋
Tags:
17 views
1 Star2 Stars3 Stars4 Stars5 Stars (No Ratings Yet)
Loading...

Comments

Be the first to comment.

Leave a Reply

返回顶部