欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

回溯法递归——“数独”

程序员文章站 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;	
	}	
}

运行结果:

运行结果如图:
回溯法递归——“数独”

相关标签: 递归算法