今天在网上逛的时候发现一个有趣的逻辑推理题目-爱因斯坦之谜。题目的描述如下:
"在一条街上有颜色互不相同的五栋房子,不同国籍的人分别住在这五栋房子力,每人抽不同品牌的香烟,喝不同的饮料,养不同的宠物。已知如下情况:
1. 英国人住红色房子里。
2. 瑞典人养狗。
3. 丹麦人喝茶。
4. 绿色房子坐落在白色房子的左面。
5. 绿色房子的主人喝咖啡。
6. 抽Pall Mall香烟的人养鸟。
7. 黄色房子的主人抽Dunhill香烟。
8. 挪威人住第一间房子。
9. 五座房子中间的那座的主人喝牛奶。
10. 抽Blends香烟的住在养猫人的隔壁。
11. 养马的人住在抽Dunhill香烟者的隔壁。
12. 抽Blue Master香烟的喝啤酒。
13. 德国人抽Prince香烟。
14. 挪威人住的房子在蓝色房子的隔壁。
15. 抽Blends香烟的人有一个喝水的邻居。
问:谁养鱼? "
该题目的详细英文描述在维基百科上 http://en.wikipedia.org/wiki/Zebra_Puzzle
很明显这个题目是根据已知信息和规则进行一步一步的推断,最后得出结论
问题推导过程中需要记忆的信息比较多,找excel来记录,先在excel上画出空表格如下:
每一步推导过程中把当前步骤的最新结论用红色表示,
第一步
根据规则8和9推出
第二步
根据规则14推出
第三步
根据规则4和5推出
第四步
根据规则1和7推出
第五步
根据规则11推出
第六步
根据规则3推出丹麦人只能住第二间或第五间
第七步
根据第六步,假设丹麦人住第二间,则根据12条,推出第五间喝啤酒抽Blue Master,剩下的饮料水由挪威人喝
第八步
根据规则15 第二间抽Blends香烟,根据第13条第四间住德国人,又剩下的香烟Pall Mall由住第三间的人抽
第九步
根据规则6和规则10 推出
第十步
瑞典人只能住剩下第五间,又根据规则2推出
第十步完成后,答案已经揭晓:德国人养鱼
在推导过程中第七步的时候假设丹麦人住第二间,假设丹麦人住第五间会如何?
第十一步:
根据第六步,假设丹麦人住第五间,根据规则2,瑞典人住第四间,剩下的德国人住第二间,再根据规则13推出
第十二步
根据第十一步,剩下喝啤酒的人只能在住第一间或第二间,但是第一间和第二间抽烟和第12条矛盾,所以第十一步的假设不成立,丹麦人只能住第二间
用表格推理的过程已经完成,作为一个程序员接下来该做的事情是写一个算法来推导