题解 P1784 【数独】

· · 题解

实在想不出这题和矩阵有什么关系【好吧。。。用矩阵来存。。。】

DFS即可

因为是9*9，so，定义第i行第j列为n=i*9+j， i, j=0 . . 9

那么第n个数位于第n/9行第n mod 9列。。。


#include<cstdio>
int num[9][9]               //定义数组
bool flag                     //完成的标志
bool judge(int n,int k){        //判断在第n个位置放置k是否合法
    int x=n/9                       //行
    int y=n%9                     //列
    for(int i=0;i<9;i++){
        if(num[i][y]==k)return false            //行不合法，返回fasle
        else ;
        if(num[x][i]==k)return false            //列不合法，返回fasle
    }
    int fx=(x/3)*3
    int fy=(y/3)*3
    for(int i=fx;i<fx+3;i++){                              //九宫格内不合法，返回fasle
        for(int j=fy;j<fy+3;j++){
            if(num[i][j]==k)return false
        }
    }
    return true                          //全合法返回true
}
void dfs(int n){
    if(n>80)flag=false             //n>80即为完成了，修改flag来终止所有操作
                                                   //我对爆栈有心理恐惧。。。
    if(num[n/9][n%9])dfs(n+1)         //如果不为0，就跳过
    else if(flag){
        int x=n/9
        int y=n%9
        for(int tem=1;tem<10;tem++){
            if(judge(n,tem)){               //judge的定义见上面
                num[x][y]=tem
                dfs(n+1)
            }
            if(flag)num[x][y]=0           //如果程序进行到这里就说明上面的dfs失败了
                                                           //所以把num[x][y]复位
                                                           //可以去掉if(flag)试试结果，想想为什么。。
        }
    }
}
int main(){                        //主函数里的不解释，上面都说完了
    int i,j,k,n
    for(i=0;i<9;i++)for(j=0;j<9;j++){
        scanf("%d",&num[i][j])
    }
    flag=true
    dfs(0)
    for(i=0;i<9;i++){
        for(j=0;j<9;j++)printf("%d ",num[i][j])
        printf("\n")
    }
}

[color=#636363]HINT: To Copy is FORBIDDEN... [/color]