#include<stdio.h>
#include<stdlib.h>
//Error函式用于例外情況處理
void Error(char * s)
{
printf("%s",s);
exit (1);
}
//判斷將填入的數n，是否是所在行和列的唯一數
int Ranks(int (*a)[9],int i,int j,int n)
{
int x;
if(i<0||i>8||j<0||j>8||n<1||n>9) Error("引數錯誤!");
else
{
for(x=0;x<9;x++)
{
if(n==a[x][j]||n==a[i][x]) return (0);
}
return (1);
}
}
//區域判斷函式,用于遍歷3*3九宮格時判斷列(j)的起始位置
int Reg_judge(int x)
{
if(x<3) return 0;
if(x>2&&x<6) return 3;
if(x>5) return 6;
}
//判斷將填入的數n,是否是所在3*3九宮格中的唯一數
int Nine_Palaces(int (*a)[9],int i,int j,int n)
{
int x,y,k,t;
if(i<0||i>8||j<0||j>8||n<1||n>9) Error("引數錯誤!");
else
{
if(i<3)
{
x=0; y=Reg_judge(j);
}
else
{
if(i<6)
{
x=3; y=Reg_judge(j);
}
else
{
x=6; y=Reg_judge(j);
}
}
}
for(k=x;k<x+3;k++)
{
for(t=y;t<y+3;t++)
{
if(n==a[k][t]) return (0);
}
}
return (1);
}
int main()
{
char c;
int a[9][9]={0};
int b[9][9]={0}; //用于數獨初始非零值備份
int i,j,x,k;
long count=1;
int *p_b=b[0];
a[0][1]=9;a[0][5]=2;a[0][8]=1;
a[1][4]=6;a[1][8]=2;
a[2][6]=4;
a[3][0]=6;a[3][4]=8;
a[4][1]=2;
a[5][2]=1;a[5][3]=7;a[5][5]=4;
a[6][0]=3;a[6][1]=6;
a[7][2]=7;a[7][6]=5;
a[8][0]=9;a[8][1]=5;a[8][5]=7;a[8][8]=8;
//輸出a陣列的初始狀態
printf("數獨初始狀態\n");
for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
{
printf("%4d",a[i][j]);
}
printf("\n\n");
}
printf("=======================================\n");
//填入方案
for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
{
if(a[i][j]==0)
{
for(x=1;x<=9;x++)
{Again: //goto陳述句標簽
if(Ranks(a,i,j,x)&&Nine_Palaces(a,i,j,x))
{
a[i][j]=x; break;
}
}
if(x==10) //如果a[i][j]沒有被賦值1~9的任何數
{Again1: //goto陳述句標簽
j-=1; //往回退一步
if(j==-1)
{
j=8;i-=1; if(i==-1) Error("\n數獨解決方案已盡或無解!");
}
if(p_b[i*9+j]==0) //退一步不是初始非零值
{
if(a[i][j]==9)
{
a[i][j]=0; //是9則賦值為0
goto Again1; //跳轉至標簽Again1,繼續退一步
}
else //不是初始非零值且不是9
{
x=(a[i][j]+1); //將此值加1賦給x
a[i][j]=0; //跳轉前需先將此值歸零
goto Again; //跳轉至判斷函式處，判斷此值是否成立
}
}
else //退一步是初始非零值
{
goto Again1; //跳轉至標簽Again1處,繼續退一步
}
}
}
else
{
b[i][j]=a[i][j]; //將初始非零值備份
}
}
}
//輸出填入數字后數獨游戲的結果
printf("\n數獨解決方案No.%ld\n",count++);
for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
{
printf("%4d",a[i][j]);
}
printf("\n\n");
}
printf("繼續請輸入Y 或 y 否則輸入任意鍵結束");
//求其他解的思想是這樣的:設程式上次求出的解最后填入的那個數不成立，讓其往前繼續搜索其他方案,直至無解
c='y'; // c=getchar();getchar(); //如果手動輸入將c='y'; 洗掉
if(c=='Y'||c=='y')
{
i=j=8;
if(p_b[i*9+j]==0) //如果最后一個數不是初始非零值
{
a[i][j]=0; goto Again1;
}
else //最后一個數是初始非零值
{
goto Again1;
}
}
return 0;
}
uj5u.com熱心網友回復：
有人說嚴謹的數獨只應有且只有一個解，如果有朋友手上有一個解的盤面，麻煩留言，我想用這程式跑一下，看能不能解出來，能解的話看看效率如何轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/146240.html
標籤：C語言
上一篇：getw（）函式使用問題