数独游戏
题目描述
输入格式
The input test file will contain multiple cases. Each test case consists of a single line containing 81 characters, which represent the 81 squares of the Sudoku grid, given one row at a time. Each character is either a digit (from 1 to 9) or a period (used to indicate an unfilled square). You may assume that each puzzle in the input will have exactly one solution. The end-of-file is denoted by a single line containing the word “end”.
注意： 本题输入数据量较大，cin, getline可能会超时，建议使用scanf。
输出格式
For each test case, print a line representing the completed Sudoku puzzle.
输入样例
.2738..1..1...6735.......293.5692.8...........6.1745.364.......9518...7..8..6534.
......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.
end
输出样例
527389416819426735436751829375692184194538267268174593643217958951843672782965341
416837529982465371735129468571298643293746185864351297647913852359682714128574936
题目思路
题目整体思路很容易想到：对于每一个空位置，尝试每一个可填数，填入后与同行、同列和同块的所有数字进行比对，看是否有重复；若有，更改当前填入数据，直到该位置无可能性，返回上一个填写的位置，更改数据。
难点1 怎样实现与同行同列同块数字的比较？
首先，我们可以通过一维数组存储输出输入的字符数组。这会为后面的遍历和查找带来方便。对该数组进行扩充，变成二维数组left，第一维存放该位置的数字，第二维存放该位置可放数字的可能性（如果数字确定可能性就为1）。
该位置可放数字的可能性通过函数assign对数组的更新来确定
bool assign(int left[][10],int idx,int lefted)
{
//假设idx位置的值是lefted
left[idx][0]=1;
for(int i=1;i<10;i++)
{
left[idx][i]=0;
}
left[idx][lefted]=1;
int row=idx/9,col=idx%9;
//在相应行判断有无重复元素
for(int i=0;i<9;i++)
{
int now=row*9+i;
//若当前判断位置不是自身且该位置lefted是唯一可能性，说明该假设错误
if(now!=idx&&!remove(left,now,lefted))
{
return false;
}
}
//在相应列判断有无重复元素
for(int i=0;i<9;i++)
{
int now=i*9+col;
if(now!=idx&&!remove(left,now,lefted))
{
return false;
}
}
//在相应块判断有无重复元素
for(int i=0;i<3;i++)
{
for(int j=0;j<3;j++)
{
int now=((row/3)*3+i)*9+(col/3)*3+j;
if(now!=idx&&!remove(left,now,lefted))
{
return false;
}
}
}
return true;
}难点2 怎样修改某位置的可能数字？
通过remove函数实现，注意，修改时要对可能性为1和2的位置进行特判
//从value数组中移除 value[idx][lefted]的可能性
bool remove(int left[][10],int idx,int lefted)
{
if(left[idx][lefted]==1)//若shudu[idx]有取lefted的可能
{
left[idx][lefted]=0;
left[idx][0]--;
//该位置没有其他可能性了
if(left[idx][0]==0)
{
return false;
}
//该位置只有一种可能性了
else if(left[idx][0]==1)
{
for(int i=1;i<10;i++)
{
if(left[idx][i]!=0)
{
if(!assign(left,idx,i))
return false;
else
return true;
}
}
}
else
return true;
}
else
return true;
}难点3 怎样修改递归函数使得时间复杂度减低？
在选择试探的空位时，我们可以采用每次优先选择可能数字最少的进行试探，这样可以在极大程度上减少我们的搜索量。（快速失败法）
//选择shudu[]的空缺位置中可能性最少的位置进行匹配
bool search_match(int left[][10])
{
int minx=0,minl=9;
int flag=1;
for(int i=0;i<81;i++)
{
if(left[i][0]!=1)
{
flag=0;
if(left[i][0]<minl)
{
minl=left[i][0];
minx=i;
}
}
}
//当所有位置的可能性都为1时说明成功，结束递归
if(flag==1)
{
complete_shudu(left);
return true;
}
for(int i=1;i<10;i++)
{
//遍历该位置的所有可能性
if(left[minx][i]!=0)
{
//设临时数组，将left[][]拷贝过来
int left_temp[81][10];
for(int j=0;j<81;j++)
{
for(int k=0;k<10;k++)
{
left_temp[j][k]=left[j][k];
}
}
//若i可以成功插入，且i插入后的数独可以完整填出来
if(assign(left_temp,minx,i))
{
if(search_match(left_temp))
return true;
}
//若i不可以插入，则在left数组中删掉该可能性
left[minx][0]--;
left[minx][i]=0;
}
}
return false;
}完整代码
#include<stdio.h>
#include<string.h>
char shudu[100];//输入的数独数组
int left[82][10]={0};//对于数独第i号格子shudu[i][0]表示其可选择的数，shudu[i][j]表示是否可选数字j
bool assign(int value[][10],int idx,int lefted);
//对left数组进行初始化
void init(int left[82][10],char s[100])
{
for(int i=0;i<81;i++)
{
if(s[i]=='.')
{
left[i][0]=9;
for(int j=1;j<10;j++)
{
left[i][j]=1;
}
}
else
{
left[i][0]=1;
for(int j=1;j<10;j++)
{
left[i][j]=0;
}
left[i][(int)(s[i]-'0')]=1;
}
}
}
//打印数独数组
void print(char s[100])
{
for(int i=0;i<81;i++)
{
printf("%c",s[i]);
}
printf("\n");
}
//将整理好的数字填充到shudu数组中
void complete_shudu(int left[][10])
{
for(int i=0;i<81;i++)
{
for(int j=1;j<10;j++)
{
if(left[i][j]!=0)
{
shudu[i]=j+'0';
break;
}
}
}
}
//从value数组中移除 value[idx][lefted]的可能性
bool remove(int left[][10],int idx,int lefted)
{
if(left[idx][lefted]==1)//若shudu[idx]有取lefted的可能
{
left[idx][lefted]=0;
left[idx][0]--;
if(left[idx][0]==0)
{
return false;
}
else if(left[idx][0]==1)
{
for(int i=1;i<10;i++)
{
if(left[idx][i]!=0)
{
if(!assign(left,idx,i))
return false;
else
return true;
}
}
}
else
return true;
}
else
return true;
}
//更新shudu[idx]的值 ，并更新left表
bool assign(int left[][10],int idx,int lefted)
{
//假设idx位置的值是lefted
left[idx][0]=1;
for(int i=1;i<10;i++)
{
left[idx][i]=0;
}
left[idx][lefted]=1;
int row=idx/9,col=idx%9;
//在相应行判断有无重复元素
for(int i=0;i<9;i++)
{
int now=row*9+i;
//若当前判断位置不是自身且该位置lefted是唯一可能性，说明该假设错误
if(now!=idx&&!remove(left,now,lefted))
{
return false;
}
}
//在相应列判断有无重复元素
for(int i=0;i<9;i++)
{
int now=i*9+col;
if(now!=idx&&!remove(left,now,lefted))
{
return false;
}
}
//在相应块判断有无重复元素
for(int i=0;i<3;i++)
{
for(int j=0;j<3;j++)
{
int now=((row/3)*3+i)*9+(col/3)*3+j;
if(now!=idx&&!remove(left,now,lefted))
{
return false;
}
}
}
return true;
}
//选择shudu[]的空缺位置中可能性最少的位置进行匹配
bool search_match(int left[][10])
{
int minx=0,minl=9;
int flag=1;
for(int i=0;i<81;i++)
{
if(left[i][0]!=1)
{
flag=0;
if(left[i][0]<minl)
{
minl=left[i][0];
minx=i;
}
}
}
//当所有位置的可能性都为1时说明成功，结束递归
if(flag==1)
{
complete_shudu(left);
return true;
}
for(int i=1;i<10;i++)
{
//遍历该位置的所有可能性
if(left[minx][i]!=0)
{
//设临时数组，将left[][]拷贝过来
int left_temp[81][10];
for(int j=0;j<81;j++)
{
for(int k=0;k<10;k++)
{
left_temp[j][k]=left[j][k];
}
}
//若i可以成功插入，且i插入后的数独可以完整填出来
if(assign(left_temp,minx,i))
{
if(search_match(left_temp))
return true;
}
//若i不可以插入，则在left数组中删掉该可能性
left[minx][0]--;
left[minx][i]=0;
}
}
return false;
}
int main()
{
scanf("%s",shudu);
while(strcmp(shudu,"end")!=0)
{
//每次读入一个数独，都要将left数组重置
memset(left,0,sizeof(left));
init(left,shudu);
//根据已确定的数字更新未确定块的可选情况
for(int i=0;i<81;i++)
{
if(shudu[i]!='.')
{
assign(left,i,(int)(shudu[i]-'0'));
}
}
search_match(left);
print(shudu);
memset(shudu,NULL,sizeof(shudu));
scanf("%s",shudu);
}
return 0;
}总结
数独的解法中，最经典的是舞蹈链的解法，可以很好的降低时间复杂度，但是目前自己还看不懂这种做法。
链接先放在这里，以后再慢慢看：https://www.cnblogs.com/grenet/p/3163550.html
另，特别感谢我的小伙伴耐心讲解，这里附上他的博客地址：https://www.cztcode.com/2020/poj3074-summary/
查看9道真题和解析
