谁的宠物是斑马。。。
爱因斯坦提出的问题，据说世界上95%的人无法解决：
Zebra Puzzle:
Five men with different nationalities and with different jobs live in consecutive houses on a street. These houses are painted different colors. The men have different pets and have different favorite drinks. Determine who owns a zebra and whose favorite drinks is mineral water(which is one of the favorite drinks) given these clues: The Englishmean lives in the red house. The Spanish owns a dog. The Japanese man is a painter. The Italian drinks tea. The Norwegian lives in the first house on the left. The green house is on the right of white one. The photographer breeds snails. The diplomat lives in the yellow house. Milk is drunk in the middle house. The owner of the green house drinks coffee. The Norwegian's house is next to the blue one. The violinist drinks orange juice. The fox is in a house next to that of the diplomat.
我的想法很简单，就是穷举法。然后用条件去约束，主要就是怎样把条件翻译成计算机语言。但是只有一个地方有问题，并且让我想了一天一夜：条件与条件之间所产生的新的条件，或者说推论。比如，隐含条件是每一个职业，饮料，房屋颜色，宠物必须是唯一的，因此，当一种职业有四个已经确定了，那么第五个也就确定了。可是，假如可以确定四个职业同时与条件不冲突，而第五个职业按照这个原则确定为最后剩下的选项时候与条件冲突，导致无法来定，那么说明前面四个职业的确定有问题，即虽然表面上与条件步冲突，实际却不可行。幸好这个题目不是要我们用这种“后验式”的推理，仔细看题目发现，在第一步就可推断出Norwegian人的房屋颜色，可是，怎样让计算机来做呢？我本来想用“树形”搜索，可是这实在是一个恶梦，后来发现这个问题的简单程度是给人的头脑设定的，还用不着计算机大师的“绞尽脑汁”。（Knight's tour就不同了，我至今还不敢去trace其中的bug---简直太夸张了，运行一两个小时没出来第四个结果。）于是，就有让程序运行两遍的笨办法---第一次找出Norwegian人的房子，然后再找别的。因为，我把初始条件设定城互相矛盾的，不选定Norwegian人的房子，条件总不成立。
很awkward的。
#include <iostream> #include <iomanip> #include <cmath>
using namespace std;
const NationNum =5; const OccupationNum = 5; const ColorNum =5; const PetNum = 5; const DrinkNum =5; const FunNum =5;
char *strCol[NationNum*4] = {"Diplomat", "Photographer", "Painter", "Violinist",
"Physician", "Red", "Yellow", "White", "Green", "Blue",
"Dog", "Snail", "Horse", "Zebra", "Fox", "Coffee", "Juice", "Tea",
"Milk", "Water"};
char *strRow[NationNum] = {"English", "Spanish", "Japanese", "Norwegian", "Italian"};
enum National
{English, Spanish, Japanese, Norwegian, Italian};
enum Occupation
{Diplomat, Photographer, Painter, Violinist, Physician};
enum Color
{Red = 5, Yellow =6, White=7, Green=8, Blue=9};
enum Pet
{Dog=10, Snail=11, Horse=12, Zebra=13, Fox=14};
enum Drink
{Coffee=15, Juice=16, Tea=17, Milk=18, Water=19};
int Logic[NationNum][NationNum * 4] = {0};
bool totalCheck(); void initialize(); void display(int num);
bool check1(); bool check4(); bool check7(); bool check12(); bool check13();
void enforce();
void restore();
void basicEnforce(int, int);
void basicRestore(int state1, int state2);
bool (*pfun[FunNum])() = {check1,check4,check7,check12, check13}; //function pointer array这样调用多个检查条件比较方便。
bool judge(int i, int j); void final();
int main()
{
initialize();
for (int counter =0; counter<2; counter++) //这纯粹是作弊，我硬要程序算两遍，因为，我还没有实现让程序去分析相关条件作推理的功能。
{
for (int i=0; i< NationNum; i++)
{
for (int j=0; j< NationNum*4; j++)
{
if (Logic[i][j]!=1)
{
judge(i, j);
}
} } final(); } display(0); display(1); display(2); display(3);
return 0; }
bool testRow(int section, int row, int &col, int &total)
{
int temp=0;
for (int j=section*NationNum; j< (section+1)*NationNum; j++)
{
temp+=j;
if (Logic[row][j]==1)
{
col= j;
return true;
}
}
total=temp;
return false;
}
void final()
{
bool testRow(int section, int row, int &col, int &total);
int col=0, mask=0, total=0;
int counter=0, row=0;
for (int k=0; k< 4; k++)
{
counter=0;
total=0;
mask=0;
for (int i=0; i< NationNum; i++)
{
if (testRow(k, i, col, total))
{
mask+= col;
}
else
{
counter++;
row= i;
}
}
if (counter==1)
{
if (judge(row, total-mask))
{
cout<<"\n find out i="<<row<<" j="<<total-mask<<endl;
}
}
}
}
bool judge(int i, int j)
{
Logic[i][j] =1;
enforce();
if (!totalCheck())
{
Logic[i][j] =0;
restore();
return false;
}
return true;
}
bool totalCheck()
{
for (int i=0; i< FunNum; i++)
{
if (!pfun[i]())
{
return false;
}
}
return true;
}
void display(int num)
{
cout<<setw(10)<<"Nationality";
for (int i=num*NationNum; i< (num+1)*NationNum; i++)
{
cout<<setw(10)<<strCol[i];
}
cout<<endl;
for (i=0; i< NationNum; i++)
{
cout<<setw(10)<<strRow[i];
for (int j =num* NationNum; j< NationNum*(num +1); j++)
{
cout<<setw(10)<<Logic[i][j];
}
cout<<endl;
}
}
bool check1()
{
return (Logic[Norwegian][Green] == 0 && Logic[Norwegian][White]==0
&& Logic[Norwegian][Blue]==0&& (Logic[Norwegian][Red]==1||Logic[Norwegian][Yellow]==1)); }
bool check4()
{
return (Logic[Norwegian][Milk]==0);
}
bool check7()
{
for (int i=0; i< NationNum; i++)
{
if (Logic[i][Physician] == 1&&Logic[i][Horse]==1) //not both
{
return false;
}
}
return true;
}
bool check12()
{
for (int i=0; i< NationNum; i++)
{
if (Logic[i][Physician]==1&& Logic[i][Fox]==1)
{
return false;
}
}
return true;
}
bool check13()
{
int result =0;
for (int i=0; i< NationNum; i++)
{
for (int k =0; k< 4; k++)
{
result =0;
for (int j= k* NationNum; j<(k+1)*NationNum; j++)
{
if (Logic[i][j]==1)
{
result ++;
if (result>1)
{
return false;
}
}
}
}
}
for (int k =0; k< 4; k++)
{
for (int j= k* NationNum; j<(k+1)*NationNum; j++)
{
result =0;
for (i=0; i< NationNum; i++)
{
if (Logic[i][j]==1)
{
result ++;
if (result>1)
{
return false;
}
}
}
}
}
return true; }
void enforce()
{
basicEnforce(Photographer, Snail);
basicEnforce(Diplomat, Yellow);
basicEnforce(Green, Coffee);
basicEnforce(Violinist, Juice);
}
void restore()
{
basicRestore(Photographer, Snail);
basicRestore(Diplomat, Yellow);
basicRestore(Green, Coffee);
basicRestore(Violinist, Juice);
}
void basicRestore(int state1, int state2)
{
for (int i=0; i< NationNum; i++)
{
if (Logic[i][state1]==0)
{
Logic[i][state2] =0;
}
if (Logic[i][state2]==0)
{
Logic[i][state1]=0;
}
}
}
void basicEnforce(int state1, int state2)
{
for (int i=0; i< NationNum; i++)
{
if (Logic[i][state1]==1)
{
Logic[i][state2] =1;
}
if (Logic[i][state2]==1)
{
Logic[i][state1]=1;
} } }
void initialize()
{
Logic[English][Red] = 1;
Logic[Spanish][Dog] = 1;
Logic[Japanese][Painter] = 1;
Logic[Italian][Tea] = 1;
}
以下就是运行结果，可以看出Egnlishman 养了zebra,Norwegian爱喝矿泉水，怎么样你做出来了吗？
