回溯数独问题

---

---

如图

分析：

分了两种方法，第一种按大小走，第二种按照坐标。
其中，第二种需注意：
　　1、到n-1行/列的时候判断
　　2、切莫忽略了a[x][y]!=0的情况，而且分a[x][y]==0的情况和a[x][y]!=0的情况，分别讨论

第一种方法：

/*
    方法一：traceback(t);t代表0...80的某个数 
*/ 
#include<stdio.h>
#define n 9
int a[n][n]={0,0,5,3,0,0,0,0,0,
             8,0,0,0,0,0,0,2,0,
             0,7,0,0,1,0,5,0,0,
             4,0,0,0,0,5,3,0,0,
             0,1,0,0,7,0,0,0,6,
             0,0,3,2,0,0,0,8,0,
             0,6,0,5,0,0,0,0,9,
             0,0,4,0,0,0,0,3,0,
             0,0,0,0,0,9,7,0,0};

bool OK(int x,int y){
    int x0=x/3*3;
    int y0=y/3*3;
    
    //判断行是否相同
    for(int i=0;i<n;i++){             //判断行和列是否相同时，因为题目给的数独中已经 
        if(a[x][i]==a[x][y]&&i!=y)    //有一部分的值了，我保证第x行第0列到y-1列不和我相同 
            return false;             //的同时，还得保证第y列以后的初始就带的值也不能相同 
    }                                 //所以要从0遍历到n-1 

    //判断列是否相同
    for(int i=0;i<n;i++){
        if(a[i][y]==a[x][y]&&i!=x)
            return false;
    } 
    
    for(int i=x0;i<x0+3;i++){
        for(int j=y0;j<y0+3;j++){
            if(a[i][j]==a[x][y]&&i!=x&&j!=y)
                return false;
        }       
    }
    return true;
}

void traceback(int t){
    if(t==81)//0到80都走完了,并且能走到最后，结果一定是正确的 
    {
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                printf("%d",a[i][j]);
            }
            printf("\n");
        } 
        return;
    } 
    int x=t/9;  //横坐标 
    int y=t%9;  //纵坐标
    if(a[x][y]!=0){//表示a[x][y]已经有值了
        traceback(t+1);
    } else{
        for(int i=1;i<10;i++){//i是给数独赋值的，只能是1到9，不能从0开始 
            a[x][y]=i;
            if(OK(x,y)){
                traceback(t+1);
            }
            a[x][y]=0;
        }
    }
}

int main(){
    traceback(0);
    return 0;
}

运行截图

---

第二种方法：

/*
    方法二：traceback(x,y);x,y 是下标为x行，y列的数字，且采用按列走，
            与“拉丁矩阵”正好相反  
*/
#include<stdio.h> 
#define n 9
int a[n][n]={0,0,5,3,0,0,0,0,0,
             8,0,0,0,0,0,0,2,0,
             0,7,0,0,1,0,5,0,0,
             4,0,0,0,0,5,3,0,0,
             0,1,0,0,7,0,0,0,6,
             0,0,3,2,0,0,0,8,0,
             0,6,0,5,0,0,0,0,9,
             0,0,4,0,0,0,0,3,0,
             0,0,0,0,0,9,7,0,0};

bool OK(int x,int y){
    int x0=x/3*3;
    int y0=y/3*3;
    
    for(int i=0;i<n;i++){  //判断行是否相同 
        if(a[x][y]==a[x][i]&&y!=i)
            return false;
    }
    
    for(int i=0;i<n;i++){  //判断行是否相同 
        if(a[x][y]==a[i][y]&&x!=i)
            return false;
    }
    
    for(int i=x0;i<x0+3;i++){
        for(int j=y0;j<y0+3;j++){
            if(a[x][y]==a[i][j]&&i!=x&&j!=y)
                return false; 
        }
    }
    return true;
} 

void traceback(int x,int y){   //按列走 
int oldvalue=0;
    if(a[x][y]!=0){  //这个位置已经放了值
        if(y==n-1){
            if(x==n-1){
                for(int i=0;i<n;i++){
                    for(int j=0;j<n;j++){
                        printf("%3d",a[i][j]);
                    }
                    printf("\n");
                } 
                return;
            }else{
                traceback(x+1,y);
            }
        }else{
            if(x==n-1){
                traceback(0,y+1);
            }else{
                traceback(x+1,y); 
            }
        }
    }else{   //还没有放值，所以下面操作是给它放一个数
        for(int num=1;num<=n;num++){
            oldvalue=a[x][y];
            a[x][y]=num;
            if(OK(x,y)){
                if(y==n-1){         //到达最后一列 
                    if(x==n-1){     //最后一行 
                        for(int i=0;i<n;i++){
                            for(int j=0;j<n;j++){
                                printf("%3d",a[i][j]);
                            }
                            printf("\n");
                        } 
                        return; 
                    }else{  
                        traceback(x+1,y);
                    }
                }else{
                    if(x==n-1){ 
                        traceback(0,y+1);
                    }else{
                        traceback(x+1,y);
                    }
                }
            }   
            a[x][y]=oldvalue;
        } 
    }   
}

int main(){
    traceback(0,0);
    return 0;
}

运行截图