思路
利用穷举法
C语言代码
#include<stdio.h>
//负责输出二维数组的一行，并给数组添加格式
void row_output(int i, int x[9][9])
{
int j, flag;
for (j = 0; j < 9; j++)
{
//检查是否为3的倍数
flag = (j + 1) % 3;
//当是3的倍数时加入两个空格
if (flag == 0)
printf("%d ", x[i][j]);
//否则加入一个空格
else
printf("%d ", x[i][j]);
}
}
//负责按照九宫格的形式将数组输出
void output(int x[9][9])
{
int i, flag;
for (i = 0; i < 9; i++)
{
//检查是否为3的倍数
flag = (i + 1) % 3;
row_output(i, x);
//当是3的倍数时加入两个空行
if (flag == 0)
printf("\n\n");
//否则加入一个空行
else
printf("\n");
}
}
//validate函数负责检查下x[i][j]是否为可行的值
int validate(int x[9][9], int i, int j, int num)
{
int row, column;
int isPossible = 1;
//遍历第i行查询是否有重复的值
for (column = 0; column < 9; column++)
{
if (num == x[i][column]) isPossible *= 0;
else isPossible *= 1;
}
//遍历第j列查询是否有重复的值
for (row = 0; row < 9; row++)
{
if (num == x[row][j]) isPossible *= 0;
else isPossible *= 1;
}
//遍历x[i][i]所在宫(box)查询是否有重复的值
int box_i, box_j;
//定位宫的位置
int offset_x, offset_y;
//计算x方向(即j序号增加方向)偏移量
offset_x = j - j % 3;
//计算y方向(即i序号增加方向)偏移量
offset_y = i - i % 3;
for (box_i = 0; box_i < 3; box_i++)
{
for (box_j = 0; box_j < 3; box_j++)
{
//将box_i,box_j修正到正确的九宫格
if (num == x[box_i + offset_y][box_j + offset_x]) isPossible *= 0;
else isPossible *= 1;
}
}
//验证无误返回1，否则返回0
return isPossible;
}
void solve_soduku(int x[9][9])
{
int i, j, num, flag=0;
//新建一个二维数组负责记录不可更改数字（即开始时就被填入的数字）的位置
int can_not_modify[9][9] = { 0 };
for (i = 0; i < 9; i++)
{
for (j = 0; j < 9; j++)
{
if (x[i][j] != 0) can_not_modify[i][j] = 1;
}
}
//初始化i和j
i = 0;
j = 0;
//遍历九宫格，从x[0][0]开始尝试
while (i < 9)
{
while (j < 9)
{
//判断是否为上一行试错跳转而来
start:if (flag == 1 && j == -1)
{
i--;
j = 8;
goto start;
}
//判断是否为试错跳转而来且当前值不可修改
else if (flag == 1 && can_not_modify[i][j] == 1)
{
//继续返回上一层
j--;
continue;
}
//判断当前格子是否不可修改
else if (can_not_modify[i][j] == 1)
{
j++;
continue;
}
//开始尝试
else
{
num = x[i][j];
//若当前格子还未赋值，即不是由上一次试错跳转而来，从1开始尝试
if (num == 0) num = 1;
//若flag==1即是由上一次试错而来，从上一次错误的值+1继续尝试
else if (flag == 1) num = x[i][j] + 1;
//初始化跳转标识的值
flag = 0;
//从num开始向后逐个尝试
for (; num <= 10; num++)
{
//用validate函数判断尝试的值是否可行
//如果可行将当前格子的值变为num
if (validate(x, i, j, num) == 1 && num < 10)
{
x[i][j] = num;
j++;
break;
}
//如果到9还没有可行的值填入，说明前面有错，初始当前值为0，返回上一次尝试
else if (num == 10)
{
x[i][j] = 0;
j--;
//打上跳转标识flag=1
flag = 1;
break;
}
}
}
}
//一行填满从下一行第一个继续尝试
j = 0;
i++;
}
}
void main()
{
int i, j;
char temp;
int soduku[9][9];
printf("数独求解V0.1 by:Clysto\n2018/6/20\n\n\n");
printf("请输入您要求解的数独:\n");
printf(" 123456789\n");
for (i = 0; i < 9; i++)
{
printf("%d:", i + 1);
for (j = 0; j < 10; j++)
{
temp = getchar();
if (j<9) soduku[i][j] = temp - '0';
}
}
printf("\n您输入的数独是:\n");
output(soduku);
solve_soduku(soduku);
printf("结果是:\n");
output(soduku);
}
