*/ --------------------------------------------------------------------------------------
*/ 出自： 编程中国 http://www.bc-cn.net
*/ 作者： yu_hua
*/ 时间： 2007-11-10 编程论坛首发
*/ 声明： 尊重作者劳动，转载请保留本段文字
*/ --------------------------------------------------------------------------------------

题目是：
1、 在一条街上，有5座房子，喷了5种颜色。
2、 每个房里住着不同国籍的人
3、 每个人喝不同的饮料，抽不同品牌的香烟，养不同的宠物
约束条件：
1、 英国人住红色房子
2、 瑞典人养狗
3、 丹麦人喝茶
4、 绿色房子在白色房子左面
5、 绿色房子主人喝咖啡
6、 抽Pall Mall 香烟的人养鸟
7、 黄色房子主人抽、Dunhill 香烟
8、 住在中间房子的人喝牛奶
9、 挪威人住第一间房
10、抽Blends香烟的人住在养猫的人隔壁
11、养马的人住抽Dunhill 香烟的人隔壁
12、抽Blue Master的人喝啤酒
13、德国人抽Prince香烟
14、挪威人住蓝色房子隔壁
15、抽Blends香烟的人有一个喝水的邻居

问题是：谁养鱼？

/*爱因斯坦难题的Ｃ语言程序设计(原创)*/
#include<stdio.h>
char*COL[]={NULL,"红","黄","绿","蓝","白"};
char*PAD[]={NULL,"狗","猫","鱼","鸟","马"};
char*DRK[]={NULL,"茶 ","牛奶","咖啡","啤酒","水 "};
char*GUO[]={NULL,"挪威","英国","德国","丹麦","瑞典"};
char*SMK[]={NULL,"Blends","BlueMaster","Dunhill","Pall Mall","Prince"};
struct{ char guojia, color, pads, drink, smoke; } aa[5];
int OK(void)
{
int i,j;
for(i=0;i<5;i++)
if(aa[i].guojia==2 && aa[i].color==1)goto next1;
return 0;
next1:
for(i=0;i<5;i++)
if(aa[i].guojia==5 && aa[i].pads==1)goto next2;
return 0;
next2:
for(i=0;i<5;i++)
if(aa[i].guojia==4 && aa[i].drink==1)goto next3;
return 0;
next3:
for(i=0;i<5;i++)
if(aa[i].color==3)goto next3_1;
return 0;
next3_1:
for(j=i+1;j<5;j++)
if(aa[j].color==5)goto next4;
return 0;
next4:
for(i=0;i<5;i++)
if(aa[i].color==3 && aa[i].drink==3)goto next5;
return 0;
next5:
for(i=0;i<5;i++)
if(aa[i].smoke==4 && aa[i].pads==4)goto next6;
return 0;
next6:
for(i=0;i<5;i++)
if(aa[i].color==2 && aa[i].smoke==3)goto next7;
return 0;
next7:
for(i=0;i<5;i++)
if(aa[i].guojia==3 && aa[i].smoke==5)goto next10;
return 0;
next10:
for(i=0;i<5;i++)
if(aa[i].smoke==2 && aa[i].drink==4)goto next11;
return 0;
next11:
for(i=0;i<5;i++)
if(aa[i].smoke==3)goto next12_1;
next12_1:
if(i==0){if(aa[1].pads==5)goto next13;}
else if(i==4){if(aa[3].pads==5)goto next13;}
else if(aa[i-1].pads==5||aa[i+1].pads==5)goto next13;
return 0;
next13:
for(i=0;i<5;i++)
if(aa[i].smoke==1)goto next13_1;
next13_1:
if(i==0){if(aa[1].pads==2)goto next14;}
else if(i==4){if(aa[3].pads==2)goto next14;}
else if(aa[i-1].pads==2||aa[i+1].pads==2)goto next14;
return 0;
next14:
for(i=0;i<5;i++)
if(aa[i].smoke==1)goto next14_1;
next14_1:
if(i==0){if(aa[1].drink==5)goto next15;}
else if(i==4){if(aa[3].drink==5)goto next15;}
else if(aa[i-1].drink==5||aa[i+1].drink==5)goto next15;
return 0;
next15:
return 1;
}

char color[4]={1,2,3,5};
char drink[4]={1,3,4,5};
char guojia[4]={2,3,4,5};
char smoke[]={1,2,3,4,5};
char pads[5]={1,2,3,4,5};

int rot(char a[],int n)
{ int i,j,k,t;
for(k=n-1;k>0;k--)
if(a[k-1]<a[k])break;
if(k==0)
{ for(i=0,j=n-1;i<j;i++,j--)
{char t=a[i];
a[i]=a[j];
a[j]=t;
}
return 0;
}
t=a[k-1];i=k;
for(j=k+1;j<n;j++)
if(t<a[j]&&a[j]<a[i])i=j;
a[k-1]=a[i];a[i]=t;
for(i=k;i<n-1;i++)
for(j=k;j<n-1+k-i;j++)
if(a[j]>a[j+1])
{ t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
return 1;
}

int main()
{ int i,j,k,ans=0;
int i1,i2,i3,i4,i5;
aa[1].color=4;
aa[2].drink=2;
aa[0].guojia=1;
for(i1=0;i1<24;i1++){
aa[0].color=color[0];
aa[2].color=color[1];
aa[3].color=color[2];
aa[4].color=color[3];
rot(color,4);
for(i2=0;i2<24;i2++){
aa[0].drink=drink[0];
aa[1].drink=drink[1];
aa[3].drink=drink[2];
aa[4].drink=drink[3];
rot(drink,4);
for(i3=0;i3<24;i3++){
aa[1].guojia=guojia[0];
aa[2].guojia=guojia[1];
aa[3].guojia=guojia[2];
aa[4].guojia=guojia[3];
rot(guojia,4);
for(i4=0;i4<120;i4++){
for(i=0;i<5;i++)
aa[i].smoke=smoke[i];
rot(smoke,5);
for(i5=0;i5<120;i5++){
for(j=0;j<5;j++)
aa[j].pads=pads[j];
rot(pads,5);
if(OK()){
printf("---------------------第%d种解---------------------\n",++ans);
for(k=0;k<5;k++)
printf("第%d户: %s人 %s房子 养%s 喝%s 抽%s\n",k+1,GUO[aa[k].guojia],
COL[aa[k].color],PAD[aa[k].pads],DRK[aa[k].drink],SMK[aa[k].smoke]);
}}}}}}
return 0;
}

运行结果表明：总共有七组可能的解答，具体如下
---------------------第1种解---------------------
第1户: 挪威人 黄房子 养猫 喝水 抽Dunhill
第2户: 丹麦人 蓝房子 养马 喝茶 抽Blends
第3户: 英国人 红房子 养鸟 喝牛奶 抽Pall Mall
第4户: 德国人 绿房子 养鱼 喝咖啡 抽Prince
第5户: 瑞典人 白房子 养狗 喝啤酒 抽BlueMaster
---------------------第2种解---------------------
第1户: 挪威人 绿房子 养鸟 喝咖啡 抽Pall Mall
第2户: 德国人 蓝房子 养猫 喝水 抽Prince
第3户: 英国人 红房子 养马 喝牛奶 抽Blends
第4户: 丹麦人 黄房子 养鱼 喝茶 抽Dunhill
第5户: 瑞典人 白房子 养狗 喝啤酒 抽BlueMaster
---------------------第3种解---------------------
第1户: 挪威人 绿房子 养鸟 喝咖啡 抽Pall Mall
第2户: 德国人 蓝房子 养鱼 喝水 抽Prince
第3户: 英国人 红房子 养马 喝牛奶 抽Blends
第4户: 丹麦人 黄房子 养猫 喝茶 抽Dunhill
第5户: 瑞典人 白房子 养狗 喝啤酒 抽BlueMaster
---------------------第4种解---------------------
第1户: 挪威人 绿房子 养鱼 喝咖啡 抽Blends
第2户: 德国人 蓝房子 养猫 喝水 抽Prince
第3户: 瑞典人 黄房子 养狗 喝牛奶 抽Dunhill
第4户: 英国人 红房子 养马 喝啤酒 抽BlueMaster
第5户: 丹麦人 白房子 养鸟 喝茶 抽Pall Mall
---------------------第5种解---------------------
第1户: 挪威人 绿房子 养鸟 喝咖啡 抽Pall Mall
第2户: 德国人 蓝房子 养猫 喝水 抽Prince
第3户: 瑞典人 白房子 养狗 喝牛奶 抽Blends
第4户: 英国人 红房子 养马 喝啤酒 抽BlueMaster
第5户: 丹麦人 黄房子 养鱼 喝茶 抽Dunhill
---------------------第6种解---------------------
第1户: 挪威人 绿房子 养鸟 喝咖啡 抽Pall Mall
第2户: 德国人 蓝房子 养猫 喝水 抽Prince
第3户: 瑞典人 白房子 养狗 喝牛奶 抽Blends
第4户: 丹麦人 黄房子 养鱼 喝茶 抽Dunhill
第5户: 英国人 红房子 养马 喝啤酒 抽BlueMaster
---------------------第7种解---------------------
第1户: 挪威人 绿房子 养鸟 喝咖啡 抽Pall Mall
第2户: 德国人 蓝房子 养鱼 喝水 抽Prince
第3户: 瑞典人 白房子 养狗 喝牛奶 抽Blends
第4户: 丹麦人 黄房子 养猫 喝茶 抽Dunhill
第5户: 英国人 红房子 养马 喝啤酒 抽BlueMaster

搜索+剪枝

楼主强人啊
这道题倒是很早见过
顶完毕

哦，以前在杂志上看过，15分钟推出2个，看来当时做的答案不是全部的情况

我以前就看过~~~

2楼的程序好多 goto 啊
goto用多了不好哦

考虑一下不用 goto 啊。

/*------------------------------
爱因斯坦出的逻辑推理难题
Ｃ语言程序(已将goto消除)
-------------------------------*/
#include<stdio.h>
#include<math.h>
int aa[5][5];
//aa第0行的意义: 挪威、英国、瑞典、德国、丹麦
//aa第1行的意义: 蓝、黄、绿、红、白
//aa第2行的意义: 牛奶、咖啡、啤酒、茶、水
//aa第3行的意义: 猫、狗、马、鸟、鱼
//aa第4行的意义: Blends、BlueMaster、Dunhill、Pall Mall、Prince
//aa[i][j]的意义:该人或物所属房间号(注意思路已经有了改变)
char*msg[][5]={"挪威人","英国人","瑞典人","德国人","丹麦人",
"蓝房子","黄房子","绿房子","红房子","白房子",
"喝牛奶","喝咖啡","喝啤酒","喝茶 ","喝水 ",
"养猫","养狗","养马","养鸟","养鱼","抽Blends",
"抽BlueMaster","抽Dunhill","抽Pall Mall","抽Prince"};
char guoji[4]={2,3,4,5};
char color[4]={1,3,4,5};
char drink[4]={1,2,4,5};
char pads[5]={1,2,3,4,5};
char smoke[]={1,2,3,4,5};

int OK(void)
{
if( (aa[1][1]==aa[4][2]) //黄房 抽Dunhill
&&(aa[2][1]==aa[1][2]) //绿房 喝咖啡
&&(aa[0][1]==aa[1][3]) //红房 英国人
&&(aa[2][2]==aa[4][1]) //喝啤酒者 抽BlueMaster
&&(aa[3][3]==aa[4][3]) //养鸟者 抽PallMal
&&(aa[0][2]==aa[3][1]) //瑞典人 养狗
&&(aa[0][3]==aa[4][4]) //德国人 抽Prince
&&(aa[0][4]==aa[2][3]) //丹麦人 喝茶
&&(abs(aa[4][0]-aa[3][0])==1)// 抽Blends者与养猫人邻居
&&(abs(aa[4][0]-aa[2][4])==1)// 抽Blends者与喝水人邻居
&&(abs(aa[3][2]-aa[4][2])==1)// 抽Dunhil者与养马人邻居
) return 1;
else
return 0;
}

int rot(char a[],int n) //全排列
{ int i,j,k,t;
for(k=n-1;k>0;k--)
if(a[k-1]<a[k])break;
if(k==0)
{ for(i=0,j=n-1;i<j;i++,j--)
{ char t=a[i];
a[i]=a[j];
a[j]=t;
}
return 0;
}
t=a[k-1];i=k;
for(j=k+1;j<n;j++)
if(t<a[j]&&a[j]<a[i])i=j;
a[k-1]=a[i];a[i]=t;
for(i=k;i<n-1;i++)
for(j=k;j<n-1+k-i;j++)
if(a[j]>a[j+1])
{ t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
return 1;
}

int main()
{
int i1,i2,i3,i4,i5,i,j,k,ans=0;
aa[0][0]=1; //表示挪威人住在1号房
aa[1][0]=2; //表示蓝色房子是2号房
aa[2][0]=3; //表示喝牛奶者在3号房
for(i1=0;i1<24;i1++)
{ for(j=0;j<4;j++)aa[1][j+1]=color[j];
rot(color,4);
if(aa[1][2]<aa[1][4]) //绿房在白房的左边
for(i2=0;i2<24;i2++)
{ for(j=0;j<4;j++)aa[0][j+1]=guoji[j];
rot(guoji,4);
for(i3=0;i3<24;i3++)
{ for(j=0;j<4;j++)aa[2][j+1]=drink[j];
rot(drink,4);
for(i4=0;i4<120;i4++)
{ for(j=0;j<5;j++)aa[3][j]=pads[j];
rot(pads,5);
for(i5=0;i5<120;i5++)
{ for(j=0;j<5;j++)aa[4][j]=smoke[j];
rot(smoke,5);
if(OK())
{ printf("--------------第%d组解如下--------------------\n",++ans);
for(k=1;k<=5;k++)
{ printf("第%d户: ",k);
for(i=0;i<=4;i++)
for(j=0;j<=4;j++)
if(aa[i][j]==k)printf("%s ",msg[i][j]);
printf("\n");
}
}
}
}
}
}
}
printf("=============================================\n");
return 0;
}

/*------------------------------
怎样让爱因斯坦出的逻辑
推理难题只有唯一的解?
见下文中的红色粗体字。
-------------------------------*/
#include<stdio.h>
#include<math.h>
int aa[5][5];
//aa第0行的意义: 挪威、英国、瑞典、德国、丹麦
//aa第1行的意义: 蓝、黄、绿、红、白
//aa第2行的意义: 牛奶、咖啡、啤酒、茶、水
//aa第3行的意义: 猫、狗、马、鸟、鱼
//aa第4行的意义: Blends、BlueMaster、Dunhill、Pall Mall、Prince
//aa[i][j]的意义:该人或物所属房间号
char*msg[][5]={"挪威人", "英国人", "瑞典人", "德国人", "丹麦人",
"蓝房子", "黄房子", "绿房子", "红房子", "白房子",
"喝牛奶", "喝咖啡", "喝啤酒", "喝茶 ", "喝水 ",
"养猫", "养狗", "养马", "养鸟", "养鱼",
"抽Blends","抽BlueMaster","抽Dunhill","抽Pall Mall","抽Prince"};
char guoji[4]={2,3,4,5};
char color[4]={1,3,4,5};
char drink[4]={1,2,4,5};
char pads[5]={1,2,3,4,5};
char smoke[]={1,2,3,4,5};

int OK(void)
{
if( (aa[1][1]==aa[4][2]) //黄房 抽Dunhill
&&(aa[2][1]==aa[1][2]) //喝咖啡者 绿房
&&(aa[0][1]==aa[1][3]) //英国人 红房
&&(aa[2][2]==aa[4][1]) //喝啤酒者 抽BlueMaster
&&(aa[3][3]==aa[4][3]) //养鸟者 抽PallMal
&&(aa[0][2]==aa[3][1]) //瑞典人 养狗
&&(aa[0][3]==aa[4][4]) //德国人 抽Prince
&&(aa[0][4]==aa[2][3]) //丹麦人 喝茶
&&(abs(aa[4][0]-aa[3][0])==1)// 抽Blends者与养猫人邻居
&&(abs(aa[4][0]-aa[2][4])==1)// 抽Blends者与喝水人邻居
&&(abs(aa[4][2]-aa[3][2])==1)// 抽Dunhil者与养马人邻居
) return 1;
else
return 0;
}

int rot(char a[],int n) //全排列
{ int i,j,k,t;
for(k=n-1;k>0;k--)
if(a[k-1]<a[k])break;
if(k)
{
t=a[k-1];i=k;
for(j=k+1;j<n;j++)
if(t<a[j]&&a[j]<a[i])i=j;
a[k-1]=a[i];a[i]=t;
for(i=k;i<n-1;i++)
for(j=k;j<n-1+k-i;j++)
if(a[j]>a[j+1])
{ t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
else
for(i=0,j=n-1;i<j;i++,j--)
{ t=a[i];
a[i]=a[j];
a[j]=t;
}
return k;
}

int main()
{
int i,j,k,ans=0;
aa[0][0]=1; //表示挪威人住在1号房
aa[1][0]=2; //表示蓝色房子是2号房
aa[2][0]=3; //表示喝牛奶者在3号房
do
{ for(j=0;j<4;j++)aa[0][j+1]=guoji[j];//国籍
do
{ for(j=0;j<4;j++)aa[1][j+1]=color[j];//颜色
if(aa[1][4]-aa[1][2]==1)//绿房应为白房的左邻，而不能仅仅是在白房的左边
do
{ for(j=0;j<4;j++)aa[2][j+1]=drink[j];//饮料
do
{ for(j=0;j<5;j++)aa[3][j]=pads[j];//宠物
do
{ for(j=0;j<5;j++)aa[4][j]=smoke[j];//香烟
if(OK())
{
printf("--------------第%d组解如下--------------------\n",++ans);
for(k=1;k<=5;k++)
{
printf("第%d户: ",k);
for(i=0;i<=4;i++)
for(j=0;j<=4;j++)
if(aa[i][j]==k)printf("%s ",msg[i][j]);
printf("\n");
}
}
}while(rot(smoke,5));//五种香烟全排列
}while(rot(pads,5)); //五种宠物全排列
}while(rot(drink,4)); //咖啡,啤酒,茶,水全排列
}while(rot(color,4)); //黄色,绿色,红色,白色全排列
}while(rot(guoji,4)); //英国,瑞典,德国,丹麦全排列
printf("=============================================\n");
return 0;
}