（算法）数独问题

题目：

数独问题：9*9的矩阵，要求每一行，每一列，每个九宫格都是1-9这九个数字且不能重复。

给定一9*9矩阵，里面有部分数空缺，要求找出满足上述要求的一个矩阵。

如：

思路：

代码：

 

#include<iostream>
#include<string.h>
using namespace std;

class Sudoku{
    private:
        int m_chess[9][9];
        int m_result[9][9];
        bool b_solve;

    public:
        Sudoku(int chess[9][9]){
            memcpy(m_chess,chess,sizeof(m_chess));
            b_solve=false;
        }
    
        bool IsValid(int i,int j){
            int  t=m_chess[i][j];
            int k;
            for(k=0;k<9;k++){
                if(j!=k && t==m_chess[i][k])
                    return false;
                if(i!=k && t==m_chess[k][j])
                    return false;
            }

            int iGrid=(i/3)*3;
            int jGrid=(j/3)*3;
            int k1,k2;
            for(k1=iGrid;k1<iGrid+3;k1++){
                for(k2=jGrid;k2<jGrid+3;k2++){
                    if(k2==j && k1==i)
                        continue;
                    if(t==m_chess[k1][k2])
                        return false;
                }
            }
            return true;
        }    

        bool R_Sudoku(){
            int i,j,k;
            for(i=0;i<9;i++){
                for(j=0;j<9;j++){
                    if(m_chess[i][j]==0){
                        for(k=1;k<10;k++){
                            m_chess[i][j]=k;
                            if(IsValid(i,j) && R_Sudoku()){
                                if(b_solve)
                                    memcpy(m_result,m_chess,sizeof(m_chess));
                                b_solve=true;
                                return true;
                            }
                            m_chess[i][j]=0;
                        }
                        return false;
                    }
                }
            }
            return true;
        }

        void Print(bool flag){
            if(flag){
                for(int i=0;i<9;i++){
                    for(int j=0;j<9;j++){
                        cout<<m_chess[i][j]<<" ";
                    }
                    cout<<endl;
                }
            }
            else{
                for(int i=0;i<9;i++){
                    for(int j=0;j<9;j++){
                        cout<<m_result[i][j]<<" ";
                    }
                    cout<<endl;
                }
            }
            cout<<endl;
        }
};

int main(){
    int chess[9][9]={
        {0,4,2,0,6,3,0,0,9},
        {6,0,0,0,1,0,0,0,5},
        {3,0,0,0,2,0,4,8,0},
        {1,0,0,5,0,2,6,0,8},
        {4,0,0,0,0,7,0,0,1},
        {9,0,5,6,0,0,0,0,7},
        {0,3,6,0,5,0,0,0,2},
        {2,0,0,0,7,0,0,0,4},
        {7,0,0,2,9,0,8,5,0},
    };

    Sudoku sudoku(chess);
    sudoku.Print(true);
    sudoku.R_Sudoku();
    sudoku.Print(false);

    return 0;
}