五五谜题(prolog程序) (2008-04-02 14:48:29)
标签： it 分类： 技术交流
内容: 1． 有5栋5种颜色的房子 2． 每一位房子的主人国籍都不同 3． 这五个人每人只喝一个牌子的饮料，只抽一个牌子的香烟，只养一种宠物 4． 没有人有相同的宠物，抽相同牌子的烟，喝相同牌子的饮料 已知条件： 1． 英国人住在红房子里 2． 瑞典人养了一条狗 3． 丹麦人喝茶 4． 绿房子在白房子的左边 5． 绿房子主人喝咖啡 6． 抽PALL MALL 烟的人养了一只鸟 7． 黄房子主人抽DUNHILL烟 8． 住在中间房子的人喝牛奶 9． 挪威人住在第一间房子 10． 抽混合烟的人住在养猫人的旁边 11． 养马人住在抽DUNHILL烟人的旁边 12． 抽BLUE MASTER烟的人喝啤酒 13． 德国人抽PRINCE烟 14． 挪威人住在蓝房子旁边 15． 抽混合烟的人的邻居喝矿泉水 问题：谁养鱼？ ============================= 这是个非常有趣的逻辑难题： 有五个房子，每个房子的颜色不同，里面分别住着不同国家的人，每个人都有自己 养的不同的宠物，喜欢和不同的饮料，抽不同牌子的烟。现在已知以下的一些信息 ： 英国人（englishman）住在红色（red）的房子里。 西班牙人（spaniard）养了一条狗（dog）。 挪威人（norwegian）住在左边的第一个房子里。 黄房子（yellow）里的人喜欢抽kools牌的香烟。 抽chesterfields牌香烟的人与养狐狸（fox）的人是邻居。 挪威人（norwegian）住在蓝色（blue）的房子旁边。 抽winston牌香烟的人养了一只蜗牛（Snails）。 抽Lucky Strike牌香烟的人喜欢喝桔子汁（orange juice）。 乌克兰人（ukrainian）喜欢喝茶（tea）。 日本人（japanese）抽parliaments牌的烟。 抽kools牌的香烟的人与养马（horse）的人是邻居。 喜欢喝咖啡（coffee）的人住在绿（green）房子里。 绿（green）房子在象牙白（ivory）房子的右边（图中的右边）。 中间那个房子里的人喜欢喝牛奶（milk）。 根据以上条件，你能告诉我哪个房子里的人养斑马（zebra），哪个房子里的人喜 欢喝水（water）吗？或者你能把所有的东西都对号入座吗？ 这是个典型的条件约束的问题，根据每个条件，我们都可以排除一些情况，直到最 后找到答案。不过由于这个问题的条件太多，如果人工来解答，是很要花上一点时 间的。还不如我们用这个时间来编一个程序，让计算机来解答。真的，编程花的时 间一定要比人工计算还要少！ 使用Prolog来解决这类的问题，一般使用的是“选择再校验”的方法。即用某种方 法提出一系列的可能的解，再由校验部分来判断此解是否合乎题意。直到找到答案 为止。 我们先来分析一下到底有多少种可能的解。 每个房子有不同的颜色，所以就颜色来说就有5！种情况，而一共有五个特征：颜 色、国籍、宠物、香烟和饮料。所以一共就有5!*5种情况，即600种。不是很多， 完全可以使用程序穷举出来。 下面介绍如何使用Prolog来编写解答的程序。 在此程序中使用结构h(C,N,P,Y,D)来储存房间的信息。C,N,P,Y,D分别对应颜色、 国籍、宠物、香烟和饮料。由于有五个房间，所以使用列表来储存所有房间的信息 。此列表为： [h(C1,N1,P1,Y1,D1),h(C2,N2,P2,Y2,D2),h(C3,N3,P3,Y3,D3),h(C4,N4,P4,Y4, D4),h(C5,N5,P5,Y5,D5)] 一开始所有房间的情况都是未知的，所以就使用变量来代表每个房间的情况。 在后面的条件中经常要读取房间的某个信息，所以下面就先编写五个谓词来完成这 项工作。 color(h(C,N,P,Y,D),C). nation(h(C,N,P,Y,D),N). pet(h(C,N,P,Y,D),P). yan(h(C,N,P,Y,D),Y). drink(h(C,N,P,Y,D),D). 这几个谓词很容易理解，所以就不多作解释了。 在条件中还用到了房间之间的相对位置的信息，下面的谓词就是完成这个任务的。 next(A,B,[A,B,C,D,E]). next(B,C,[A,B,C,D,E]). next(C,D,[A,B,C,D,E]). next(D,E,[A,B,C,D,E]). next(B,A,[A,B,C,D,E]). next(C,B,[A,B,C,D,E]). next(D,C,[A,B,C,D,E]). next(E,D,[A,B,C,D,E]). middle(X,[_,_,X,_,_]). first(A,[A|X]). 上面，next/3用来判断列表中两个元素是否相邻；middle/2用来读取列表的中间的 元素；first/2读取列表的第一个元素。当然，next/3不但可以判断相邻，它还能 找出相邻的元素来。例如： ?- next(4,X,[1,2,3,4,5]). X = 5 ; X = 3 ; no 很明显，next找出了列表[1,2,3,4,5]中与4相邻的元素。这里列表的元素是简单的 数字，如果是上面说所的表示房间信息的结构h(C,N,P,Y,D)，它的功能也是相同的 。 前面说过，我们将使用“选择再校验”的方法找出答案，那么我们靠什么来选择呢 ？这里将使用以前介绍过的member/2谓词。还记得member/2的定义么？ member(A,[A|X]). member(A,[B|X]) :- member(A,X). 它的第二个参数是一个列表，它可以判断第一个参数是否在这个列表中。我们是使 用递归的方法编写member/2的，如果不太清楚，请阅读列表这一章。
?- member(2,[1,2,3]). yes 我们曾经说过Prolog的谓词有多种使用方法，所以member/2还可以用来遍历列表的 所有元素。 ?-member(X,[1,2,3,4,5]). X = 1 ; X = 2 ; X = 3 ; X = 4 ; X = 5 ; no 这正是我们需要的功能，使用它就可以选择出所有的情况了。 有了以上的准备工作，我们就可以开始正式编写解答部分了。我们先把程序列出来 ，然后再来讲解。解题的谓词为solve/3，第一个参数X返回所以东西对号入座后的 房间列表，第二参数TT返回养斑马的人住的房间，第三个参数TTT返回喜欢喝水的 人的房间。 solve(X,TT,TTT):- %首先把X绑定为房间列表，注意此时的房间的属性还不能确定，所以都使用变量 代表。 X=[h(C1,N1,P1,Y1,D1),h(C2,N2,P2,Y2,D2),h(C3,N3,P3,Y3,D3),h(C4,N4,P4, Y4,D4),h(C5,N5,P5,Y5,D5)], %英国人（englishman）住在红色（red）的房子里。 member(Z1,X), %首先从X列表中选择一个房间Z1， color(Z1,red), %Z1的颜色是red。 nation(Z1,englishman), %Z1里住的人是englishman。下同。 %西班牙人（spaniard）养了一条狗（dog）。 member(Z2,X), pet(Z2,dog), nation(Z2,spaniard), %挪威人（norwegian）住在左边的第一个房子里。 first(Z3,X), nation(Z3,norwegian), %黄房子（yellow）里的人喜欢抽kools牌的香烟。 member(Z4,X), yan(Z4,kools), color(Z4,yellow), %抽chesterfields牌香烟的人与养狐狸（fox）的人是邻居。 member(Z5,X), pet(Z5,fox), next(Z6,Z5,X), %用next(Z5,Z6,X)也一样。 yan(Z6,chesterfields), %挪威人（norwegian）住在蓝色（blue）的房子旁边。 member(Z7,X), color(Z7,blue), next(Z8,Z7,X), nation(Z8,norwegian), %抽winston牌香烟的人养了一只蜗牛（Snails）。 member(Z9,X), yan(Z9,winston), pet(Z9,snails), %抽Lucky Strike牌香烟的人喜欢喝桔子汁（orange juice）。 member(Z10,X), drink(Z10,'orange juice'), yan(Z10,'Lucky Strike'), %乌克兰人（ukrainian）喜欢喝茶（tea）。 member(Z11,X), nation(Z11,ukrainian), drink(Z11,tea), %日本人（japanese）抽parliaments牌的烟。 member(Z12,X), nation(Z12,japanese), yan(Z12,parliaments), %抽kools牌的香烟的人与养马（horse）的人是邻居。 member(Z13,X), pet(Z13,horse), next(Z14,Z13,X), yan(Z14,kools), %喜欢喝咖啡（coffee）的人住在绿（green）房子里。 member(Z15,X), color(Z15,green), drink(Z15,coffee), %绿（green）房子在象牙白（ivory）房子的右边（图中的右边）。 member(Z16,X), color(Z16,ivory), next(Z17,Z16,X), %这里我们没有使用右边的条件，而是假设它们是邻居，所 以最后的答案有两个。 color(Z17,green), %这一点请读者自己修改，当然还需要编写一个判断右边的 谓词。 %中间那个房子里的人喜欢喝牛奶（milk）。 middle(Z18,X), drink(Z18,milk), %以上是所有的条件，下面开始回答我们的问题。 %找出宠物为zebra的房间。 member(TT,X), pet(TT,zebra), %找出喝水的房间。 member(TTT,X), drink(TTT,water). 你阅读这个程序应该没有什么问题吧。它简直就是把我们的条件直接翻译成 Prolog语言。例如： %抽chesterfields牌香烟的人与养狐狸（fox）的人是邻居。 member(Z5,X), pet(Z5,fox), next(Z6,Z5,X), %用next(Z5,Z6,X)也一样。 yan(Z6,chesterfields), 用语言来描述就是：首先Z5是个房子，对应于member(Z5,X)；然后它的宠物是fox ，对应于pet(Z5,fox)；它的邻居是Z6，对应于next(Z6,Z5,X)；最后Z6的人抽 chesterfields，对应于yan(Z6,chesterfields)。你看只要把原始的条件稍加分解 ，就变成了我们的Prolog程序。 哈哈，这样的程序谁都可以编出来，你看到Prolog的优势了吧。Prolog是描述型的 语言，你只要使用Prolog的语言把问题描述一遍就行了，剩下的问题就让计算机代 劳吧:)。如果使用其它的语言，例如C、Basic等，你就不得不自己考虑程序的流程 ，所以这些语言都叫作过程型的语言。比起Prolog可是低级多了。 好了，最后让我们来运行一下程序。 ?- solve(X,TT,TTT). X = [h(yellow,norwegian,fox,kools,water),h(blue,ukrainian,horse, chesterfields,tea), h(red,englishman,snails,winston,milk),h(iory,spaniard,dog,'Lucky Strike','orange juice'), h(green,japanese,zebra,parliaments,coffee)] TT = h(green,japanese,zebra,parliaments,coffee) TTT = h(yellow,norwegian,fox,kools,water) ; X = [h(yellow,norwegian,fox,kools,water),h(blue,ukrainian,horse, chesterfields,tea), h(red,englishman,snails,winston,milk),h(green,japanese,zebra, parliaments,coffee), h(ivory,spaniard,dog,'Lucky Strike','orange juice')] TT = h(green,japanese,zebra,parliaments,coffee) TTT = h(yellow,norwegian,fox,kools,water) no 由于第13个条件中我们没有使用题目中的右边的限制，所以答案就有两个，你可以 看到这两个答案的最后两个房间正好倒了过来。 再花点功夫把答案更美观地写出来，这个程序就完美了。 好了，到现在为止我只用了1个小时，那些手工解题的朋友们，怎么样，答案出来 了么
分享
顶
阅读┊ ┊ ┊┊ ┊打印┊
已投稿到：
排行榜 圈子
加载中，请稍候......
前一篇：博弈论与纳什平衡Game Theory and Nash Equilibrium
后一篇：形式化方法
评论 重要提示：警惕虚假中奖信息 在插画中找寻曾经的美好 关注每日最热门博客
发评论 旅游行摄，轻品日本 是谁改变了你的博客？ 关注每日最热门博客
登录名： 密码： 找回密码 注册
昵 称：
验证码： 请点击后输入验证码
