shudu.cpp

数独求解 每行和每列和每小格为1到9的数字,用程序求解的算发.

//-------数独-------
//行和列和每小格为1到9的数字,用程序求解.
//------------------------------------------
#include "stdio.h"
#include "conio.h"
void main()
{
	int shudu[]={
		0,0,0,	0,0,5,	0,9,0,
		0,0,6,	1,0,0,	0,0,3,
		0,1,4,	8,9,0,	0,0,0,

		9,6,0,	0,0,0,	0,0,0,
		0,0,0,	0,2,0,	0,0,0,
		0,0,0,	0,0,0,	0,7,2,

		0,0,0,	0,1,8,	6,4,0,
		7,0,0,	0,0,9,	2,0,0,
		0,2,0,	3,0,0,	0,0,0,
	};
/*
		0,0,0,	0,0,0,	0,0,0,
		0,0,0,	0,0,0,	0,0,0,
		0,0,0,	0,0,0,	0,0,0,
//l2
		4,0,0,	7,0,1,	0,0,6,
		7,2,0,	0,0,0,	0,8,9,
		0,0,6,	0,0,0,	5,0,0,

		0,9,0,	1,0,5,	0,6,0,
		0,0,0,	9,3,8,	0,0,0,
		0,7,0,	6,0,4,	0,5,0,

		0,0,7,	0,0,0,	6,0,0,
		1,3,0,	0,0,0,	0,4,8,
		6,0,0,	2,0,3,	0,0,5,
//l3
		0,0,0,	0,4,0,	7,0,0,
		0,0,7,	0,0,1,	0,5,0,
		0,0,8,	3,0,2,	0,0,0,

		1,0,0,	0,0,0,	0,0,0,
		0,4,5,	6,0,3,	9,2,0,
		0,0,0,	0,0,0,	0,0,6,

		0,0,0,	9,0,5,	2,0,0,
		0,9,0,	4,0,0,	3,0,0,
		0,0,2,	0,1,0,	0,0,0,

//l4
		0,0,0,	0,0,5,	0,9,0,
		0,0,6,	1,0,0,	0,0,3,
		0,1,4,	8,9,0,	0,0,0,

		9,6,0,	0,0,0,	0,0,0,
		0,0,0,	0,2,0,	0,0,0,
		0,0,0,	0,0,0,	0,7,2,

		0,0,0,	0,1,8,	6,4,0,
		7,0,0,	0,0,9,	2,0,0,
		0,2,0,	3,0,0,	0,0,0,

*/
	int sdTmp[8100],sdIndex,sdFlag,sdError;
	int num[]={0,0,0,0,0,0,0,0,0,0};
	int i,j,c,l,m,mm,ll,cc,t,coutL;

	i=0;
	clrscr();
	while(i<81){
		if(shudu[i]==0){
			l=(i/9)*9;
			c=i%9;
			m=(i/27)*27+(c/3)*3;
			for(j=1;j<10;j++) num[j]=0;

			for(j=0;j<9;j++){
				if(shudu[l+j]) num[shudu[l+j]]=1;
			}
			for(j=0;j<9;j++){
				if(shudu[j*9+c]) num[shudu[j*9+c]]=1;
			}
			for(j=0;j<9;j++){
				if(shudu[m+(j/3)*9+j%3]) num[shudu[m+(j/3)*9+j%3]]=1;
			}
			mm=0;
			for(j=1;j<10;j++){
				if(num[j]) mm++;
			}
			if(mm==8){
				for(j=1;j<10;j++)
				if(num[j]==0){
					shudu[i]=j;
					i=0;
					break;
				}
			}else i++;
		}else i++;
	}

//====================================================
	i=0;
	while(i<81){
		if(shudu[i]==0){
			l=(i/9)*9;
			c=i%9;
			m=(i/27)*27+(c/3)*3;
			for(j=1;j<10;j++) num[j]=0;

			for(j=0;j<9;j++){
				if(shudu[l+j]) num[shudu[l+j]]=1;
			}
			for(j=0;j<9;j++){
				if(shudu[j*9+c]) num[shudu[j*9+c]]=1;
			}
			for(j=0;j<9;j++){
				if(shudu[m+(j/3)*9+j%3]) num[shudu[m+(j/3)*9+j%3]]=1;
			}
			mm=0;
			for(j=1;j<10;j++){
				if(num[j]) mm++;
			}
			if(mm==8){
				for(j=1;j<10;j++)
				if(num[j]==0){
					shudu[i]=j;
					i=0;
					break;
				}
			}else if(mm>=1){
				for(j=1;j<10;j++)
				if(num[j]==0){
					ll=(l/27)*27;
					cc=(c/3)*3;
					coutL=0;
					if(l!=ll){
						if((shudu[ll+cc])&&(shudu[ll+cc+1])&&(shudu[ll+cc+2])) coutL++;
						else{
							for(t=0;t<9;t++) if(shudu[ll+t]==j){ coutL++; break; }
						}
					}
					if(l!=ll+9){
						if((shudu[ll+cc+9])&&(shudu[ll+cc+10])&&(shudu[ll+cc+11])) coutL++;
						else{
							for(t=9;t<18;t++) if(shudu[ll+t]==j){ coutL++; break; }
						}
					}
					if(l!=ll+18){
						if((shudu[ll+cc+18])&&(shudu[ll+cc+19])&&(shudu[ll+cc+20])) coutL++;
						else{
							for(t=18;t<27;t++) if(shudu[ll+t]==j){ coutL++; break; }
						}
					}
					if(coutL==2){
						if(c!=cc){
							if(shudu[l+cc]) coutL++;
							else {
								for(t=0;t<9;t++) if(shudu[cc+t*9]==j){ coutL++;  break; }
							}
						}
						if(c!=cc+1){
							if(shudu[l+cc+1]) coutL++;
							else {
								for(t=0;t<9;t++) if(shudu[cc+t*9+1]==j){ coutL++; break; }
							}
						}
						if(c!=cc+2){
							if(shudu[l+cc+2]) coutL++;
							else{
								for(t=0;t<9;t++) if(shudu[cc+t*9+2]==j){ coutL++; break; }
							}
						}
						if(coutL==4) break;
					}
					coutL=0;
					if(c!=cc){
						if((shudu[ll+cc])&&(shudu[ll+cc+9])&&(shudu[ll+cc+18])) coutL++;
						else {
							for(t=0;t<9;t++) if(shudu[cc+t*9]==j){ coutL++;  break; }
						}
					}
					if(c!=cc+1){
						if((shudu[ll+cc+1])&&(shudu[ll+cc+10])&&(shudu[ll+cc+19])) coutL++;
						else {
							for(t=0;t<9;t++) if(shudu[cc+t*9+1]==j){ coutL++; break; }
						}
					}
					if(c!=cc+2){
						if((shudu[ll+cc+2])&&(shudu[ll+cc+11])&&(shudu[ll+cc+20])) coutL++;
						else{
							for(t=0;t<9;t++) if(shudu[cc+t*9+2]==j){ coutL++; break; }
						}
					}
					if(coutL==2){
						if(l!=ll){
							if(shudu[ll+c]) coutL++;
							else {
								for(t=0;t<9;t++) if(shudu[ll+t]==j){ coutL++; break; }
							}
						}
						if(l!=ll+9){
							if(shudu[ll+c+9]) coutL++;
							else {
								for(t=9;t<18;t++) if(shudu[ll+t]==j){ coutL++; break; }
							}
						}
						if(l!=ll+18){
							if(shudu[ll+c+18]) coutL++;
							else{
								for(t=18;t<27;t++) if(shudu[ll+t]==j){ coutL++; break; }
							}
						}
						if(coutL==4) break;
					}

				}
				if(coutL==4){
					shudu[i]=j;
					i=0;
				}else i++;
			}else i++;
		}else i++;
	}

//====================================================
	sdIndex=0;
	sdError=0;
	i=0;
	while(i<81){
		if(shudu[i]==0){
			l=(i/9)*9;
			c=i%9;
			m=(i/27)*27+(c/3)*3;
			for(j=1;j<10;j++) num[j]=0;

			for(j=0;j<9;j++){
				if(shudu[l+j]) num[shudu[l+j]]=1;
			}
			for(j=0;j<9;j++){
				if(shudu[j*9+c]) num[shudu[j*9+c]]=1;
			}
			for(j=0;j<9;j++){
				if(shudu[m+(j/3)*9+j%3]) num[shudu[m+(j/3)*9+j%3]]=1;
			}
			mm=0;
			for(j=1;j<10;j++){
				if(num[j]) mm++;
			}
			if(mm==9){
				sdError++;
				if(sdIndex==0) break;
				sdIndex--;
				for(j=0;j<81;j++) shudu[j]=sdTmp[sdIndex*81+j];
				i=0;
			}else if(mm==8){
				for(j=1;j<10;j++)
				if(num[j]==0){
					shudu[i]=j;
					i=0;
					break;
				}
			}else if(mm>=7){
				for(j=1;j<10;j++)
				if(num[j]==0){
					ll=(l/27)*27;
					cc=(c/3)*3;
					coutL=0;
					if(l!=ll){
						if((shudu[ll+cc])&&(shudu[ll+cc+1])&&(shudu[ll+cc+2])) coutL++;
						else{
							for(t=0;t<9;t++) if(shudu[ll+t]==j){ coutL++; break; }
						}
					}
					if(l!=ll+9){
						if((shudu[ll+cc+9])&&(shudu[ll+cc+10])&&(shudu[ll+cc+11])) coutL++;
						else{
							for(t=9;t<18;t++) if(shudu[ll+t]==j){ coutL++; break; }
						}
					}
					if(l!=ll+18){
						if((shudu[ll+cc+18])&&(shudu[ll+cc+19])&&(shudu[ll+cc+20])) coutL++;
						else{
							for(t=18;t<27;t++) if(shudu[ll+t]==j){ coutL++; break; }
						}
					}
					if(coutL==2){
						if(c!=cc){
							if(shudu[l+cc]) coutL++;
							else {
								for(t=0;t<9;t++) if(shudu[cc+t*9]==j){ coutL++;  break; }
							}
						}
						if(c!=cc+1){
							if(shudu[l+cc+1]) coutL++;
							else {
								for(t=0;t<9;t++) if(shudu[cc+t*9+1]==j){ coutL++; break; }
							}
						}
						if(c!=cc+2){
							if(shudu[l+cc+2]) coutL++;
							else{
								for(t=0;t<9;t++) if(shudu[cc+t*9+2]==j){ coutL++; break; }
							}
						}
						if(coutL==4) break;
					}
					coutL=0;
					if(c!=cc){
						if((shudu[ll+cc])&&(shudu[ll+cc+9])&&(shudu[ll+cc+18])) coutL++;
						else {
							for(t=0;t<9;t++) if(shudu[cc+t*9]==j){ coutL++;  break; }
						}
					}
					if(c!=cc+1){
						if((shudu[ll+cc+1])&&(shudu[ll+cc+10])&&(shudu[ll+cc+19])) coutL++;
						else {
							for(t=0;t<9;t++) if(shudu[cc+t*9+1]==j){ coutL++; break; }
						}
					}
					if(c!=cc+2){
						if((shudu[ll+cc+2])&&(shudu[ll+cc+11])&&(shudu[ll+cc+20])) coutL++;
						else{
							for(t=0;t<9;t++) if(shudu[cc+t*9+2]==j){ coutL++; break; }
						}
					}
					if(coutL==2){
						if(l!=ll){
							if(shudu[ll+c]) coutL++;
							else {
								for(t=0;t<9;t++) if(shudu[ll+t]==j){ coutL++; break; }
							}
						}
						if(l!=ll+9){
							if(shudu[ll+c+9]) coutL++;
							else {
								for(t=9;t<18;t++) if(shudu[ll+t]==j){ coutL++; break; }
							}
						}
						if(l!=ll+18){
							if(shudu[ll+c+18]) coutL++;
							else{
								for(t=18;t<27;t++) if(shudu[ll+t]==j){ coutL++; break; }
							}
						}
						if(coutL==4) break;
					}

				}
				if(coutL==4){
					shudu[i]=j;
					i=0;
				}else {
					sdFlag=0;
					for(j=1;j<10;j++)
					if(num[j]==0){
						if(sdFlag==0){
							shudu[i]=j;
							for(m=0;m<81;m++) sdTmp[sdIndex*81+m]=shudu[m];
							sdIndex++;
							sdFlag=1;
						}else{
							shudu[i]=j;
							i=0;
							break;
						}
					}
				}
			}else i++;
		}else i++;
	}

	for(i=0;i<81;i++){
		printf("%3d",shudu[i]);
		if((i+1)%9==0) printf("\n");
		else if((i+1)%3==0) printf("   ");
		if((i+1)%27==0) printf("\n");
	}
	printf("%d\n",sdError);

}

/*	for(i=0;i<81;i++){
		printf("%3d",shudu[i]);
		if((i+1)%9==0) printf("\n");
		else if((i+1)%3==0) printf("   ");
		if((i+1)%27==0) printf("\n");
	}*/