做个数独玩一玩

今天突发奇想，看到空间有一个数独，从前没有做过这类的东西，数独源于瑞士，后在美国发展、并在日本得以发扬光大的数学智力拼图游戏。拼图是九宫格（即3格宽×3格高）的正方形状，每一格又细分为一个九宫格。在每一个小九宫格中，分别填上1至9的数字，让整个大九宫格每一列、每一行的数字都不重复。
于是就想到可以用二维数组试想一下，然后就试了试。。。

class Shudo
{
	private:
		int DataBasic[9][9];
		int DataResult[9][9];
		bool isSloved;
	public:
	    void PrintA(){
			for(int i=0;i<=8;i++){
				for(int j=0;j<=8;j++){
					cout<<DataBasic[i][j]<<" ";
				}
				cout<<"\n";
			}
		}
		void PrintB(){
				for(int i=0;i<=8;i++){
				for(int j=0;j<=8;j++){
					cout<<DataResult[i][j]<<" ";
				}
				cout<<"\n";
			}
			
		}
		Shudo(int Data[9][9])
		{
			memcpy(DataBasic,Data,sizeof(DataBasic));
			isSloved=false;
		}
		bool isVaild(int i,int j)
		{
			int t=DataBasic[i][j];
			int k;
			for(k=0;k<9;k++)
			{
				if((j!=k)&&(t==DataBasic[i][k]))
					return false;
				if((i!=k)&&(t==DataBasic[k][j]))
					return false;
			}
			int iData=(i/3)*3;
			int jData=(j/3)*3;
			int k1,k2;
			for(k1=iData;k1<iData+3;k1++)
			{
				for(k2=jData;k2<jData+3;k2++)
				{
					if((k2==j)&&(k1==i))
					continue;
					if(t==DataBasic[k1][k2])
					return false;
				}
			}
			return true;
		}
		bool ShuduSlove()
		{
			int i,j,k;
			for(i=0;i<9;i++)
			{
				for(j=0;j<9;j++)
				{
					if(DataBasic[i][j]==0)
					{
						for(k=1;k<10;k++)
						{
							DataBasic[i][j]=k;
							if(isVaild(i,j)&&ShuduSlove())
							{
								if(!isSloved)
								memcpy(DataResult,DataBasic,sizeof(DataBasic));
									isSloved=true;
									return true;
							}
							DataBasic[i][j]=0;
						}
						return false;
					}
				}
			}
			return true;
		}
 } ;

先写了一个数独类，及9行9列的二维数组，用DataBasic表示初始的题目，用DataResult表示最后完成的题目，方法是挨个深度优先遍历后往里填，用isVaild()方法验证行列是否合适，合适就把值填到DataResult中。
找了一个题目试了一下，把它打出来：

 int main(){
 int data[9][9]={
 	{0,4,2,0,6,3,0,0,9},
	{6,0,0,0,1,0,0,0,5},
	{3,0,0,0,2,0,4,8,0},
	{1,0,0,5,0,2,6,0,8},
	{4,0,0,0,0,7,0,0,1},
	{9,0,5,6,0,0,0,0,7},
	{0,3,6,0,5,0,0,0,2},
	{2,0,0,0,7,0,0,0,4},
	{7,0,0,2,9,0,8,5,0},
	};
Shudo shudu(data);
shudu.PrintA();
shudu.ShuduSlove();
cout<<"\n";
shudu.PrintB();
return 0;
}

能出结果，还凑活

以后挂个GUI，估计就能用了。。。

2016-10-05