$$\color{Purple}{kuangbin题解目录}$$
描述
数独 是一种传统益智游戏,你需要把一个 $9 \\times 9$ 的数独补充完整,使得数独中每行、每列、每个 $3 \\times 3$ 的九宫格内数字 $1 \\sim 9$ 均恰好出现一次。
请编写一个程序填写数独。
输入格式
输入包含多组测试用例。
每个测试用例占一行,包含 $81$ 个字符,代表数独的 $81$ 个格内数据(顺序总体由上到下,同行由左到右)。
每个字符都是一个数字($1-9$)或一个 .
(表示尚未填充)。
您可以假设输入中的每个谜题都只有一个解决方案。
文件结尾处为包含单词 end
的单行,表示输入结束。
输出格式
每个测试用例,输出一行数据,代表填充完全后的数独。
输入样例:
4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......
......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.
end
输出样例:
417369825632158947958724316825437169791586432346912758289643571573291684164875293
416837529982465371735129468571298643293746185864351297647913852359682714128574936
思路
-
搜索
- 该题用搜索在$Poj$若不用
内联函数
,会$T$掉 - 该九宫格下标从$(0,0)$开始,将每行、每列、每个方格都二进制化,初始时每个地方都可以填(即二进制全部置为1),再将已经填好的数放入当前的二进制中,最后处理未放置的元素;
优化搜索顺序
: 从未填的数中找最少可填数字
的点进行枚举,减小搜索树的搜索范围;排除等效冗余
: 任意一个状态下,我们只需要找一个位置填数即可,而不是找所有的位置和可填的数字;位运算
: 可用lowbit函数
优化时间效率.- 当前该位置$(x,y)$的状态可表示为:
row[x]&col[y]&cell[x/3][y/3]
,其中$row[x]$表示当前行可填数的情况,$col[y]$表示当前列可填数的情况,$cell[\frac{x}{3}][\frac{y}{3}]$表示当前方格可填数的情况,二进制第$i$位($0 \le i \le 8$)的状态表示是实际数字$i+1$是否可填($1$表示可填,$0表示不可填$); - 关于已知坐标$(x,y)$求对应的方格坐标为$(\frac{x}{3},\frac{y}{3})$,此处也可一维化为$\frac{x}{3}\times 3+\frac{y}{3}$(范围$0-8$),如下图所示:
- 该题用搜索在$Poj$若不用
-
$Dancing\ Links$
- 属于
精确覆盖问题
,构建的$01$矩阵,以每个位置可填9个数
(即有$9\times 9 \times 9=729$行,可适当开大一点)作为横坐标,以当前位置是否填数,当前行是否有该数,当前列是否有该数,当前方格是否有该数
(即有$4\times 9\times 9 =324$列,可适当开大点)作为纵坐标;- 设当前位置的坐标是$(x,y)$(下标从$0$开始),对应方格一维化为$\frac{x}{3}\times 3+\frac{y}{3}$,填的数是$num$(此处数范围是$1\le num \le 9$).
每个位置可填9个数
转化为对应的行是$\color{Red}{(x\times 9 + y)\times 9 + num}$
当前位置是否填数
,列可表示为$\color{Red}{x\times 9+y+1}$,共$81$个.
当前行是否有该数
,列可表示为$\color{Red}{9\times 9 + x\times 9 +num}$,共$81$个.
当前列是否有该数
,列可表示为$\color{Red}{2\times 9\times 9 + y\times 9 +num}$,共$81$个.
当前方格是否有该数
,列可表示为$\color{Red}{3\times 9\times 9 + (\frac{x}{3}\times 3+ \frac{y}{3})\times 9 +num}$,共$81$个.
代码
- 搜索
// Problem: 数独
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/168/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Date: 2023-01-16 12:38:49
//
// Powered by CP Editor (https://cpeditor.org)
/**
* @author : SDTBU_LY
* @version : V1.0.0
* @上联 : ac自动机fail树上dfs序建可持久化线段树
* @下联 : 后缀自动机的next指针DAG图上求SG函数
**/
#include<iostream>
#include<cstring>
#include<algorithm>
#define MAXN 9
#define MAXM (1<<9)
using namespace std;
typedef long long ll;
string s;
int one_cnt[MAXM];//one_cnt[state]记录每个state中1的个数
int num[MAXM];//对应的十进制数
int row[MAXN],col[MAXN];//存每行、每列的填数情况
int cell[3][3];//存每个单元格的填数情况
inline int lowbit(int x)//树状数组经典操作
{
return x&-x;
}
void init()//初始化函数
{
for(int i=0;i<MAXN;i++)//每一行每一列都置为(111111111)_2,表示都可以填数
row[i]=col[i]=MAXM-1;
//每一方格都置为(111111111)_2,表示都可以填数
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
cell[i][j]=MAXM-1;
}
inline int get_state(int x,int y)//获取当前位置(x,y)可填的状态
{
return row[x]&col[y]&cell[x/3][y/3];
}
void draw(int x,int y,int temp_num,int is_place)
{//x横坐标,y纵坐标,temp_num所填数,is_place是否放置(即放置或者恢复)
if(is_place==1)//放在对应位置
s[x*MAXN+y]='1'+temp_num;
else s[x*MAXN+y]='.';//恢复
int pos=1<<temp_num;//查找二进制的状态对应的位置
//若is_place=1,此时该行该列该方格应-pos(表示当前的行列方格已经填上该数)
//反之,应加上pos(此处为了少写一个大判断,直接将pos变为相反数即可,负负得正).
if(is_place==0)
pos=-pos;
row[x]-=pos;
col[y]-=pos;
cell[x/3][y/3]-=pos;
}
int dfs(int cnt)
{
if(cnt==0)//填完所有数字
return 1;
int min_cnt=10;//最多9个1
int pos_x=0,pos_y=0;
for(int i=0;i<MAXN;i++)
for(int j=0;j<MAXN;j++)
if(s[i*MAXN+j]=='.')
{
//选择当前填数最小的位置进行填数,减少搜索分支数
int state=get_state(i,j);
if(one_cnt[state]<min_cnt)
pos_x=i,pos_y=j,min_cnt=one_cnt[state];
}
int state=get_state(pos_x,pos_y);
for(int i=state;i>=1;i-=lowbit(i))
{
int temp=num[lowbit(i)];
draw(pos_x,pos_y,temp,1);//填数
if(dfs(cnt-1)==1)//搜索下一个点
return 1;
draw(pos_x,pos_y,temp,0);//恢复现场
}
return 0;//搜索失败
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
for(int i=0;i<MAXN;i++)//方便快速查询修改的位置在哪
num[1<<i]=i;
//此处用lowbit快速计算出每个状态1的个数
for(int i=0;i<MAXM;i++)
for(int j=i;j>=1;j-=lowbit(j))
one_cnt[i]++;
while(cin >> s)
{
if(s=="end")
break;
init();
int cnt=0;//记录未填的数的个数
int pos=0;//记录字符串的位置
for(int i=0;i<MAXN;i++)
for(int j=0;j<MAXN;j++)
{
if(s[pos]!='.')//表示已经填好数
{
int temp_num=s[pos]-'1';//方便二进制操作(在放的时候会还原)
draw(i,j,temp_num,1);
//在i,j位置上填temp_num(此时状态为1)
}
else cnt++;//当前未填数
pos++;
}
dfs(cnt);
cout << s << endl;
}
return 0;
}
- $Dancing\ Links$
// Problem: 数独
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/168/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Date: 2023-01-16 13:54:39
//
// Powered by CP Editor (https://cpeditor.org)
/**
* @author : SDTBU_LY
* @version : V1.0.0
* @上联 : ac自动机fail树上dfs序建可持久化线段树
* @下联 : 后缀自动机的next指针DAG图上求SG函数
**/
#include<iostream>
#include<cstring>
#include<algorithm>
#define MAXN 750
#define MAXM 350
#define MAXP (MAXN*MAXM)
using namespace std;
typedef long long ll;
string s;
struct Dancing_Links_Node{
int Up;
int Down;
int Left;
int Right;
int row;//行数
int col;//列数
};
int cnt=0;//记录结点个数
Dancing_Links_Node node[MAXP];
int f_row[MAXN];//记录每行的第一个元素
int c_cnt[MAXM];//每列元素个数
int res[100];//保存最终结果
int temp[100];
void Init_Node(int num)//初始化head和列元素,将其上下左右指针指好,行数和列数可不用初始化
{
for(int i=0;i<=num;i++)
{
node[i].Left=i-1;//左-1
node[i].Right=i+1;//右+1
node[i].Up=i;//上下指向自己
node[i].Down=i;
c_cnt[i]=0;//列个数清空
}
node[0].Left=num;//让head的左边指向最后一个的列元素
node[num].Right=0;//让最后一个的列元素的右边指向head
cnt=num;//更新结点个数
memset(f_row,-1,sizeof(f_row));
}
void Insert_Node(int x,int y){//插入新节点(链式前向星的构图方式)
//更新具体值
node[++cnt].row=x;//更新行数
node[cnt].col=y;//更新列数
//先处理该结点的所在列链上的情况
node[cnt].Down=node[y].Down;//更新当前元素的指向下面
node[node[y].Down].Up=cnt;//之前的最后一个元素指向最后
node[cnt].Up=y;
node[y].Down=cnt;
//然后处理该结点的所在行链上的情况
if(f_row[x]<0)//表示该结点是其所在行的第一个元素
{
node[cnt].Left=cnt;//自己指向自己
node[cnt].Right=cnt;//自己指向自己
f_row[x]=cnt;//更新当前行的第一个元素
}
else//表示该结点不是其所在行的第一个元素
{
node[cnt].Right=node[f_row[x]].Right;
node[node[f_row[x]].Right].Left=cnt;
node[cnt].Left=f_row[x];
node[f_row[x]].Right=cnt;
}
c_cnt[y]++;//当前列元素+1
}
void Remove_Link(int y)//删除列元素所在的列链 及 其中元素所对应行
{
for(int i=node[y].Down;i!=y;i=node[i].Down)//枚举列链中的元素
{
for(int j=node[i].Right;j!=i;j=node[j].Right)//枚举列链中元素所对应行链中元素并删除
{
node[node[j].Down].Up=node[j].Up;
node[node[j].Up].Down=node[j].Down;
//当前元素删除后,该元素的下面元素指向上面的是当前元素的上面元素
//当前元素删除后,该元素的上面元素指向下面的是当前元素的下面元素
c_cnt[node[j].col]--;//当前列的元素-1
}
}
//删除列链(仅需删除列元素即可删除整个列链)
node[node[y].Left].Right=node[y].Right;
node[node[y].Right].Left=node[y].Left;
//当前列元素的左面元素指向右边面的是当前元素的右面元素
//当前列元素的右面元素指向左边面的是当前元素的左面元素
}
void Resume_Link(int y)//恢复列元素所在列链 及 其中元素所对应行
{
//恢复列链(仅需恢复列元素即可恢复整个列链)
node[node[y].Left].Right=y;
node[node[y].Right].Left=y;
for(int i=node[y].Up;i!=y;i=node[i].Up)//枚举列链中的元素
for(int j=node[i].Left;j!=i;j=node[j].Left)//枚举列链中元素所对应行链中元素并恢复
{
node[node[j].Down].Up=j;
node[node[j].Up].Down=j;
//当前元素的上面元素指向下面的是当前元素
//当前元素的下面元素指向上面的是当前元素
c_cnt[node[j].col]++;//当前列的元素+1
}
}
int dance(int depth)//depth表示答案的个数(所搜的层数)
{
if(node[0].Right==0)//如果head.right=head,说明有解,输出答案
{
//1-9存的是(0,0)的情况
//res[i]存的是满足的行,求的对应的位置为(res[i]-1)/9
//最终的结果是(res[i]-1)%9+1
for(int i=0;i<depth;i++)
temp[(res[i]-1)/9]=(res[i]-1)%9+1;
for(int i=0;i<81;i++)
cout << temp[i];
cout << endl;
return 1;
}
int y=node[0].Right;//取列元素y=head.right
for(int i=node[0].Right;i!=0;i=node[i].Right)//剪枝(减少搜索树的分叉)
if(c_cnt[i]<c_cnt[y])
y=i;
Remove_Link(y);//删除列链
for(int i=node[y].Down;i!=y;i=node[i].Down)
{
res[depth]=node[i].row;
for(int j=node[i].Right;j!=i;j=node[j].Right)//删除选择行链元素所在列链
Remove_Link(node[j].col);
if(dance(depth+1)==1)
return 1;
for(int j=node[i].Left;j!=i;j=node[j].Left)//恢复选择行链元素所在列链
Resume_Link(node[j].col);
}
Resume_Link(y);//恢复列链
return 0;
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
while(cin >> s)
{
if(s=="end")
break;
Init_Node(9*9*4);
for(int x=0;x<=8;x++)
for(int y=0;y<=8;y++)
for(int num=1;num<=9;num++)
if(s[x*9+y]=='.'||s[x*9+y]==num+'0')//此处当该位置未填时把所有情况放入链中,反之把当前数放入链中
{
int temp_row=(x*9+y)*9+num;
int temp_col_1=x*9+y+1;
int temp_col_2=9*9+x*9+num;
int temp_col_3=2*9*9+y*9+num;
int temp_col_4=3*9*9+(x/3*3+y/3)*9+num;
Insert_Node(temp_row,temp_col_1);
Insert_Node(temp_row,temp_col_2);
Insert_Node(temp_row,temp_col_3);
Insert_Node(temp_row,temp_col_4);
}
dance(0);
}
return 0;
}