
分析:
分了两种方法,第一种按大小走,第二种按照坐标。
其中,第二种需注意:
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;
}

网友评论