/*--------------------------------------------
本人用Ｃ语言编写的破解难题的程序(完美版)
----------------------------------------------*/
#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;
}
/**
--------------第1组解如下--------------------
第1户: 挪威人 黄房子 喝水 养猫 抽Dunhill
第2户: 丹麦人 蓝房子 喝茶 养马 抽Blends
第3户: 英国人 红房子 喝牛奶 养鸟 抽Pall Mall
第4户: 德国人 绿房子 喝咖啡 养鱼 抽Prince
第5户: 瑞典人 白房子 喝啤酒 养狗 抽BlueMaster
--------------第2组解如下--------------------
第1户: 挪威人 绿房子 喝咖啡 养鱼 抽Blends
第2户: 德国人 蓝房子 喝水 养猫 抽Prince
第3户: 瑞典人 黄房子 喝牛奶 养狗 抽Dunhill
第4户: 英国人 红房子 喝啤酒 养马 抽BlueMaster
第5户: 丹麦人 白房子 喝茶 养鸟 抽Pall Mall
--------------第3组解如下--------------------
第1户: 挪威人 绿房子 喝咖啡 养鸟 抽Pall Mall
第2户: 德国人 蓝房子 喝水 养猫 抽Prince
第3户: 英国人 红房子 喝牛奶 养马 抽Blends
第4户: 丹麦人 黄房子 喝茶 养鱼 抽Dunhill
第5户: 瑞典人 白房子 喝啤酒 养狗 抽BlueMaster
--------------第4组解如下--------------------
第1户: 挪威人 绿房子 喝咖啡 养鸟 抽Pall Mall
第2户: 德国人 蓝房子 喝水 养鱼 抽Prince
第3户: 英国人 红房子 喝牛奶 养马 抽Blends
第4户: 丹麦人 黄房子 喝茶 养猫 抽Dunhill
第5户: 瑞典人 白房子 喝啤酒 养狗 抽BlueMaster
--------------第5组解如下--------------------
第1户: 挪威人 绿房子 喝咖啡 养鸟 抽Pall Mall
第2户: 德国人 蓝房子 喝水 养猫 抽Prince
第3户: 瑞典人 白房子 喝牛奶 养狗 抽Blends
第4户: 丹麦人 黄房子 喝茶 养鱼 抽Dunhill
第5户: 英国人 红房子 喝啤酒 养马 抽BlueMaster
--------------第6组解如下--------------------
第1户: 挪威人 绿房子 喝咖啡 养鸟 抽Pall Mall
第2户: 德国人 蓝房子 喝水 养鱼 抽Prince
第3户: 瑞典人 白房子 喝牛奶 养狗 抽Blends
第4户: 丹麦人 黄房子 喝茶 养猫 抽Dunhill
第5户: 英国人 红房子 喝啤酒 养马 抽BlueMaster
--------------第7组解如下--------------------
第1户: 挪威人 绿房子 喝咖啡 养鸟 抽Pall Mall
第2户: 德国人 蓝房子 喝水 养猫 抽Prince
第3户: 瑞典人 白房子 喝牛奶 养狗 抽Blends
第4户: 英国人 红房子 喝啤酒 养马 抽BlueMaster
第5户: 丹麦人 黄房子 喝茶 养鱼 抽Dunhill
=============================================
**/
