數(shù)獨(dú)-Sudoku

#include<iostream>
#include <vector>
#include <fstream>
using namespace std;
bool isValid(std::vector<std::vector<int>> &chess,
                    int x,int y,int val){
    bool ret=true;
    for(int j=0;j<9;j++){
        if(j==y) continue;
        if(val==chess.at(x).at(j)){
            ret=false;
            return ret;
        }
    }
    for(int i=0;i<9;i++){
        if(i==x) continue;
        if(val==chess.at(i).at(y)){
            ret=false;
            return ret;
        }
    }
    int new_x=x/3,new_y=y/3;
    int tl_x=new_x*3,tl_y=new_y*3;
    for(int i=tl_x;i<tl_x+3;i++){
        for(int j=tl_y;j<tl_y+3;j++){
            if(i==x&&j==y){
                continue;
            }
            if(val==chess.at(i).at(j)){
                ret=false;
                return ret;
            }
        }
    }
    return true;
}
struct Pos{
    Pos(int i,int j):x(i),y(j),val(0){}
    int x;
    int y;
    int val;
};
class Solution{
public:
    bool backTracking(std::vector<std::vector<int>> &matrix,
                      std::vector<Pos>& pos,int n){
        bool ret=false;
        if(n==pos.size()){
            return true;
        }
        for(int i=1;i<=9;i++){
            pos.at(n).val=i;
            if(isValid(matrix,pos.at(n).x,pos.at(n).y,i)){
                matrix.at(pos.at(n).x).at(pos.at(n).y)=i;
                ret=backTracking(matrix,pos,n+1);
                if(ret){
                    break;
                }else{
                    matrix.at(pos.at(n).x).at(pos.at(n).y)=0;
                }
            }
        }
        return ret;
    }
    void findSolution(std::vector<std::vector<int>> &matrix,
                      std::vector<Pos>& pos){
        bool ret=false;
        for(int i=1;i<=9;i++){
            pos.at(0).val=i;
            if(isValid(matrix,pos.at(0).x,pos.at(0).y,i)){
                matrix.at(pos.at(0).x).at(pos.at(0).y)=i;
                ret=backTracking(matrix,pos,1);
                if(ret){
                    break;
                }else{
                    matrix.at(pos.at(0).x).at(pos.at(0).y)=0;
                }
            }
        }
        if(ret){
            int len=pos.size();
            for(int i=0;i<len;i++){
                matrix.at(pos.at(i).x).at(pos.at(i).y)
                        =pos.at(i).val;
            }
        }
    }
};
int main(){
    //std::ifstream in("data.txt");
    //std::streambuf *cinbackup;
    //cinbackup=cin.rdbuf(in.rdbuf());
    std::vector<std::vector<int>> matrix;
    matrix.resize(9,std::vector<int>());
    std::vector<Pos> zero_pos;
    for(int i=0;i<9;i++){
        for(int j=0;j<9;j++){
            int num;
            std::cin>>num;
            matrix.at(i).push_back(num);
            if(0==num){
                zero_pos.push_back(Pos(i,j));
            }
        }
    }
    Solution so;
    so.findSolution(matrix,zero_pos);
    for(int i=0;i<9;i++){
        for(int j=0;j<9;j++){
            if(8==j){
                std::cout<<matrix.at(i).at(j)<<std::endl;
            }else{
                 std::cout<<matrix.at(i).at(j)<<" ";
            }
        }
    }
    return 0;
}

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成,瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明:文章內(nèi)容(如有圖片或視頻亦包括在內(nèi))由作者上傳并發(fā)布,文章內(nèi)容僅代表作者本人觀點(diǎn),簡(jiǎn)書系信息發(fā)布平臺(tái),僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容