搜索>>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-9
        if(!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