|
|
#include<stdio.h>
|
|
|
int main()
|
|
|
{
|
|
|
bool fill(int board_[9][9]);
|
|
|
int JudgeMent(int board[9][9]);
|
|
|
bool judge = 1;
|
|
|
int result = 0;
|
|
|
int b_0[9][9];
|
|
|
for ( int i=0;i<9;i++)
|
|
|
{
|
|
|
for(int j=0;j<9;j++)
|
|
|
{
|
|
|
scanf("%d",&b_0[i][j]);
|
|
|
}
|
|
|
|
|
|
}//读取数组
|
|
|
|
|
|
|
|
|
judge=JudgeMent(b_0);
|
|
|
if(judge==1)
|
|
|
{
|
|
|
|
|
|
if(!fill(b_0))
|
|
|
{
|
|
|
printf("No solution");
|
|
|
}
|
|
|
else
|
|
|
{
|
|
|
printf("|-----------------------|\n");
|
|
|
for(int i=0;i<9;i++)
|
|
|
{
|
|
|
printf("| ");
|
|
|
for (int j=0;j<9;j++)
|
|
|
{
|
|
|
printf("%d ",b_0[i][j]);
|
|
|
if(j==2||j==5)printf("| ");
|
|
|
if(j==8) printf("|\n");
|
|
|
}
|
|
|
if(i==2||i==5||i==8)printf("|-----------------------|\n");
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
|
|
|
return 0;
|
|
|
|
|
|
}
|
|
|
bool fill(int board_[9][9])
|
|
|
{
|
|
|
bool isValid(int board[9][9], int row, int col, int k);
|
|
|
int JudgeMent(int board[9][9]);
|
|
|
int Judgement(int board[9][9]);
|
|
|
for ( int i=0;i<9;i++)
|
|
|
{
|
|
|
for(int j=0;j<9;j++)
|
|
|
{
|
|
|
if(board_[i][j]!=0)
|
|
|
{
|
|
|
//b_0[i][j]++;
|
|
|
continue;
|
|
|
}
|
|
|
for(int k=1;k<=9;k++)
|
|
|
{
|
|
|
if(isValid( board_, i, j, k)) {
|
|
|
board_[i][j] = k;
|
|
|
/* 判断下一层递归之后是否找到一种解法，是则返回true */
|
|
|
if (fill(board_))
|
|
|
{
|
|
|
return true;
|
|
|
}
|
|
|
/* 回溯，将当前位置清零 */
|
|
|
board_[i][j] = 0;
|
|
|
}
|
|
|
|
|
|
}
|
|
|
return 0;
|
|
|
}
|
|
|
|
|
|
}
|
|
|
return 1;
|
|
|
}
|
|
|
|
|
|
int JudgeMent(int board[9][9])
|
|
|
{
|
|
|
int parallel[9][9]={0};//用于计数，计算每行1-9出现的次数
|
|
|
int vertical[9][9]={0}; //用于计数，计算每列1-9出现的次数
|
|
|
int a[9][9]={0}; //用于计数，计算每块1-9出现的次数
|
|
|
int element,line=0, column=0, block =0;
|
|
|
int i,j,k;//用于控制循环
|
|
|
int err01,err02,err12,err11,err21,err22;//记录数据出错的位置
|
|
|
bool judgement=0;
|
|
|
printf("The original Sudoku matrix: \n") ;
|
|
|
printf("|-----------------------|\n");
|
|
|
for(i=0;i<9;i++)
|
|
|
{
|
|
|
printf("| ");
|
|
|
for ( j=0;j<9;j++)
|
|
|
{
|
|
|
printf("%d ",board[i][j]);
|
|
|
if(j==2||j==5)printf("| ");
|
|
|
if(j==8) printf("|\n");
|
|
|
}
|
|
|
if(i==2||i==5||i==8)printf("|-----------------------|\n");
|
|
|
}//输出数组；
|
|
|
|
|
|
for ( i=0;i<9;i++)
|
|
|
{
|
|
|
for( j=0;j<9;j++)
|
|
|
{
|
|
|
if(board[i][j]>=1&&board[i][j]<=9)
|
|
|
{
|
|
|
element=board[i][j];
|
|
|
parallel[i][element-1]++;
|
|
|
}
|
|
|
|
|
|
}
|
|
|
|
|
|
}//统计各行各个数字出现的次数
|
|
|
for ( i=0;i<9;i++)
|
|
|
{
|
|
|
for( j=0;j<9;j++)
|
|
|
{
|
|
|
if(parallel[i][j]>1)
|
|
|
{
|
|
|
line=parallel[i][j];
|
|
|
err01=j+1;
|
|
|
err02=i+1;
|
|
|
goto end;
|
|
|
}
|
|
|
}
|
|
|
|
|
|
}//判断行
|
|
|
for ( i=0;i<9;i++)
|
|
|
{
|
|
|
for( j=0;j<9;j++)
|
|
|
{
|
|
|
if(board[i][j]>=1&&board[i][j]<=9)
|
|
|
{
|
|
|
element=board[i][j];
|
|
|
vertical[element-1][j]++;
|
|
|
}
|
|
|
|
|
|
}
|
|
|
|
|
|
}
|
|
|
for ( i=0;i<9;i++)
|
|
|
{
|
|
|
for( j=0;j<9;j++)
|
|
|
{
|
|
|
if(vertical[i][j]>1)
|
|
|
{
|
|
|
column=vertical[i][j];
|
|
|
err11=j+1;
|
|
|
err12=i+1;
|
|
|
goto end;
|
|
|
}
|
|
|
}
|
|
|
|
|
|
}
|
|
|
//判断列
|
|
|
for (i=0;i<9;i++)
|
|
|
{
|
|
|
for(j=0;j<9;j++)
|
|
|
{
|
|
|
if(board[i][j]>=1&&board[i][j]<=9)
|
|
|
{
|
|
|
element=board[i][j];
|
|
|
k=i/3*3+j/3;
|
|
|
a[k][element-1]++;
|
|
|
}
|
|
|
|
|
|
}
|
|
|
}
|
|
|
for ( i=0;i<9;i++)
|
|
|
{
|
|
|
for( j=0;j<9;j++)
|
|
|
{
|
|
|
if(a[i][j]>1)
|
|
|
{
|
|
|
block=a[i][j];
|
|
|
err21=i+1;
|
|
|
err22=j+1;
|
|
|
goto end;
|
|
|
}
|
|
|
}
|
|
|
|
|
|
}
|
|
|
//判断块
|
|
|
end:
|
|
|
if(line>1)
|
|
|
{
|
|
|
printf("False:Invalid initial Sudoku matrix!\n");
|
|
|
printf("The number %d in the line %d has been used!",err01,err02);
|
|
|
}
|
|
|
else if(column>1)
|
|
|
{
|
|
|
printf("False:Invalid initial Sudoku matrix!\n");
|
|
|
printf("The number %d in the column %d has been used!",err12,err11);
|
|
|
}
|
|
|
else if(block>1)
|
|
|
{
|
|
|
printf("False:Invalid initial Sudoku matrix!\n");
|
|
|
printf("The number %d in the block %d has been used!",err22,err21);
|
|
|
}
|
|
|
else
|
|
|
{
|
|
|
printf("True:Valid initial Sudoku matrix!\n");
|
|
|
judgement=1;
|
|
|
}
|
|
|
return judgement;
|
|
|
|
|
|
}
|
|
|
bool isValid(int board[9][9], int row, int col, int k) {
|
|
|
// 判断当前行是否有重复元素
|
|
|
for (int i = 0; i < 9; i++) {
|
|
|
if (board[i][col] == k) {
|
|
|
return false;
|
|
|
}
|
|
|
}
|
|
|
// 判断当前列是否有重复元素
|
|
|
for (int j = 0; j < 9; j++) {
|
|
|
if (board[row][j] == k) {
|
|
|
return false;
|
|
|
}
|
|
|
}
|
|
|
// 计算当前9宫格左上角的位置
|
|
|
int startRow = (row / 3) * 3;
|
|
|
int startCol = (col / 3) * 3;
|
|
|
//判断当前元素所在九宫格是否有重复元素
|
|
|
for (int i = startRow; i < startRow + 3; i++) {
|
|
|
for (int j = startCol; j < startCol + 3; j++) {
|
|
|
if (board[i][j] == k) {
|
|
|
return false;
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
//满足条件，返回true
|
|
|
return true;
|
|
|
}
|
|
|
|
