程序员休闲娱乐之数独!| 技术头条
作者 | 宋广泽
责编 | 胡巍巍
前几天闲着没事,就玩了玩经典益智游戏数独。
简单的可以轻松过关。
稍微难一点的也可以勉强过关。
可是再难呢?如下图所示这种的,就有点招架不住了。
有的时候凭直觉相信自己填的数字是正确的,可是填着填着快到了最后,却发现前面的某个数字填错了导致后面的也一错再错,根本无法修补,颇有些不撞南墙不回头的意味在里面。
计算机总是能够不知疲倦的替你思考,何不让计算机撞南墙然后最后给你答案?
身为一名三流算法竞赛选手,第一时间想到了深度优先搜索算法,也就是常说的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个细节