回溯法递归——“数独”
程序员文章站
2022-06-03 12:08:44
...
你一定听说过“数独”游戏吧！
玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个同色九宫内的数字均含1-9，不重复。
本题的要求就是输入数独题目，程序输出数独的唯一解。格式要求，输入9行，每行9个数字，0代表未知，其它数字为已知。输出9行，每行9个数字表示数独的解。
分析：
这题要用到哪些知识点呢？
1、数组的使用。（灵活运用数组的下标）
2、递归（回溯法递归）
思路：
一、设计数独的初始化（也就是键盘输入元素），
我这里用了一个函数将这一个步骤包装了起来。
void Initialize()//输入
{
int i,j;
long p;
printf("输入：");
for(i=0;i<9;++i)
{
j=8;
scanf("%ld",&p);//键盘输入一个长整型数
while(p)//利用循环把这个数的每一位放进数组中
{
num[i][j--]=p%10;
/*放的时候，为了让原有的顺序不变，我是倒着存入数组的，
因此这里j下标我是由大不断自减的*/
p/=10;
}
}
}
二、以上是输出，那么我们现在先把输出给写了吧。
（哈哈~我比较喜欢把简单的事先做了）
同样，我还是用了一个函数把这个过程包装了起来。
void Print()
{
int i,j;
printf("输出：\n");
for(i=0;i<9;++i)//9行
{
for(j=0;j<9;++j)//9列
{
printf("%d",num[i][j]);
}
printf("\n");//每输出一行，我就换行
}
}
三、下面就是我们递归调用的主要部分了！！！
先想一想有哪些基本步骤？
1、设置出口！在递归的程序中这是一个重点，一定要记得设置递归的出口，
也就是我们什么时候，在什么条件成立下，我们可以跳出这个函数结束程序。
填满81个“坑”，我们就结束程序。当然还有，别忘了乘机输出哦！
/*判断是否填完*/
if(n==81){//如果填完，输出并结束程序
Print();
return;
}
2、判断！判断上一次填入的数是否符合数独的条件。
（在该行、该列、该九宫格中是否是唯一的，不重复的？）
如果不符合要求，就结束这层递归，回溯！（怎么回溯？后面再细讲。）
/*判断前一个数填的是否符合要求*/
if(n>=1&&n<=81)
if(Judge(n-1)==0)//Judge是一个自定义函数，用来判断是否满足数独条件
return;
3、判断！这也是一个判断，判断下标n上是否有数？
如果有数我们就递归去判断下标n+1。
/*求行列下标*/
int x,y;
x=n/9;
y=n%9;
/*判断这个位置是否有数*/
if(num[x][y]!=0)
Sudoku(n+1);//递归
4、如果这个“坑”没有数（也就是为0的时候）。
我们就要给这个“坑”填上数！
/*填坑*/
if(num[x][y]==0)
{
int i;
for(i=1;i<10;++i)//只能填1~9的数字哦！
{
num[x][y]=i;
Sudoku(n+1);//递归
}
/*回溯*/
num[x][y]=0;
/*****************************************************************
回溯：
递归调用大致分为两种形式，一种是分治，一种就是回溯。
分治：参考[递归——分治](https://blog.csdn.net/qq_39841059/article/details/103596915)
回溯：回溯就相当于你在走迷宫的时候，有很多条路，你选择的其中一条路，结果走到尽头才发现走不通了，那么我们就要回到初始状态，重新来走。这样的操作就叫做回溯。
******************************************************************/
}
四、还有一个函数没写。就是判断这个数在该行、该列、该九宫格中，
是否都是唯一的，没有重复的！
int Judge(int n)
{
int x,y;
/*算出行列*/
x=n/9;//行
y=n%9;//列
int i,j;
/*判断该行有无重复*/
for(i=0;i<9;++i)
{
if(i==y) continue;
if(num[x][y]==num[x][i]) return 0;
}
/*判断该列有无重复数字*/
for(i=0;i<9;++i)
{
if(i==x) continue;
if(num[x][y]==num[i][y]) return 0;
}
/*判断该九宫格中是否有重复数字*/
int a,b;
a=x/3*3;
b=y/3*3;
for(i=a;i<a+3;++i)
{
for(j=b;j<b+3;++j)
{
if(i==x&&j==y) continue;
if(num[i][j]==num[x][y]) return 0;
}
}
return 1;
}
代码
以上是我的思路，不到之处在所难免。以下我把我的整体代码与大家分享！
/************************************
数独：回溯法递归
1、初始化函数
2、递归函数
3、判断在本行本列本九宫格中是否有重复
4、输出函数
************************************/
#include<stdio.h>
int num[9][9];//定义一个全局变量，存放数独中的数字
void Initialize();//初始化函数
void Print();//输出函数
int Judge(int n);//判断在该行该列该九宫格中是否重复
void Sudoku(int n);//回溯法递归函数
int main()
{
Initialize();
Sudoku(0);
return 0;
}
void Initialize()
{
int i,j;
int n;
printf("输入：\n");
for(i=0;i<9;++i)
{
j=9;
scanf("%d",&n);
while(n)
{
num[i][--j]=n%10;
n/=10;
}
}
}
void Print()
{
int i,j;
printf("输出：\n");
for(i=0;i<9;++i)
{
for(j=0;j<9;++j)
{
printf("%d",num[i][j]);
}
printf("\n");
}
}
int Judge(int n)
{
int x,y;
/*算出行列*/
x=n/9;//行
y=n%9;//列
int i,j;
/*判断该行有无重复*/
for(i=0;i<9;++i)
{
if(i==y) continue;
if(num[x][y]==num[x][i]) return 0;
}
/*判断该列有无重复数字*/
for(i=0;i<9;++i)
{
if(i==x) continue;
if(num[x][y]==num[i][y]) return 0;
}
/*判断该九宫格中是否有重复数字*/
int a,b;
a=x/3*3;
b=y/3*3;
for(i=a;i<a+3;++i)
{
for(j=b;j<b+3;++j)
{
if(i==x&&j==y) continue;
if(num[i][j]==num[x][y]) return 0;
}
}
return 1;
}
void Sudoku(int n)
{
/*判断前一个数填的是否符合要求*/
if(n>=1&&n<=81)
if(Judge(n-1)==0)
return;
/*判断是否填完*/
if(n==81){//如果填完，输出并结束程序
Print();
return;
}
/*求行列下标*/
int x,y;
x=n/9;
y=n%9;
/*判断这个位置是否有数*/
if(num[x][y]!=0)
Sudoku(n+1);
/*填坑*/
if(num[x][y]==0)
{
int i;
for(i=1;i<10;++i)
{
num[x][y]=i;
Sudoku(n+1);//递归
}
/*回溯*/
num[x][y]=0;
}
}
运行结果：
运行结果如图：
上一篇： 汉诺塔