计蒜客：数独（DFS）

样例输入

* 2 6 * * * * * *
* * * 5 * 2 * * 4
* * * 1 * * * * 7
* 3 * * 2 * 1 8 *
* * * 3 * 9 * * *
* 5 4 * 1 * * 7 *
5 * * * * 1 * * *
6 * * 9 * 7 * * *
* * * * * * 7 5 *

样例输出

1 2 6 7 3 4 5 9 8
3 7 8 5 9 2 6 1 4
4 9 5 1 6 8 2 3 7
7 3 9 4 2 5 1 8 6
8 6 1 3 7 9 4 2 5
2 5 4 8 1 6 3 7 9
5 4 7 2 8 1 9 6 3
6 1 3 9 5 7 8 4 2
9 8 2 6 4 3 7 5 1

题解：这道题目类似八皇后问题，只不过八皇后是对每一行进行 1−8 的尝试，而这道题目是对每个空进行 1−9 的尝试。而且这道题目搜索到一种可行解就可以结束了。
标记方法为标记某行某个数字是否出现，标记某列某个数字是否出现，标记某个小方格某个数字是否出现。
注意：0-8个宫的标记方法为：行号/3*3+列号/3，scanf的c%前面加上空格，抵消输入空格的影响

#include<bits/stdc++.h>
using namespace std;
char mp[20][20];
bool f;
bool r[20][20],c[20][20],gong[20][20];
void dfs(int x,int y){
    
    if(f){
    
        return;//已经找到一种情况，退出
    }
    if(x==9){
    //到行末了找到一种合法情况打印
        for(int i=0;i<9;i++){
    
        for(int j=0;j<9;j++){
    
            cout<<mp[i][j];
            if(j!=8) cout<<" ";
            else cout<<endl;
        }
    }
        f=true;
        return;
    }
    if(y==9){
    //如果一列放置完，放置下一行
        dfs(x+1,0);
        return;
    }
    if(mp[x][y]!='*'){
    //如果已经有数字了，继续放置下一列
        dfs(x,y+1);
        return;
    }
    
    for(int j=1;j<=9;j++){
    //对一个位置枚举放置1-9的情况
        if(!r[x][j]&&!c[y][j]&&!gong[x/3*3+y/3][j]){
    //如果行，列，宫都没有这个数，则可以放置
            r[x][j]=true;
            c[y][j]=true;
            gong[x/3*3+y/3][j]=true;
            mp[x][y]='0'+j;
            dfs(x,y+1);//继续放置下一列
            r[x][j]=false;//回溯
            c[y][j]=false;
            gong[x/3*3+y/3][j]=false;
            mp[x][y]='*';
        }
    }
}
int main(){
    
    for(int i=0;i<9;i++){
    
        for(int j=0;j<9;j++){
    
            scanf(" %c",&mp[i][j]);//注意scanf的c%前面加上空格，抵消输入空格的影响
        }
    }
    for(int i=0;i<9;i++){
    
        for(int j=0;j<9;j++){
    
            if(mp[i][j]!='*'){
    //预处理标记
                r[i][mp[i][j]-'0']=true;
                c[j][mp[i][j]-'0']=true;
                gong[i/3*3+j/3][mp[i][j]-'0']=true;
            }
        }
    }
    dfs(0,0);
    return 0;
}