DFS(华为数独题解）

• 实际数独可能会解出多组，所以只能通过50%案例。

//华为数独题目
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
vector<vector<int>> checkBoard;
//存放是否被访问的空棋盘
struct Pos{
    int x;
    int y;
    bool isVis;
    Pos():x(0),y(0),isVis(false){};
};
vector<Pos> emptyPos;
bool isOver = false;
void printChecer(){
    for(int i = 0;i < checkBoard.size();i++){
        vector<int> &row = checkBoard[i];
        string str_row="";
        for(auto ele:row){
            str_row = str_row + to_string(ele) +" ";
        }
        if(str_row != "")
            cout<<str_row.substr(0,str_row.size()-1)<<"\n";
    }
}
//bool isOver = false;
//输入为当前空行的索引
void dfs(int index){
    //到了终止条件
    if(index == emptyPos.size()){
        //isOver = true;

        printChecer();
        //checkBoard[emptyPos.back().x][emptyPos.back().y] = 0;
        isOver  =true;
        //cout<<"======="<<endl;
        return;
    }

    //取出当前的在棋盘上的索引
    int x = emptyPos[index].x;
    int y = emptyPos[index].y;
    //cout<<"x:"<<x<<",y:"<<y<<endl;

    //检测该位置是否合适1-9之间的数字
    for(int num = 1;num < 10;num++){
        bool isRowOk = true, isColOk = true, isQuareOk = true;
        //检查x行是否满足条件
        for(int i = 0; i < 9;i++){
            if(checkBoard[x][i] == num) {
                isRowOk = false;
                break;
            }
        }
        if(!isRowOk) continue;

        //检查y列是否满足条件
        for(int i = 0; i < 9;i++){
            if(checkBoard[i][y] == num) {
                isColOk = false;
                break;
            }

        }
        if(!isColOk) continue;

        //检查在3X3方块内是否满足
        int xIndes = 0,yIndes = 0;
        for(int i = 2; i < 9;i += 3){
            if(x < i && xIndes == 0){
                xIndes = i;
            }
            if(y < i && yIndes == 0){
                yIndes = i;
            }
            if(yIndes != 0 && xIndes != 0) break;
        }
        for(int i = xIndes; i >= xIndes -3;i--){
            for(int j = yIndes; j < yIndes-3;j--){
                if(checkBoard[i][j] == num){
                    isQuareOk = false;
                    break;
                }
            }
            if(!isQuareOk) break;
        }
        if(!isQuareOk) continue;
        //没有到终止条件
        if(isColOk && isQuareOk && isRowOk){
            checkBoard[x][y] = num;
            dfs(index+1);
            
            if(isOver){
                return;
            }
            checkBoard[x][y] = 0;
        }
    }
}

int  main(){
    for(int i = 0; i< 9;i++){
        vector<int> row;

        for(int j = 0;j < 9;j++){
            int num;
            cin>> num;
            row.push_back(num);
            if(num ==0){
                //空棋盘
                Pos p;
                p.x = i;
                p.y = j;
                emptyPos.push_back(p);
            }
        }
        checkBoard.push_back(row);
    }
    //cout<<"size:"<<emptyPos.size()<<endl;
    dfs(0);

    return 0;
}