求教，c实现一个数独游戏计算

长风起点 2012-07-03 08:48:06

用c怎么实现编程？具体的算法写写，这个题目说是芬兰数学家因卡拉花费3个月设计出了世界上迄今难度最大的数独游戏，而且它只有一个答案。

...全文

287 6 打赏收藏转发到动态举报

写回复

用AI写文章

6 条回复

切换为时间正序

请发表友善的回复…

发表回复

zunceng 2012-07-03

打赏
举报

其实数独和8皇后一样可以遍深搜历解的

PANHL97 2012-07-03

打赏
举报

8 1 2 7 5 3 6 4 9
9 4 3 6 8 2 1 7 5
6 7 5 4 9 1 2 8 3
1 5 4 2 3 7 8 9 6
3 6 9 8 4 5 7 2 1
2 8 7 1 6 9 5 3 4
5 2 1 9 7 4 3 6 8
4 3 8 5 2 6 9 1 7
7 9 6 3 1 8 4 5 2
请按任意键继续. . .
计算结果

PANHL97 2012-07-03

打赏
举报



#include <stdio.h>

#include <stdlib.h>



int getmap(int maps[],int data)

{

	int i;

	for(i=0;i<10;i++)

		if(maps[i]==data)

			return i;

}



int chkdata(int data[][9],int x,int y)

{

	int i;

	int sum1=0,sum2=0,sum3=0,or1=0,or2=0,or3=0;

	

	for(i=0;i<9;i++)

	{

		sum1+=data[i][y];

		or1|=data[i][y];

		sum2+=data[x][i];

		or2|=data[x][i];

		sum3+=data[x-x%3+i%3][y-y%3+i/3];

		or3|=data[x-x%3+i%3][y-y%3+i/3];

	}

	if((sum1!=or1) || (sum2!=or2) ||(sum3!=or3))

		return 0;

	return 1;

}



void initdata(int datain[][9],int dataout[][9],int maps[],int handlenum[][9])

{

	int i,j;

	for(i=0;i<9;i++)

		for(j=0;j<9;j++)

		{

			dataout[i][j]=maps[datain[i][j]];

			if(datain[i][j]==0)

				handlenum[i][j]=-1;

			else

				handlenum[i][j]=0;

		}

}



int getdata(int data[][9],int x,int y)

{

	int sum=0,i;

	for(i=0;i<9;i++)

	{

		sum|=data[i][y];

		sum|=data[x][i];

		sum|=data[x-x%3+i%3][y-y%3+i/3];

	}

	return 511&(sum^511);

}



int calhandle(int datahandle[][9][10],int handlenum[][9],int maps[],int x,int y,int data)

{

	int i=0,j,k;

	for(j=1;j<10;j++)

	{

		k=maps[j]&data;

		if(k!=0)

			datahandle[x][y][i++]=maps[j];

	}

	handlenum[x][y]=i;

}

	



main()

{

	int datain[9][9]={

		{8,0,0,0,0,0,0,0,0},

		{0,0,3,6,0,0,0,0,0},

		{0,7,0,0,9,0,2,0,0},

		{0,5,0,0,0,7,0,0,0},

		{0,0,0,0,4,5,7,0,0},

		{0,0,0,1,0,0,0,3,0},

		{0,0,1,0,0,0,0,6,8},

		{0,0,8,5,0,0,0,1,0},

		{0,9,0,0,0,0,4,0,0}};

	int maps[10]={0,1,2,4,8,16,32,64,128,256};

	int datamap[9][9];

	int datahandle[9][9][10];

	int handlenum[9][9];

	int findnum[9][9]={0};

	int i,j,k;



	initdata(datain,datamap,maps,handlenum);

	for(i=0;i<9;i++)

		for(j=0;j<9;j++)

			if(handlenum[i][j]!=0)

				calhandle(datahandle,handlenum,maps,i,j,getdata(datamap,i,j));

	for(i=0;i<9;i++)

		for(j=0;j<9;j++)

		{

			if(handlenum[i][j]==0)

				continue;

			datamap[i][j]=datahandle[i][j][findnum[i][j]++];

			while(!chkdata(datamap,i,j))

			{

				if(findnum[i][j]!=handlenum[i][j])

					datamap[i][j]=datahandle[i][j][findnum[i][j]++];

				else

				{

					findnum[i][j]=0;

					datamap[i][j]=0;

					j--;

					if(j<0)

					{

						j=8;

						i--;

					}

					while(handlenum[i][j]==0 || (findnum[i][j]==handlenum[i][j] && handlenum[i][j]!=0))

					{

						if(handlenum[i][j]!=0)

						{

							findnum[i][j]=0;

							datamap[i][j]=0;

						}

						j--;

						if(j<0)

						{

							j=8;

							i--;

						}

						if(i<0)

						{

							printf("false");

							i=100;

							j=100;

							break;

						}

					}

					if(i==100)

						break;

					datamap[i][j]=datahandle[i][j][findnum[i][j]++];

					continue;

				}

				if(i==100)

					break;

			}

		}



	system("cls");

	printf("\n");

	if(i!=100 && j!=100)

	{

		for(i=0;i<9;i++)

		{

			for(j=0;j<9;j++)

				printf("%3d ",getmap(maps,datamap[i][j]));

			printf("\n");

		}

	}

	system("pause");

}