题解 | #Sudoku#2023华为编程笔试牛客网练习C

#include<bits/stdc++.h>
#define N 9
using namespace std;

bool row[N][N],col[N][N],block[N][N];
int a[N][N];
bool flag=false;

void init()
{
    memset(row,0,sizeof row);
    memset(col,0,sizeof col);
    memset(block,0,sizeof block);
    flag=false;
}

int getBlock(int x,int y)
{
    return (x/3)*3+(y/3);
}

bool check(int x,int y,int num)
{
    return !row[x][num]&&!col[y][num]&&!block[getBlock(x,y)][num];
}

void dfs(int x,int y)
{
    if(flag) return ;
    if(x==N)
    {
        flag=true;
        return ;
    }
    if(a[x][y])
    {
        if(y==N-1) dfs(x+1,0);
        else dfs(x,y+1);
    }
    else
    {
        for(int i=0;i<N;i++)
        {
            if(check(x,y,i))
            {
                a[x][y]=i+1;
                row[x][i]=col[y][i]=block[getBlock(x,y)][i]=true;
                if(y==N-1) dfs(x+1,0);
                else dfs(x,y+1);
                if(flag) return ;
                row[x][i]=col[y][i]=block[getBlock(x,y)][i]=false;
                a[x][y]=0;
            }
        }
    }
}

int main()
{
    init();
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
        {
            cin>>a[i][j];
            if(a[i][j])
            {
                int num=a[i][j]-1;
                row[i][num]=true;
                col[j][num]=true;
                block[getBlock(i,j)][num]=true;
            }
        }
    dfs(0,0);
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
            cout<<a[i][j]<<" ";
        cout<<endl;
    }
    return 0;
}

数独是一个数字逻辑游戏，玩家需要根据已知的数字填充空缺位，使得每一行、每一列、每一个小九宫格内都包含1到9的数字，且不重复。

解题思路是使用深搜的方法。

首先，初始化，用三个布尔数组记录每一行、每一列、每一个小九宫格内的数字是否出现过。

然后，我们从第一行第一列开始，判断当前位置是否已经有数字：

• 如果已经有数字，则直接判断下一个位置；
• 如果没有数字，则从1到9枚举每一个数字，判断这个数字是否在该行、该列、该小九宫格内都没有出现过。

如果满足要求，就把该数字放入该位置并标记为已出现，继续判断下一个位置；

如果不满足要求，则回溯，重置该位置的数字，并把该数字在行、列、小九宫格内的标记重置。

如果我们搜索到最后一行最后一列，说明我们已经成功搜索到了一种可能的解，此时就可以退出搜索。

最后，如果

搜索成功，我们就可以输出最终的数独盘面。

总体来说，数独问题可以使用深搜来解决，每一个位置都枚举所有可能的数字，如果满足要求，就继续搜索，如果不满足要求，就回溯。直到找到一种可能的解，就可以输出结果。