【题解】数独(养生题)

【题解】数独(养生题)

暴力DFS，但是我的代码比较短，供大家参考。

优雅的暴力——搜索算法小结

不过我还用了随机化搜索，这种搜索思想可以防止被毒瘤出题人卡掉。有兴趣的可以看一下我的一篇总结里面写了搜索的一些技巧。

对于实现，我的思路是...不好说，但是这样写搜索又快又稳还短。

以上是洛谷装逼的话

//@winlere
#include <cstdio>
#include <algorithm>

using namespace std;
const int maxn=11;
int line[maxn][maxn],row[maxn][maxn];
int blok[maxn][maxn],loc[maxn][maxn];
int mp[maxn][maxn],seed[maxn];

void dfs(const int&x,const int&y){
      if(x>9) {
	    for(register int t=1;t<=9;++t,putchar('
'))
		  for(register int i=1;i<=9;++i)
			printf("%d ",mp[t][i]);
	    exit(0);
      }
      if(y>9) return dfs(x+1,1);
      if(mp[x][y]) return dfs(x,y+1);
      for(register int t0=1,t=seed[t0];t0<=9;++t0,t=seed[t0])
	    if(!line[x][t]&&!row[y][t]&&!blok[loc[x][y]][t])
		  line[x][t]=mp[x][y]=row[y][t]=blok[loc[x][y]][t]=t,
			dfs(x,y+1),
			line[x][t]=mp[x][y]=row[y][t]=blok[loc[x][y]][t]=0;
}

int main(){
      for(register int t=1;t<=9;++t) seed[t]=t;
      srand(19260817);
      random_shuffle(seed+1,seed+10);
      for(register int t=1;t<=9;++t)
	    for(register int i=1,t1;i<=9;++i)
		  scanf("%1d",&t1),loc[t][i]=3*((t-1)/3)+(i+2)/3,mp[t][i]=blok[loc[t][i]][t1]=line[t][t1]=row[i][t1]=t1;
      dfs(1,1);
}