/*------------------------------
爱因斯坦逻辑推理难题
Ｃ语言程序设计完美版
-------------------------------*/
#include<stdio.h>
#include<math.h>
char guoji[]={1/*挪威人住1号房*/,2,3,4,5},
color[]={2/*蓝房子是2号房*/,1,3,4,5},
drink[]={3/*喝牛奶者3号房*/,1,2,4,5},
pads[ ]={1,2,3,4,5},
smoke[]={1,2,3,4,5},
*aa[5]={guoji,color,drink,pads,smoke},
*msg[]={"挪威人", "英国人", "瑞典人", "德国人", "丹麦人",
"蓝房子", "黄房子", "绿房子", "红房子", "白房子",
"喝牛奶", "喝咖啡", "喝啤酒", "喝茶 ", "喝水 ",
"养猫", "养狗", "养马", "养鸟", "养鱼" ,
"抽Blends","抽BlueMaster","抽Dunhill","抽Pall Mall","抽Prince"};
int OK(void)
{
if( (color[1]==smoke[2]) //住黄房者 抽Dunhill
&&(drink[1]==color[2]) //喝咖啡者 住绿房
&&(guoji[1]==color[3]) //英国人 住红房
&&(drink[2]==smoke[1]) //喝啤酒者 抽BlueMaster
&&(pads[3]==smoke[3]) //养鸟者 抽PallMal
&&(guoji[2]==pads[1]) //瑞典人 养狗
&&(guoji[3]==smoke[4]) //德国人 抽Prince
&&(guoji[4]==drink[3]) //丹麦人 喝茶
&&(abs(smoke[0]-pads[0])==1)// 抽Blends者与养猫人邻居
&&(abs(smoke[0]-drink[4])==1)// 抽Blends者与喝水人邻居
&&(abs(smoke[2]-pads[2])==1)// 抽Dunhil者与养马人邻居
&&((color[2]-color[4])== -1)// 绿房是白房的左邻
) return 1;
else
return 0;
}
//全排列(要求n个元素互异,且最初n个元素已按升序排列好)
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;
do
{
do
{
do
{
do
{
do
{
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[5*i+j]);
printf("\n");
}
}
}while(rot(smoke,5)); //五种香烟全排列
}while(rot(pads,5)); //五种宠物全排列
}while(rot(drink+1,4));//咖啡,啤酒,茶,水全排列
}while(rot(color+1,4));//黄色,绿色,红色,白色全排列
}while(rot(guoji+1,4)); //英国,瑞典,德国,丹麦全排列
printf("=============================================\n");
return 0;
}
/** 运行结果
--------------第1组解如下--------------------
第1户: 挪威人 黄房子 喝水 养猫 抽Dunhill
第2户: 丹麦人 蓝房子 喝茶 养马 抽Blends
第3户: 英国人 红房子 喝牛奶 养鸟 抽Pall Mall
第4户: 德国人 绿房子 喝咖啡 养鱼 抽Prince
第5户: 瑞典人 白房子 喝啤酒 养狗 抽BlueMaster
=============================================
**/
