点击查看原文
9X9方格数独填数，主要就是9个3X3小方格的bool查重数组的设计， 这里利用 （i-1）/3，（j-1）/3的方式把小方格的点的向量合并成一个向量，再利用3进制的移位操作变换成线性，如此九个3x3小方格也能和行列一样查重了。
代码基本没变，在原文的基础上加了点注释，毕竟本人ACM菜鸡QAQ
#include <iostream> #include <cstdio> #include <cstring> using namespace std; int map[10][10],count1; //count1表示初始数独图中还空的位置 bool row[10][10],coloumn[10][10],cr[10][10];//用来标记行，竖，小方格已经填过了哪些数 struct p { int x,y; }point[100];//标记每个格子的横纵坐标 int cxbfine(int i,int j)//规定每个3*3方格的号码 { return ((i-1)/3)*3+(j-1)/3; // 这里是利用三进制数将一个二维向量映射到一维上 } int dfs(int n)//进行深搜，符合条件往下，填不下就回溯 { if(n>count1) return 1; for(int i=1;i<=9;i++) if(!row[point[n].x][i] && !coloumn[point[n].y][i] && !cr[cxbfine(point[n].x,point[n].y)][i]) { //处理，方便搜索的进行 row[point[n].x][i]=true; coloumn[point[n].y][i]=true; cr[cxbfine(point[n].x,point[n].y)][i]=true; map[point[n].x][point[n].y]=i; if(dfs(n+1)) return 1; //深搜 row[point[n].x][i]=false; coloumn[point[n].y][i]=false; cr[cxbfine(point[n].x,point[n].y)][i]=false; //如果搜索不成功，回溯的时候清除搜索痕迹 } return 0; } int main() { int n,i,j; cin>>n; while(n--) { count1=0; memset(row,false,sizeof(row)); memset(coloumn,false,sizeof(coloumn)); memset(cr,false,sizeof(cr)); for(i=1;i<=9;i++)//输入并判断 for(j=1;j<=9;j++) { scanf(" ",&map[i][j]); if(map[i][j]) { row[i][map[i][j]]=true; coloumn[j][map[i][j]]=true; cr[cxbfine(i,j)][map[i][j]]=true; } else { count1++; point[count1].x=i; point[count1].y=j; } } dfs(1); for(i=1;i<=9;i++) { for(j=1;j<=9;j++) printf("%d",map[i][j]); //cout<<map[i][j]; printf("\n"); //cout<<endl; } } return 0; }
