0 0 8 0 6 0 0 0 0
3 0 0 4 7 5 0 0 0
2 4 5 0 0 0 1 0 0
6 2 0 9 4 7 0 0 0
9 1 0 0 0 0 0 2 7
0 0 0 1 2 6 0 9 3
0 0 6 0 0 0 2 5 8
0 0 0 3 8 4 0 0 9
0 0 0 0 5 0 3 0 0
【解题思路】(以上面的题目为例)：
1、首先根据行、列、以及3×3的小方格内数字不能重复的规则，对空白表格都扫描一遍；得到每个表格的可选值。
1.1 例如，首先对第一行第一列表格找可选值：
1.1.1 根据行规则排除掉6、8
1.1.2 根据列规则排除掉2、3、6、9
1.1.3 根据3×3小方格([0][0] 到[2][2]之间方形区域)的规则排除掉2、3、4、5、8
1.1.4 得到表格[0][0]的总共可以排除掉的填充值为：2、3、4、5、6、8、9，所以可选值就为：1、7。
另外：对于第一行第三个表格，已经有固定值。
2、遍历完了之后，如果某个表格的可选值只有一个，就把这个值标识成这个表格的固定值。根据第1步的结果，把所有可以确定的都确定了。
3、如果第2步有新的固定值，就重复执行第1步，直到没有可以唯一确定的了。
3.1 如果所有的表格都有唯一的取值，那么就找到了可行解，程序退出。
4、对于有些简单的题目，经过前3步就得到可行解。 如果前3步找不到解，那么到了这步就需要做假设，即剩下的空白表格的目前可选取值可能不止一个。
4.1 对需要做假设的表格进行排序，按照可选值的个数排序。 （例如，可选值只有两个的排在最前面）
4.2 对可选值最少的进行假设取值，顺序尝试每个取值。 如果取了某个值，然后就进入下次递归（跳到第一步）。 （4.1中不排序也可以，只需要找出最小值就可以）
4.2.2 如果返回成功，假设成立，成功退出；
4.2.3 如果返回失败，假设不成立，失败退出；
4.2.4 因为是递归，直到退出到最高层的假设，如果一直是假设成立就成功退出，得到可行解。
【实现思路】
数独的解法，代码写的比较粗糙，先保留着，递归版本。
百科了之后，说合格的数独应该是有解，并且只能有唯一解，那么看来出题的算法要更复杂些，呵呵。
实现中用了gTimes简单的统计了递归次数，如果递归太多就认为无解了。
另外程序的递归也不能太深，要不会溢出或什么的报错，递归的程序可以转换成非递归的，需要用循环，可能还需要借助栈结构。
手机上的数独游戏，都可以正确得出解了，就赖的搞非递归的了。
有些数组使用了10个元素，第一个用来统计个数的，是不是有点恶心了，确实有点，呵呵，不想封装或者使用C++容器。
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>
void printMap(const char map[9][9]);
int resudoku(char map[9][9]);
void getOptionValues(const char map[9][9], char optionValues[9*9][9+1]);
void getExcludeValues(const char map[9][9], int row, int column, char ifExclude[10]);
int hasFinish(char optionValues[9*9][9+1]);
void getSortedOptionNum(const char optionValues[9*9][9+1], char sortedOptionNum[9*9]);
int gTimes = 0;
int main()
{
int tmp;
int ret = 0;
char map[9][9] = {0};
/*
{
0, 0, 8, 0, 6, 0, 0, 0, 0,
3, 0, 0, 4, 7, 5, 0, 0, 0,
2, 4, 5, 0, 0, 0, 1, 0, 0,
6, 2, 0, 9, 4, 7, 0, 0, 0,
9, 1, 0, 0, 0, 0, 0, 2, 7,
0, 0, 0, 1, 2, 6, 0, 9, 3,
0, 0, 6, 0, 0, 0, 2, 5, 8,
0, 0, 0, 3, 8, 4, 0, 0, 9,
0, 0, 0, 0, 5, 0, 3, 0, 0
};
*/
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
scanf("%d", &tmp);
map[i][j] = tmp;
assert(map[i][j] >= 0 && map[i][j] <= 9);
}
}
printMap(map);
ret = resudoku(map);
if (ret == 0)
{
printf("得到可行解，结果如下：\n");
printMap(map);
}
else
{
printf("没找到可行解！\n");
}
system("pause.exe");
return 0;
}
void printMap(const char map[9][9])
{
int i, j;
for (i = 0; i < 9; i++)
{
for (j = 0; j < 9; j++)
printf("%d ", map[i][j]);
printf("\n");
}
}
int resudoku(char map[9][9])
{
int i, j, k, index = 0;
int hasFilled = 1; //是否得到固定取值
char optionValues[9*9][9+1]; //获取可选取值
char sortedOptionNum[9*9]; //保存排序结果，根据optionValues[x][0]的大小排序，即按照表格可选项的个数的多少排序
char supposeMap[9][9] = {0}, value = 0;
printf("gTimes=%d\n", ++gTimes);
if (gTimes > 500)
return(-2);
//只要能得到唯一表格的唯一取值，就一直循环，直到需要做假设时(即所有的可选项都不止一个时)
while (hasFilled)
{
hasFilled = 0;
getOptionValues(map, optionValues);
打印可选取值
//for (i = 0; i < 9; i++)
//{
// for (j = 0; j < 9; j++)
// {
// printf("格子[%d][%d]有%d个可选值:", i, j, optionValues[i*9+j][0]);
// for (k = 0; k < optionValues[i*9+j][0]; k++)
// {
// printf("%d ", optionValues[i*9+j][k+1]);
// }
// printf("\n");
// }
//}
//固定唯一取值
for (i = 0; i < 9; i++)
{
for (j = 0; j < 9; j++)
{
//如果原来是不确定的，现在只有一个可选取值那么就把这个唯一的可选值变成固定值
if (map[i][j] == 0 && optionValues[i*9+j][0] == 1)
{
hasFilled = 1;
map[i][j] = optionValues[i*9+j][1];
printf("唯一确定了一个新的取值map[%d][%d]=%d\n", i, j, map[i][j]);
}
}
}
}
//如果已经全部得到唯一取值，就成功退出 （表示得到一个可行解，暂不考虑是否只有一个可行解）
if (hasFinish(optionValues))
{
return 0;
}
//对可选项的个数进行排序
getSortedOptionNum(optionValues, sortedOptionNum);
//找出可选项范围最小的那个来开始做取值假设
index = sortedOptionNum[0];
//对每一个取值做假设
for (i = 0; i < optionValues[index][0]; i++)
{
//这次的假设表示为: 表格optionValues[index]有optionValues[index][0]个取值，现在取其中的一个值optionValues[index][i+1]作为[index/9][index%9]的取值
value = optionValues[index][i+1];
memcpy(supposeMap, map, 9*9*sizeof(char));
supposeMap[index/9][index%9] = value;
printf("假设map[%d][%d]=%d ...\n",index/9, index%9, value);
if (resudoku(supposeMap) == 0)
{
printf("假设map[%d][%d]=%d成立!\n",index/9, index%9, value);
memcpy(map, supposeMap, 9*9*sizeof(char));
return 0;
}
printf("假设map[%d][%d]=%d不成立\n",index/9, index%9, value);
}
return -1;
}
//对可选项的个数进行排序(找出可选项大于1的，进行插入排序)
void getSortedOptionNum(const char optionValues[9*9][9+1], char sortedOptionNum[9*9])
{
int i, j, index, size = 0;
memset(sortedOptionNum, -1, 9*9);
for (i = 0; i < 9*9; i++)
{
if (optionValues[i][0] < 2)
continue;
index = 0;
while (index < size)
{
if (optionValues[i][0] < optionValues[sortedOptionNum[index]][0])
break;
index++;
}
//optionValues[i][0]不比sortedOptionNum[]中所有的值小，就添加到末尾，元素个数size加一
if (index == size)
{
size++;
sortedOptionNum[size-1] = i;
}
else
{
size++;
for (j = size - 1; j > index; j--)
{
sortedOptionNum[j] = sortedOptionNum[j-1];
}
sortedOptionNum[index] = i;
}
}
}
int hasFinish(char optionValues[9*9][9+1])
{
int i;
for (i = 0; i < 9 * 9; i++)
{
if (optionValues[i][0] != 1)
return 0;
}
return 1;
}
void getOptionValues(const char map[9][9], char optionValues[9*9][9+1])
{
int i, j, k, index, num;
char ifExclude[10];
for (i = 0; i < 9; i++)
{
for (j = 0; j < 9; j++)
{
index = i * 9 + j;
if (map[i][j] != 0)
{
optionValues[index][0] = 1;
optionValues[index][1] = map[i][j];
continue;
}
else
{
optionValues[index][0] = 0;
}
getExcludeValues(map, i, j, ifExclude);
for (k = 1; k <= 9; k++)
{
if (ifExclude[k] == 0)
{
optionValues[index][0] ++;
num = optionValues[index][0];
optionValues[index][num] = k;
}
}
}
}
}
//获取map[i][j]有哪些值可以排除掉。如果5可以排除掉，那么ifExclude[5]=1; ifExclude[0]表示排除的个数，取值范围[0,9]
void getExcludeValues(const char map[9][9], int row, int column, char ifExclude[10])
{
char value = 0;
int i, j;
int rowStart, rowEnd, columnStart, columnEnd;
memset(ifExclude, 0, 10 * sizeof(char));
//只有在map[row][column]的取值不确定时，才需要排除不能的取值
assert(map[row][column] == 0);
//根据同一列表格的取值来排除
for(i = 0; i < 9; i++)
{
value = map[i][column];
//assert(value >= 0 && value <= 9);
if (value != 0)
{
//如果之前还没有添加到排除列表中，才添加进去，并且把排除的个数+1
if (ifExclude[value] == 0)
{
ifExclude[value] = 1; //map[row][column]的取值排除了value
ifExclude[0]++;
}
}
}
//根据同一行表格的取值来排除
for(j = 0; j < 9; j++)
{
value = map[row][j];
//assert(value >= 0 && value <= 9);
if (value != 0)
{
if (ifExclude[value] == 0)
{
ifExclude[value] = 1;
ifExclude[0]++;
}
}
}
//根据小方格的取值来排除
rowStart = 3 * (row / 3);
rowEnd = rowStart + 3;
columnStart = 3 * (column / 3);
columnEnd = columnStart + 3;
for (i = rowStart; i < rowEnd; i++)
{
for (j = columnStart; j < columnEnd; j++)
{
value = map[i][j];
//assert(value >= 0 && value <= 9);
if (value != 0)
{
if (ifExclude[value] == 0)
{
ifExclude[value] = 1;
ifExclude[0]++;
}
}
}
}
}
例子，与输出
0 0 8 0 6 0 0 0 0
3 0 0 4 7 5 0 0 0
2 4 5 0 0 0 1 0 0
6 2 0 9 4 7 0 0 0
9 1 0 0 0 0 0 2 7
0 0 0 1 2 6 0 9 3
0 0 6 0 0 0 2 5 8
0 0 0 3 8 4 0 0 9
0 0 0 0 5 0 3 0 0
7 9 8 2 6 1 5 3 4
3 6 1 4 7 5 9 8 2
2 4 5 8 9 3 1 7 6
6 2 3 9 4 7 8 1 5
9 1 4 5 3 8 6 2 7
5 8 7 1 2 6 4 9 3
4 3 6 7 1 9 2 5 8
1 5 2 3 8 4 7 6 9
8 7 9 6 5 2 3 4 1
======================================================
0 0 6 7 5 0 0 0 0
0 0 8 0 0 0 6 9 4
0 0 1 9 8 0 0 0 7
0 5 0 1 0 7 0 2 0
4 6 0 0 0 0 0 1 3
0 2 0 6 0 3 0 7 0
6 0 0 0 1 9 7 0 0
3 1 2 0 0 0 8 0 0
7 0 0 0 6 2 1 0 0
9 3 6 7 5 4 2 8 1
5 7 8 2 3 1 6 9 4
2 4 1 9 8 6 3 5 7
8 5 3 1 9 7 4 2 6
4 6 7 5 2 8 9 1 3
1 2 9 6 4 3 5 7 8
6 8 5 3 1 9 7 4 2
3 1 2 4 7 5 8 6 9
7 9 4 8 6 2 1 3 5
======================================================
9 0 4 0 0 6 0 0 0
0 0 0 3 8 7 0 0 0
0 0 0 0 0 0 3 5 6
7 5 2 0 1 0 0 0 0
0 0 0 9 0 4 0 0 3
0 0 0 0 7 0 5 1 8
6 1 8 0 0 0 0 0 0
0 0 0 2 3 8 0 0 0
0 0 0 1 0 0 4 0 7
9 3 4 5 2 6 7 8 1
5 6 1 3 8 7 9 4 2
8 2 7 4 9 1 3 5 6
7 5 2 8 1 3 6 9 4
1 8 6 9 5 4 2 7 3
3 4 9 6 7 2 5 1 8
6 1 8 7 4 9 9 3 5
4 7 5 2 3 8 1 6 9
2 9 3 1 6 5 4 2 7
====================================================
3 0 4 2 0 5 0 6 9
0 0 0 0 0 0 0 0 0
1 0 0 4 0 0 7 8 0
9 0 0 0 2 0 0 0 6
5 0 0 0 0 0 0 0 3
8 0 0 0 7 0 0 0 1
0 9 2 0 0 4 0 0 8
0 0 0 0 0 0 0 0 0
4 1 0 6 0 3 5 0 7
gTimes=1
唯一确定了一个新的取值map[0][6]=1
唯一确定了一个新的取值map[8][2]=8
唯一确定了一个新的取值map[0][4]=8
唯一确定了一个新的取值map[8][4]=9
唯一确定了一个新的取值map[0][1]=7
唯一确定了一个新的取值map[8][7]=2
唯一确定了一个新的取值map[7][8]=4
假设map[1][0]=2 …
gTimes=2
唯一确定了一个新的取值map[1][8]=5
唯一确定了一个新的取值map[2][8]=2
假设map[1][1]=6 …
gTimes=3
唯一确定了一个新的取值map[1][2]=9
唯一确定了一个新的取值map[2][1]=5
唯一确定了一个新的取值map[7][1]=3
唯一确定了一个新的取值map[3][1]=4
唯一确定了一个新的取值map[3][6]=8
唯一确定了一个新的取值map[4][1]=2
唯一确定了一个新的取值map[5][1]=2
唯一确定了一个新的取值map[3][5]=1
唯一确定了一个新的取值map[1][5]=7
假设map[1][3]=1 …
gTimes=4
唯一确定了一个新的取值map[1][4]=3
唯一确定了一个新的取值map[1][6]=4
唯一确定了一个新的取值map[1][7]=4
唯一确定了一个新的取值map[2][4]=6
唯一确定了一个新的取值map[2][5]=9
唯一确定了一个新的取值map[4][4]=4
唯一确定了一个新的取值map[4][6]=9
唯一确定了一个新的取值map[5][6]=9
唯一确定了一个新的取值map[4][3]=8
唯一确定了一个新的取值map[4][7]=7
唯一确定了一个新的取值map[5][5]=6
唯一确定了一个新的取值map[5][7]=5
唯一确定了一个新的取值map[7][6]=6
唯一确定了一个新的取值map[5][2]=3
唯一确定了一个新的取值map[5][3]=3
唯一确定了一个新的取值map[6][6]=3
唯一确定了一个新的取值map[7][0]=7
唯一确定了一个新的取值map[3][2]=7
唯一确定了一个新的取值map[3][3]=5
唯一确定了一个新的取值map[6][0]=6
唯一确定了一个新的取值map[6][7]=1
唯一确定了一个新的取值map[7][2]=5
唯一确定了一个新的取值map[7][3]=5
唯一确定了一个新的取值map[6][3]=7
唯一确定了一个新的取值map[7][4]=1
唯一确定了一个新的取值map[7][7]=9
假设map[4][2]=1 …
gTimes=5
假设map[7][5]=2 …
gTimes=6
假设map[7][5]=2不成立
假设map[7][5]=8 …
gTimes=7
假设map[7][5]=8不成立
假设map[4][2]=1不成立
假设map[4][2]=6 …
gTimes=8
假设map[7][5]=2 …
gTimes=9
假设map[7][5]=2不成立
假设map[7][5]=8 …
gTimes=10
假设map[7][5]=8不成立
假设map[4][2]=6不成立
假设map[1][3]=1不成立
假设map[1][3]=3 …
gTimes=11
唯一确定了一个新的取值map[1][4]=1
唯一确定了一个新的取值map[1][6]=4
唯一确定了一个新的取值map[1][7]=4
唯一确定了一个新的取值map[2][4]=6
唯一确定了一个新的取值map[3][3]=5
唯一确定了一个新的取值map[2][5]=9
唯一确定了一个新的取值map[3][7]=7
唯一确定了一个新的取值map[4][4]=4
唯一确定了一个新的取值map[4][6]=9
唯一确定了一个新的取值map[5][3]=9
唯一确定了一个新的取值map[5][6]=9
唯一确定了一个新的取值map[6][4]=5
唯一确定了一个新的取值map[7][4]=5
唯一确定了一个新的取值map[3][2]=3
唯一确定了一个新的取值map[4][3]=8
唯一确定了一个新的取值map[5][5]=6
唯一确定了一个新的取值map[5][7]=5
唯一确定了一个新的取值map[7][6]=6
唯一确定了一个新的取值map[6][6]=3
唯一确定了一个新的取值map[7][0]=7
唯一确定了一个新的取值map[7][2]=7
唯一确定了一个新的取值map[6][0]=6
唯一确定了一个新的取值map[6][7]=1
唯一确定了一个新的取值map[7][3]=1
唯一确定了一个新的取值map[6][3]=7
唯一确定了一个新的取值map[7][7]=9
假设map[4][2]=1 …
gTimes=12
假设map[7][5]=2 …
gTimes=13
假设map[7][5]=2不成立
假设map[7][5]=8 …
gTimes=14
假设map[7][5]=8不成立
假设map[4][2]=1不成立
假设map[4][2]=6 …
gTimes=15
假设map[7][5]=2 …
gTimes=16
假设map[7][5]=2不成立
假设map[7][5]=8 …
gTimes=17
假设map[7][5]=8不成立
假设map[4][2]=6不成立
假设map[1][3]=3不成立
假设map[1][1]=6不成立
假设map[1][1]=8 …
gTimes=18
假设map[1][2]=6 …
gTimes=19
唯一确定了一个新的取值map[2][1]=5
唯一确定了一个新的取值map[5][2]=3
唯一确定了一个新的取值map[2][2]=9
唯一确定了一个新的取值map[3][1]=4
唯一确定了一个新的取值map[2][5]=6
唯一确定了一个新的取值map[3][6]=8
唯一确定了一个新的取值map[2][4]=3
唯一确定了一个新的取值map[3][5]=1
唯一确定了一个新的取值map[5][5]=9
唯一确定了一个新的取值map[1][4]=1
唯一确定了一个新的取值map[1][5]=7
唯一确定了一个新的取值map[3][2]=7
唯一确定了一个新的取值map[4][3]=8
唯一确定了一个新的取值map[4][5]=8
唯一确定了一个新的取值map[5][3]=5
唯一确定了一个新的取值map[1][3]=9
唯一确定了一个新的取值map[3][3]=3
唯一确定了一个新的取值map[3][7]=5
唯一确定了一个新的取值map[4][2]=1
唯一确定了一个新的取值map[5][7]=4
唯一确定了一个新的取值map[6][4]=5
唯一确定了一个新的取值map[7][2]=5
唯一确定了一个新的取值map[7][4]=5
唯一确定了一个新的取值map[7][5]=2
唯一确定了一个新的取值map[1][7]=3
唯一确定了一个新的取值map[5][6]=2
唯一确定了一个新的取值map[1][6]=4
唯一确定了一个新的取值map[4][6]=9
唯一确定了一个新的取值map[5][1]=6
唯一确定了一个新的取值map[6][7]=1
唯一确定了一个新的取值map[4][1]=2
唯一确定了一个新的取值map[4][7]=7
唯一确定了一个新的取值map[6][3]=7
唯一确定了一个新的取值map[7][1]=3
唯一确定了一个新的取值map[7][7]=9
唯一确定了一个新的取值map[6][0]=6
唯一确定了一个新的取值map[7][3]=1
唯一确定了一个新的取值map[7][6]=6
唯一确定了一个新的取值map[6][6]=3
唯一确定了一个新的取值map[7][0]=7
假设map[4][4]=4 …
gTimes=20
假设map[4][4]=4成立!
假设map[1][2]=6成立!
假设map[1][1]=8成立!
假设map[1][0]=2成立!
得到可行解，结果如下：
3 7 4 2 8 5 1 6 9
2 8 6 9 1 7 4 3 5
1 5 9 4 3 6 7 8 2
9 4 7 3 2 1 8 5 6
5 2 1 8 4 8 9 7 3
8 6 3 5 7 9 2 4 1
6 9 2 7 5 4 3 1 8
7 3 5 1 5 2 6 9 4
4 1 8 6 9 3 5 2 7
请按任意键继续. . .
今天的文章数独解法分享到此就结束了，感谢您的阅读。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/5575.html
