算法
深搜+剪枝优化:
状态的储存(state[x][y]可以填哪些数0~15),用的二进制存储
搜索顺序(枚举每个空格,选备选方案最少的深搜),
优化(对每行,列,宫格,空格,若没有字母可填则无解恢复现场回溯,若只能填一个字母则填上;每次选空格时选择备选方案最少的格子来填)
题目描述
请你将一个16x16的数独填写完整,使得每行、每列、每个4x4十六宫格内字母A~P均恰好出现一次。
保证每个输入只有唯一解决方案。
输入格式
输入包含多组测试用例。
每组测试用例包括16行,每行一组字符串,共16个字符串。
第i个字符串表示数独的第i行。
字符串包含字符可能为字母A~P或”-“(表示等待填充)。
测试用例之间用单个空行分隔,输入至文件结尾处终止。
样例
输入样例:
--A----C-----O-I
-J--A-B-P-CGF-H-
--D--F-I-E----P-
-G-EL-H----M-J--
----E----C--G---
-I--K-GA-B---E-J
D-GP--J-F----A--
-E---C-B--DP--O-
E--F-M--D--L-K-A
-C--------O-I-L-
H-P-C--F-A--B---
---G-OD---J----H
K---J----H-A-P-L
--B--P--E--K--A-
-H--B--K--FI-C--
--F---C--D--H-N-
输出样例:
FPAHMJECNLBDKOGI
OJMIANBDPKCGFLHE
LNDKGFOIJEAHMBPC
BGCELKHPOFIMAJDN
MFHBELPOACKJGNID
CILNKDGAHBMOPEFJ
DOGPIHJMFNLECAKB
JEKAFCNBGIDPLHOM
EBOFPMIJDGHLNKCA
NCJDHBAEKMOFIGLP
HMPLCGKFIAENBDJO
AKIGNODLBPJCEFMH
KDEMJIFNCHGAOPBL
GLBCDPMHEONKJIAF
PHNOBALKMJFIDCEG
IAFJOECGLDPBHMNK
C++ 代码
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=16,M=N*N+1;
int ones[1<<N],Log[1<<N];//ones[x]表示x里有多少个1,Log[x]表示x对应的是第几位(eg 1 0 0 0 --> 2)
int state[N][N];//表示(x,y)位置可以选的集合{A~P} (位 3 2 1 0)
char str[N][N+1];//矩阵状态
int bstate[N*N+1][N][N],bstate2[N*N+1][N][N];//state备份
char bstr[N*N+1][N][N+1];//str备份
//深搜+剪枝优化:
//1.状态的储存:state[x][y]表示x行y列这个格子可以填哪些数(0~15)(即0~2^15-1,可二进制表示);
//2.搜索顺序(枚举每个空格,选备选方案最少的深搜)
//3.优化(对每行,列,宫格,空格,若没有字母可填则无解恢复现场回溯,若只能填一个字母则填上;每次选空格时选//择备选方案最少的格子来填)
inline int lowbit(int x){
return x&-x;
}
void draw(int x,int y,int c){
str[x][y]=c+'A';
for(int i=0;i<N;i++)
{
state[x][i]&=~(1<<c);
state[i][y]&=~(1<<c);
}
int sx=x/4*4,sy=y/4*4;
for(int i=0;i<4;i++)
for(int j=0;j<4;j++){
state[sx+i][sy+j]&=~(1<<c);
}
state[x][y]=1<<c;
}
bool dfs(int cnt)
{
if(!cnt)return true;
int kcnt=cnt;//备份
memcpy(bstate[kcnt],state,sizeof state);
memcpy(bstr[kcnt],str,sizeof str);
//对于每一个空格,如果一个字母都不能填,则无解;如果只能填一个字母,则直接填;
for(int i=0;i<N;i++)
for(int j=0;j<N;j++){
if(str[i][j]=='-'){
int s=state[i][j];
if(!s){
memcpy(state,bstate[kcnt],sizeof state);
memcpy(str,bstr[kcnt],sizeof str);
return false;
}
if(ones[s]==1){
draw(i,j,Log[s]);
cnt--;
}
}
}
//对于每一行,如果某个字母不能出现在任何一个位置,则无解;
//如果某个字母只能出现在某个位置,则直接填
for(int i=0;i<N;i++)
{
int sor=0,sand=(1<<N)-1;
int drawn=0;
for(int j=0;j<N;j++){
int s=state[i][j];
sand&=~(s&sor);//交集(看是否某个字母只能出现在某个位置)
sor|=s; //并集,每个字母在每一个位置都恰好出现一次
if(str[i][j]!='-')drawn|=s;//将已经填好的记录下来
}
if(sor!=(1<<N)-1){
memcpy(state,bstate[kcnt],sizeof state);
memcpy(str,bstr[kcnt],sizeof str);//回溯恢复现场
return false;
}
for(int j=sand;j;j-=lowbit(j)){
int t=lowbit(j);
if(!(drawn&t)){//若交集里的(某个字母只能出现在某个位置)
for(int k=0;k<N;k++){
if(state[i][k]&t){
draw(i,k,Log[t]);
cnt--;
break;
}
}
}
}
}
//对于每一列,如果某个字母不能出现在任何一个位置,则无解;
////如果某个字母只能出现在某个位置,则直接填
for(int j=0;j<N;j++){
int sor=0,sand=(1<<N)-1;
int drawn=0;
for(int i=0;i<N;i++){
int s=state[i][j];
sand&=~(s&sor);
sor|=s;
if(str[i][j]!='-')drawn|=s;
}
if(sor!=(1<<N)-1){
memcpy(state,bstate[kcnt],sizeof state);
memcpy(str,bstr[kcnt],sizeof str);
return false;
}
for(int i=sand;i;i-=lowbit(i)){
int t=lowbit(i);
if(!(drawn&t)){
for(int k=0;k<N;k++){
if(state[k][j]&t){
draw(k,j,Log[t]);
cnt--;
break;}
}
}
}
}
//对于每个16宫格,如果某个字母不嫩出现在任何一个位置,则无解;
//如果某个字母只能出现在某个位置,则直接填
for(int i=0;i<N;i++){
int sor=0,sand=(1<<N)-1;
int drawn=0;
for(int j=0;j<N;j++){
int sx=i/4*4,sy=i%4*4;
int dx=j/4,dy=j%4;
int s=state[sx+dx][sy+dy];
sand&=~(s&sor);
sor|=s;
if(str[sx+dx][sy+dy]!='-')drawn|=s;
}
if(sor!=(1<<N)-1){
memcpy(state,bstate[kcnt],sizeof state);
memcpy(str,bstr[kcnt],sizeof str);
return false ;
}
for(int j=sand;j;j-=lowbit(j)){
int t=lowbit(j);
if(!(drawn&t)){
for(int k=0;k<N;k++){
int sx=i/4*4,sy=i%4*4;
int dx=k/4,dy=k%4;
if(state[sx+dx][sy+dy]&t){
draw(sx+dx,sy+dy,Log[t]);
cnt--;
break;
}
}
}
}
}
//选择分支最少的坐标(x,y)(即state可选字母集合中元素数最少的x,y坐标)
if(!cnt)return true;
int x,y,s=100;
for(int i=0;i<N;i++)
for(int j=0;j<N;j++){
if(ones[state[i][j]]<s&&str[i][j]=='-'){//比较记录
s=ones[state[i][j]];
x=i;
y=j;
}
}
memcpy(bstate2[kcnt],state,sizeof state);//备份
for(int i=state[x][y];i;i-=lowbit(i)){
memcpy(state,bstate2[kcnt],sizeof state);
draw(x,y,Log[lowbit(i)]);
if(dfs(cnt-1))return true;//回溯
}
memcpy(state,bstate[kcnt],sizeof state);//恢复现场
memcpy(str,bstr[kcnt],sizeof str);
return false;
}
int main(){
for(int i=0;i<N;i++)Log[1<<i]=i;//预处理
for(int i=0;i<(1<<N);i++)
{
for(int j=i;j;j-=lowbit(j))ones[i]++;
}
while(cin>>str[0]){
for(int i=1;i<N;i++)cin>>str[i];
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
state[i][j]=(1<<N)-1;
int cnt=0;
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
if(str[i][j]!='-') draw(i,j,str[i][j]-'A');//更新状态
else cnt++;//储存空格数
dfs(cnt);//深搜
for(int i=0;i<N;i++) cout<<str[i]<<endl;
cout<<endl;
}
return 0;
}
标题NB(
😥主要是但看题目想不起思路