题目描述
数独是一种传统益智游戏,你需要把一个9 × 9的数独补充完整,使得图中每行、每列、每个3 × 3的九宫格内数字1~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
C++ 代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=9;
int ones[1<<N],map[1<<N];
int row[N],col[N],cell[3][3];
char str[100];
//inline是关键字,表示内联函数,可加快编译速度,只要不是递归函数都可用inline加速
inline int lowbit(int x){//(返回x最低位为1,对应的二进制数)
return x&-x;
}
void init(){
for(int i=0;i<N;i++)row[i]=col[i]=(1<<N)-1;//(每行,每列{1~9})
for(int i=0;i<3;i++)//(3x3)
for(int j=0;j<3;j++)
cell[i][j]=(1<<N)-1;
}
inline int get(int x,int y){
return row[x]&col[y]&cell[x/3][y/3];//取此行此列和此单元在(x,y)处可选的数集合
}
bool dfs(int cnt){
if(!cnt)return true;
//找出可选方案数最少的空格
int minv=10;
int x,y;//(记录最少空格的坐标)
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
if(str[i*9+j]=='.'){
int t=ones[get(i,j)];
if(t<minv){
minv=t;
x=i;
y=j;
}
}
for(int i=get(x,y);i;i-=lowbit(i)){
int t=map[lowbit(i)];
//修改状态
row[x]-=1<<t;
col[y]-=1<<t;
cell[x/3][y/3]-=1<<t;
str[x*9+y]='1'+t;
if(dfs(cnt-1))return true;
//恢复现场
str[x*9+y]='.';
cell[x/3][y/3]+=1<<t;
col[y]+=1<<t;
row[x]+=1<<t;
}
return false;
}
int main(){
for(int i=0;i<N;i++)map[1<<i]=i;
for(int i=0;i<1<<N;i++){
int s=0;
for(int j=i;j;j-=lowbit(j))s++;//i的二进制中有s个1
ones[i]=s;
}
while(cin>>str,str[0]!='e'){
init();//初始化(每行,每列,每个3x3矩阵的可选集合都是{1~9},即二进制9位都为1)
int cnt=0;
for(int i=0,k=0;i<N;i++)
for(int j=0;j<N;j++,k++)
if(str[k]!='.'){//(修改每行每列,每个3x3在此坐标处可选集合)
int t=str[k]-'1';
row[i]-=1<<t;
col[j]-=1<<t;
cell[i/3][j/3]-=1<<t;
}
else cnt++;//(记录有多少个空格)
dfs(cnt);//(递归深搜)
cout<<str<<endl;//(输出方案)
}
return 0;
}