搜索P1784 数独

P1784 数独 链接此处

一句话题意

输入一个没填好的九宫格数独,把它填好

关键

同八皇后那道题一样,是用DFS+回溯,不过不同于八皇后可以一行一行枚举,数独里每一个数都是单一的,必须单独枚举
还有,个数处理必须格外小心,对于一个数上取整是(num-1)/a+1

int x=(pos-1)/9+1;//上取整,一般矩阵的行数
int y=(pos-1)%9+1;//一般矩阵的列数
int block_x=(x-1)/3+1;
int block_y=(y-1)/3+1;

没有太多可说,放一下DFS代码.

void dfs(int pos)//pos:位置数:一个一个枚举
{if(pos>81){for(int i=1;i<=9;i++,cout<<endl)for(int j=1;j<=9;j++)cout<<tu[i][j]<<' ';//输出exit(0);}int x=(pos-1)/9+1;//上取整,一般矩阵的行数int y=(pos-1)%9+1;//一般矩阵的列数int block_x=(x-1)/3+1;//宫数int block_y=(y-1)/3+1;if(tu[x][y])//如果数独本有数{dfs(pos+1);//下一个return;//后面枚举就不必了}for(int num=1;num<=9;num++)//枚举每个位置可能的1-9if(!vis[x][y] and !heng[x][num] and !shu[y][num] and !block[block_x][block_y][num]){vis[x][y]=1,tu[x][y]=num,heng[x][num]=1,shu[y][num]=1,block[block_x][block_y][num]=1;//标记dfs(pos+1);vis[x][y]=0,tu[x][y]=0,heng[x][num]=0,shu[y][num]=0,block[block_x][block_y][num]=0;//回溯}
}

知识网络

搜索=>DFS+回溯

2026年2月7日16:16:43