C语言数独求解

发布网友 发布时间：2022-08-22 23:45

我来回答

共1个回答

热心网友 时间：2024-11-23 19:43

#include

/*数字0表示该位置为空，待填入数字
{0,0,4,6,0,2,0,9,1},
{2,1,0,9,8,4,0,5,6},
{9,0,0,0,7,1,4,2,0},
{1,2,5,0,6,0,3,4,7},
{4,7,6,0,0,0,9,8,5},
{8,3,9,0,4,0,1,6,2},
{0,9,1,2,5,0,0,0,4},
{5,8,0,4,1,6,0,3,9},
{6,4,0,3,0,7,5,0,0}};
*/

int data[9][9] = {
{0,7,0,2,6,0,9,0,0},
{3,0,0,0,0,8,0,0,7},
{0,9,0,0,5,7,0,0,0},
{5,0,0,0,0,0,0,7,0},
{0,4,7,3,1,2,8,5,0},
{0,8,0,0,0,0,0,0,1},
{0,0,0,8,2,0,0,4,0},
{7,0,0,6,0,0,0,0,2},
{0,0,4,0,3,9,0,8,0}};

void input()
{
int i,j;
for(i = 0;i < 9;i++)
for(j = 0;j < 9;j++)
scanf("%d",&data[i][j]);
}

void output()
{
int i,j;
for(i = 0;i < 9;i++)
{
for(j = 0;j < 9;j++)
printf("%d ",data[i][j]);
printf("\n");
}
printf("\n");
}

/*检查num是否可放置在3*3区域是否有冲突*/
int CheckSquare(int line,int col,int num)
{
int i = (line / 3) * 3;
int j = (col / 3) * 3;
int m,n;
for(m = i;m < i + 3;m++)
for(n = j;n < j + 3;n++)
if((data[m][n] == num) && !(m == line && n == col))
return 0;
return 1;
}

/*检查行冲突*/
int CheckLine(int line,int col,int num)
{
int i = 9;
while(i--)
if((data[line][i] == num) && (i != col))
return 0;
return 1;
}

/*检查列冲突*/
int CheckColumn(int line,int col,int num)
{
int i = 9;
while(i--)
if((data[i][col] == num) && (i != line))
return 0;
return 1;
}

/*检查i行j列是否可放置num*/
int Check(int i,int j,int num)
{
return CheckSquare(i,j,num) && CheckLine(i,j,num) && CheckColumn(i,j,num);
}

/*检查是否完成*/
int IsDone()
{
int i,j;
for(i = 0;i < 9;i++)
for(j = 0;j < 9;j++)
if(!Check(i,j,data[i][j]) || (data[i][j] == 0))
return 0;
return 1;
}

void Calc()
{
int i,j,x;
if(IsDone())
{
output();
return;
}
for(i = 0;i < 9;i++)
{
for(j = 0;j < 9;j++)
{
if(data[i][j] == 0)
{
for(x = 1; x <= 9;x++)
{
if(Check(i,j,x))
{
data[i][j] = x;
Calc();
}
}
if(x == 10)
{
data[i][j] = 0;
return ;
}
}
}
}
}

int main()
{
// input();
Calc();
output();

return 0;
}