题解 | #Sudoku#

不用调试器实在是搞不定啊。。。。 递归，永远的神。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N=9;
vector<vector<int>> sudoku(9,vector<int>(9,0));
struct point{
    int x;
    int y;
};

vector<int> judge(point p){
    vector<int>vec;
    vector<int>heng = sudoku[p.x];
    vector<int>shu;
    for(int i =0 ;i<9;i++)
    {
        shu.push_back(sudoku[i][p.y]);
    }
    vector <int> nine;
    int qidian=p.x/3;
    int yqidian = p.y/3;
    for(int i = qidian*3;i<qidian*3+3;i++)
        for(int j = yqidian*3;j<yqidian*3+3;j++){
            nine.push_back(sudoku[i][j]);
        }
    heng.insert(heng.end(),shu.begin(),shu.end());
    heng.insert(heng.end(),nine.begin(),nine.end());
    for(int i = 1 ;i<=9;i++)
    {
        if(find(heng.begin(),heng.end(),i)==heng.end())
            vec.push_back(i);
    }
    
    return vec;
    
    
}
bool solve(point p,vector<point>&vec,int index){
    bool flag = false;
    if(index>=vec.size())
        return true;
    p=vec[index];
    vector<int> possible= judge(p);
    if(possible.size()>0){
    for(int i =0 ;i<possible.size();i++){
        sudoku[p.x][p.y]=possible[i];
        flag = solve(vec[index],vec,index+1);
       if( flag==false)
         sudoku[p.x][p.y]=0;
        else
            break;
    }
    }
    else
        return false;
    return flag;
    
}
int main()
{
    vector<point> vec;
    for(int i =0;i<N;i++)
        for(int j =0;j<N;j++)
        {
            cin>>sudoku[i][j];
            if(sudoku[i][j]==0)
                vec.push_back({i,j});
        }
    point p = vec[1];
    judge(p);
    solve(p,vec,0);
    for(int i =0 ;i< N;i++)
    { for(int j =0 ;j<N;j++)
            cout<<sudoku[i][j]<<" ";
        cout<<endl;}
    return 0;
}