using System;
namespace netsafe.math
{
	public	class ayst
	{
/// <summary>
/// 问题中的所有元素
/// </summary>
string[,] data=	{{"黄房子","蓝房子","白房子","红房子","绿房子"},
{"挪威人","英国人","德国人","丹麦人","瑞典人"},
{"DUNHILL","PRINCE","混合烟", "PALL MALL","BLUE MASTER"},
{"咖 啡","矿泉水","茶","牛奶"," 啤酒 "},
{"鱼"," 恐龙","马",	"鸟","狗"}};
/// <summary>/// answer用来存放答案
/// </summary>
int[,] answer=new int[6, 6];
int[,] ALL=new int[6,122];
int	count=1;
int	nLevel	= 0;
int[] List=new int[6];
public static void	Main(string[] args)
{
	ayst c=new ayst();
	c.p();	///生成全排列到all
	c.run();
	Console.Read(); /// 按任意键继续
	}
void run()
{
	int	i1,i2,i3,i4,i5;///通过逻辑条件顺序的有效选择来优化程序
	for	(i1=1;i1<=120;i1++)///房子
	{
	///9 、挪威人住第一间房子
	///14 、挪威人住在蓝房子旁边
	///不满足条件就短路
	///	
	if (ALL[2,i1]!=2)continue;
	for(int	j=0;j<5;j++,answer[j,1]=ALL[j,i1]);
	for	(i2=1;i2<=120;i2++)///人种
	{			
		for(int	j=0;j<5;j++,answer[j,2]=ALL[j,i2]);
		///9 、挪威人住第一间房子
		if (ALL[1,i2]!=1)continue;
		///1、 英国人住在红房子里 
		///
		if (find(1,4)!=find(2,2))continue;
		///4 、绿房子在白房子左边 
		///	
		if (find(1,5)>find(1,3))continue;
		for	(i3=1;i3<=120;i3++)///烟
		{
			for(int	j=0;j<5;j++,answer[j,3]=ALL[j,i3]);
			///13、 德国人抽PRINCE烟
			///		
			if(find(2,3)!=find(3,2))continue;
			///7 、黄房子主人抽DUNHILL烟
			///		
			if(find(1,1)!=find(3,1))continue;
			for	(i4=1;i4<=120;i4++)///饮料
			{	
				for(int	j=0;j<5;j++,answer[j,4]=ALL[j,i4]);
				///8 、住在中间那间房子的人喝牛奶	
				///		
				if(ALL[3,i4]!=4)continue;
				///5 、绿房子主人喝咖啡 
				///	
				if (find(1,5)!=find(4,1))continue;
				///3 、丹麦人喝茶 
				///		
				if(find(2,4)!=find(4,3))continue;
				///15 、抽混合烟的人的邻居喝矿泉水	
				if(Math.Abs(find(3,3)-find(4,2))!=1)continue;
				///12 、抽BLUE	MASTER烟的人喝啤酒
				///		
				if(find(3,5)!=find(4,5))continue;
				for	(i5=1;i5<=120;i5++)///宠物
				{					
					for(int	j=0;j<5;j++,answer[j,5]=ALL[j,i5]);
					///10 、抽混合烟的人住在养鱼人的旁边
					///	
					if(Math.Abs(find(3,3)-find(5,1))!=1)continue;
					///2 、瑞典人养了一条狗 
					///		
					if(find(2,5)!=find(5,5))continue;
					///6 、抽PALL MALL烟的人养了一只鸟	
					///		
					if(find(3,4)!=find(5,4))continue;
					///11 、养马人住在DUNHILL烟的人旁边 
					///	
					if(Math.Abs(find(5,3)-find(3,1))!=1)continue;
					///
					///能活到这里的data,当然是答案喽
					///
					write_answer();
				}
			}
		}
	}
}
}
/// <summary>
/// 非常典型的用递归实现排列组合算法。
/// </summary>
public	void p()    
{
	int	nCount,nJudge,key;
	nLevel++;
	if(nLevel>5)
	{
		writeall();///有一种排列就写到All数组里
		nLevel--;
		return;
	}
	for(nCount=1;nCount<=5;nCount++)
	{
		key=0;
		for(nJudge=0;nJudge<=nLevel-1;nJudge++)
			if(nCount==List[nJudge])
			{
				key=1;
				break;
			}
		if(key==0)
		{
			List[nLevel]=nCount;
			p();
		}
	}
	nLevel--;
}
/// <summary>
/// 写入all数组
/// </summary>
void writeall()
{
	int	i;
	for	(i=1;i<=5;i++)
	{
		ALL[i,count]=List[i];
	}		
	count++;
}
int	 find(int i,int	j)
{
	int	k;
	for(k=0;k<=5;k++)
	{
		if (answer[k,i]==j)
		{
			return k;
		}
	}
	return -1;
}
/// <summary>
/// 将答案打印出来
/// </summary>
void write_answer()
{
	for	(int i = 1;i<=5;i++)
	{
		for(int	j=1	;j<=5;j++)
		{
			Console.Write(data[i-1,answer[j,i]-1]+",");
		}
		Console.WriteLine();
	}
	Console.WriteLine();
}
}
}