程序员休闲娱乐之数独！| 技术头条
作者 | 宋广泽
责编 | 胡巍巍
前几天闲着没事，就玩了玩经典益智游戏数独。
简单的可以轻松过关。
稍微难一点的也可以勉强过关。
可是再难呢？如下图所示这种的，就有点招架不住了。
有的时候凭直觉相信自己填的数字是正确的，可是填着填着快到了最后，却发现前面的某个数字填错了导致后面的也一错再错，根本无法修补，颇有些不撞南墙不回头的意味在里面。
计算机总是能够不知疲倦的替你思考，何不让计算机撞南墙然后最后给你答案？
身为一名三流算法竞赛选手，第一时间想到了深度优先搜索算法，也就是常说的DFS算法，这种算法的思想就是一条路走到黑，发现走的不对再退回上一个十字路口选择另一条没有尝试过的路走，如果问题存在一个解，那么总有那么一个时刻可以找到这个解。
DFS虽然不是一个多项式时间的算法，但对于解决数独问题来说足够了。
因为传统数独游戏一定是在9*9=81个方格内填数字，不存在更大的问题规模，所以大家就不用担心DFS会花费很长的时间来解决数独问题。
当然大家也不用担心环境问题，简单的C++编译环境、控制台应用程序就可以完成。
先简单介绍以下DFS算法：
如上图所示，我们的起点是A，我们要找到一条到H点的路，我们让遍历的顺序为从左至右。
从A出发，因该先到达B，B再到达D，发现D没有子结点，撞了南墙，该回头了；
于是又回退到B，E还没有搜索过，就搜索E，E又到I，又撞了南墙，回头到B，B也没有其他欸有走过的路径了，再回退到A；
A还可以从C开始搜索，C先到F，撞南墙，回退到C；再搜索G，撞南墙，回退到C；搜索H，此时才找到了H，也找到了一条从A到H的路径即A->C->H。
对于数独，首先要解决的就是数独规则的判定，所有的数字只有1-9，每一行、每一列、等分的每个九宫格内都不能出现重复的数字。
采用标记法，每一行、每一列、每个九宫格都有一个长度为10的的标记数字1-9在某一行、某一列、某个九宫格中是否出现过的数组名为dp，当然，长度设为9也可以，但是数组的下标是从0开始的，因此用0标记数字1是否出现过是不符合人类习惯的。
我们将数独的9行从0到8编号，将9列从0到8编号，将九宫格按照从上往下、从左往右的顺序从0到8编号，这样在遍历时，就可以根据行列坐标找到相应的dp数组，然后看看当前坐标下的数是不是已经出现过了，如果之前已经出现过，说明数独中出现了重复的数字，直接返回false。
检查数独合法性的函数的源代码：
bool check(char **board,int boardRowSize,int boardColSize)
{
int i,j;
bool dpRow[9][10],dpCol[9][10],dpGrid[9][10];
memset(dpRow,0,sizeof(dpRow));
memset(dpCol,0,sizeof(dpCol));
memset(dpGrid,0,sizeof(dpGrid));
for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
{
if(board[i][j]!='.')
{
if(dpRow[i][board[i][j]-'0']==true)
return false;
if(dpCol[j][board[i][j]-'0']==true)
return false;
if(dpGrid[i/3*3+j/3][board[i][j]-'0']==true)
return false;
dpRow[i][board[i][j]-'0']=true;
dpCol[j][board[i][j]-'0']=true;
dpGrid[i/3*3+j/3][board[i][j]-'0']=true;
}
}
}
return true;
}
举个例子，如果当前遍历到的坐标是(3,0)，即第四行第一列，那么它对应的行的dp数组的编号就是行坐标3，对应的列的dp数组的编号就是列坐标0，而对应的九宫格的dp数组的编号刚好是 行坐标3/3(向下取整)*3+列坐标0/3(向下取整)，得到的dp数组的编号是3（第四个九宫格）。
从树的搜索换到数独上来，在九乘九方格中，从上往下，从左往右进行遍历，每遍历到一个空的方格，就尝试填入1到9中的数字，每填入一个数字，然后检查一下有没有违反数独规则，如果违反了则说明此路不通，回退到上一个状态；
如果没有违反数独规则，则继续向下一个空的方格尝试填入1到9中的数字，如此循环往复，最终会给出一个完整的数独的解。如果填入1-9都不是合法的，则说明数独无解。
搜索并尝试填入数字的函数的源代码：
bool dfs(char **board,int boardRowSize,int boardColSize)
{
int i,j,k;
bool flag=false;
for(i=0;i<boardRowSize;i++)
{
for(j=0;j<boardColSize;j++)
{
if(board[i][j]=='.')
{
for(k=1;k<=9;k++)
{
board[i][j]=k+'0';
if(check(board,boardRowSize,boardColSize))
{
flag=dfs(board,boardRowSize,boardColSize);
if(flag==true)
return true;
}
board[i][j]='.';
}
return false;
}
}
}
return true;
}
为了代码的可移植性，传入的参数是一个表示数独地图的二级指针、总行数和总列数。
在主函数中，可以先为数独开辟内存空间，然后以字符串的形式输入原始条件。若输入有误则极有可能出现填不全的结果，为了避免这种结果我们可以加一条提示，输入有误则输出无法求解，输入正确才输出正确列。
主函数源代码：
int main()
{
int i;
board=(char **)malloc(9*sizeof(char *));
for(i=0;i<9;i++)
{
board[i]=(char *)malloc(9*sizeof(char));
}
for(i=0;i<9;i++)
{
scanf("%s",board[i]);
}
bool flag=dfs(board,9,9);
if(flag)
{
printf("求解成功:\n");
for(i=0;i<9;i++)
{
printf("%s\n",board[i]);
}
}
else
{
printf("无法求解!\n");
}
for(i=0;i<9;i++)
{
free(board[i]);
board[i]=NULL;
}
free(board);
board=NULL;
return 0;
}
填入一局数独给出的原始条件，得到如下的结果，
再将结果填入游戏，直接通关。
忙碌了一天，算是最后给自己的一点小小的惊喜。希望本文对你有帮助哦！
附C++控制台应用程序的全部源代码：
char **board;
//检验是否是一个有效的数独
bool check(char **board,int boardRowSize,int boardColSize)
{
int i,j;
bool dpRow[9][10],dpCol[9][10],dpGrid[9][10];
memset(dpRow,0,sizeof(dpRow));
memset(dpCol,0,sizeof(dpCol));
memset(dpGrid,0,sizeof(dpGrid));
for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
{
if(board[i][j]!='.')
{
if(dpRow[i][board[i][j]-'0']==true)
return false;
if(dpCol[j][board[i][j]-'0']==true)
return false;
if(dpGrid[i/3*3+j/3][board[i][j]-'0']==true)
return false;
dpRow[i][board[i][j]-'0']=true;
dpCol[j][board[i][j]-'0']=true;
dpGrid[i/3*3+j/3][board[i][j]-'0']=true;
}
}
}
return true;
}
//搜索并填空
bool dfs(char **board,int boardRowSize,int boardColSize)
{
int i,j,k;
bool flag=false;
for(i=0;i<boardRowSize;i++)
{
for(j=0;j<boardColSize;j++)
{
if(board[i][j]=='.')
{
for(k=1;k<=9;k++)
{
board[i][j]=k+'0';
if(check(board,boardRowSize,boardColSize))
{
flag=dfs(board,boardRowSize,boardColSize);
if(flag==true)
return true;
}
board[i][j]='.';
}
return false;
}
}
}
return true;
}
int main()
{
int i;
board=(char **)malloc(9*sizeof(char *));
for(i=0;i<9;i++)
{
board[i]=(char *)malloc(9*sizeof(char));
}
for(i=0;i<9;i++)
{
scanf("%s",board[i]);
}
bool flag=dfs(board,9,9);
if(flag)
{
printf("求解成功:\n");
for(i=0;i<9;i++)
{
printf("%s\n",board[i]);
}
}
else
{
printf("无法求解!\n");
}
for(i=0;i<9;i++)
{
free(board[i]);
board[i]=NULL;
}
free(board);
board=NULL;
return 0;
}
作者：宋广泽，青岛某普通一本大学计算机专业在校生，本科在读，学生开发者。喜欢用C/C++编写有意思的程序，解决实际问题。
声明：本文为CSDN原创投稿，未经允许请勿转载。
【END】
作为码一代，想教码二代却无从下手：
听说少儿编程很火，可它有哪些好处呢？
孩子多大开始学习比较好呢？又该如何学习呢？
最新的编程教育政策又有哪些呢？
下面给大家介绍CSDN新成员：极客宝宝（ID：geek_baby）
戳他了解更多↓↓↓
热 文 推 荐
☞Google 究竟是不是要用 Fuchsia OS 取代 Android？
☞增长88%! 2019福布斯全球区块链50强榜单, 你未必看懂这3个细节