本文共 2827 字，大约阅读时间需要 9 分钟。

填入0~9的数字。要求：连续的两个数字不能相邻。

一共有多少中可能的填数方案？

一、回溯

可参考，在 这篇文章中也有其他递归练习。

1、对于一个待填的数字k，首先判断该数是否在前面的格子内使用过；

2、如果该数字没有使用过，判断该格子的八个方向上有没有k+1或k-1；

3、填入到一行的最后一个格子，换下一行的第一个格子开始判断；

4、填到最后一个格子，总num++。

#include
   
    using namespace std;int a[3][4];int num = 0;int v[10] = {0};int pd(int k, int i, int j){//这个就是判断	if (i-1>=0 && (a[i - 1][j] == k - 1 || a[i - 1][j] == k + 1) )		return 0;	if (j-1>=0 && (a[i][j - 1] == k + 1 || a[i][j - 1] == k - 1) )		return 0;	if (i-1>=0 && j-1>=0 && (a[i - 1][j - 1] == k + 1 || a[i - 1][j - 1] == k - 1))		return 0;	if (i-1>=0 && j+1<4 && (a[i - 1][j + 1] == k + 1 || a[i - 1][j + 1] == k - 1))		return 0;	if (j + 1 < 4 && (a[i][j + 1] == k + 1 || a[i][j + 1] == k - 1))		return 0;	if (i + 1 < 3 && (a[i + 1][j] == k + 1 || a[i + 1][j] == k - 1))		return 0;	if (i + 1 < 3 && j - 1 >= 0 && (a[i + 1][j - 1] == k + 1 || a[i + 1][j - 1] == k - 1))		return 0;	if (i + 1 < 3 && j + 1 < 4 && (a[i + 1][j + 1] == k + 1 || a[i + 1][j + 1] == k - 1))		return 0;	return 1;}void f(int i, int j){	if (i == 2 && j==3)	{//已经填入到最后一个说明这种情况满足，num++		num++;		return;	}	for (int k = 0; k <= 9; k++)	{		if (pd(k, i, j)&&v[k]==0) 		{//判断8个方向是否能填入，并且是否用过			v[k] = 1;			a[i][j] = k;			if (j == 3)//到达最后一列记得换行				f(i + 1, 0);			else				f(i, j + 1);			a[i][j] = -9;			v[k] = 0;		}	}	return;}int main(){	for (int i = 0; i < 3; i++)//这里我将所有数赋值-9，因为第一个和最后一个不需要赋值，避免干扰	{		for (int j = 0; j < 4; j++)		{			a[i][j] = -9;		}	}	f(0, 1);	cout << num << endl;	return 0;}
   

哦对，上面这段代码，自己认为有个小改进，把 if (pd(k, i, j) && v[k] == 0) 这条语句，改成 if (v[k] == 0 && pd(k, i, j)) 。

二、深搜DFS

其实也并不知道这里和上面的有什么区别，因为主要的框架代码是相同的……

这段代码比上段代码的好处在于：上段代码中判断八个方向是用暴力判断的，而这段代码不是。

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #define mem(a,b) memset(a,b,sizeof(a))#define inf 0x3f3f3f3f#define N 1000+10#define LL long longusing namespace std;int map[10][10];int vis[10];int cnt = 0;int go[4][2] = { {0,-1}, {-1,-1}, {-1,0}, {-1,1}};//因为是从左到右从上到下依次，所以只需要搜索下，左下，左，左上，上四个方向即可int judge(int x, int y, int num) //x、y分别为待填格子的坐标，num是代填数字{ for(int i = 0; i < 4; ++i) { int xx = x + go[i][0]; int yy = y + go[i][1]; if (xx >= 0 && xx <= 2 && yy >= 0 && yy <= 3)//判断是否越界 { if(map[xx][yy] == num - 1 || map[xx][yy] == num + 1)//判断数字是否相邻 { return 0; } } } return 1;}void dfs(int x, int y){ if (x == 2 && y == 3) //(2,3)点时结束点的位置 { cnt++; return; } if (y > 3) //越界的时候，搜索下一层 { dfs(x+1, 0); } else { for(int i = 0; i <= 9; ++i) //枚举要填的数 { if(!vis[i] && judge(x, y, i)) { vis[i] = 1; map[x][y] = i;//填数 dfs(x, y+1); map[x][y] = -100;//搜索完毕，取消标记 vis[i] = 0; } } }}int main(){ for (int i = 0; i <= 2; ++i) { for (int j = 0; j <= 3; ++j) { map[i][j] = -100; //初始化一个不在0~9之间的值 } } dfs(0,1);//因为(0,0)点没有,所以从(0,1)点搜索 cout << cnt << endl; return 0;}
          
         
        
       
      
     
    
   

这里贴两个讲回溯与深搜的文章：

转载地址：http://jvtai.baihongyu.com/