八皇后与任性的百度

Posted on | In | | 浏览 次

面试

上周五去百度面试，一面还算顺利，问了一些基础的信息，主要是为了看对linux、mysql一些理解的深度，然后就是二面，二面先问的网络相关的东西，之后面试官直接丢过来一个八皇后问题！！完全没有复习算法的我都震惊了，一脸懵逼，幸亏这个问题是当初14年大四一个人在出租房学习的时候做过的问题，记得很清楚是在《C和指针》里面其中一章讲数组的课后题！！当时稳了一下就开始回忆问题的解题思路，当然啦因为时间太久，忘记了，于是跟面试官把思路讲了出来，所以今天特意找了一下当年写的代码！整理一下，我表示真的是人生处处不意外啊。。。😂

解题思路

关于八皇后这么著名的问题简单介绍一下就是8X8的方格，然后要把8个皇后分别放置于棋盘上，最终的摆放让她们彼此之间不能相互吃掉，换句话说就是横着竖着斜着方向上不能有两个皇后同时在，详细的介绍在wiki上有，这里不再赘述，这个问题在编程当中是个很经典的问题，之所以经典是因为解决这个问题需要用到至少两种思想：

  1. 递归
  2. 回溯

递归

递归应该稍微好理解一些，对于我们来说，每放置一颗棋子相当于是从一个N x N的棋盘变成了一个 （N-1）x N的棋盘，所以我们只要每放置一颗棋子就将其关联位置好就OK，直至放下最后一颗棋子表示正确结束

回溯

考虑到程序的性能问题，我们当然可以每次放置棋子，然后每次都重新开辟空间，但是这就带来一个问题，极端情况下或许我们需要开辟 N x N次NxN的空间，或者稍微优化一下我们每次只是重置开辟的内存空间，可是这样其实还是效率很低，这个时候就需要用到回溯的技巧了，所谓回溯简单来说就是当我本次计算发现不ok那么我便会退到本次操作之前的状态，这样我们就能在第前一次的基础上重新计算，而不是完全重头再来：）

下面上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<stdio.h>
#define MAX 9
int count;
int success;
int set_points_i(int a[][MAX],int line,int col,int i)//其实只需要设置一个点下方范围的区域即可可以减少大概25行代码
{
	int loop;
	int reg;
	for(loop = 0;loop < MAX;loop++)
	{
		a[loop][col]+=i;
		a[line][loop]+=i;
	}
	reg = line - col;
	if(reg>=0)
	{
		loop = reg;
		while(loop < MAX)
		{
			a[loop][loop - reg]+=i;
			loop++;
		}
	}
	else
	{
		loop = 0;
		while((loop - reg) < MAX)
		{
			a[loop][loop - reg]+=i;
			loop++;
		}
	}
	reg = line + col;
	if(reg>=MAX-1)
	{
		loop =reg - MAX-1;
		while(loop < MAX)
		{
			a[loop][reg - loop]+=i;
			loop++;
		}
	}
	else
	{
		loop = 0;
		while(reg - loop >= 0)
		{
			a[loop][reg - loop]+=i;
			loop++;
		}
	}
	a[line][col] = 0;
	/*
	if(i==1)a[line][col]+=2;
	else a[line][col]-=2;
	*/
}
void display_matrix(int a[][MAX])//正方形矩阵
{
	int loopi;
	int loopj;
	for(loopi = 0;loopi < MAX;loopi++)
	{
		for(loopj = 0;loopj<MAX;loopj++)
		{
			printf(" %d ",a[loopi][loopj]);
		}
		printf("\n");
	}	
}
int place_queen(int a[][MAX],int line)
{
	count++;
	int col;
	int res;
	for(col = 0;col < MAX;col++)
	{
		if(!a[line][col])
		{
			set_points_i(a,line,col,1);
			if(line == MAX-1)
			{
				display_matrix(a);//  succeed 加上return会出现负值
				success++;
			}
			if(line<MAX-1)place_queen(a,line+1);
			set_points_i(a,line,col,-1);
		}
	}
	return 0;
}
int a[MAX][MAX];
void main(void)
{
	place_queen(a,0);
	printf("Success:%d\n",success);
}

不得不说，现在回看代码一时还想不起来当初自己是什么实现的，还需要画图回忆一下才OK。

上面的代码分为两个主体部分：

  1. place_queen函数用来控制递归内部逻辑，包括每一次调用只放置一颗棋子以及防止失败时候的回溯操作，和最终判定棋子放置结束的逻辑判断
  2. set_points_i函数用来正确设置每次放置棋子之后棋盘的数据变化，包括放置棋子的+1，以及回溯的-1操作

代码编译之后运行会将棋盘打印出来，棋子为0的表示每个王后的放置位置

突然发现了当年写代码留下的备注“其实只需要设置一个点下方范围的区域即可可以减少大概25行代码”，才想起来当初自己在写的时候每次放置会将棋子的上下区域都会进行处理，其实我们每次只需要在放置棋子后正确设置棋子下方的盘位就好，这里进行一版修改，挑战一下当年的自己😂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<stdio.h>
#define MAX 8
int count;
int success;
int set_points_i(int a[][MAX],int line,int col,int i)//其实只需要设置一个点下方范围的区域即可可以减少大概25行代码
{
	int loop,nl,nc;//new line,new col
	int reg_sum;
	reg_sum = line + col;
	for(loop = line+1;loop < MAX;loop++)
	{
		a[loop][col]+=i;
		nc = reg_sum - loop;
		if (nc >= 0)
		{
			a[loop][nc] += i;
		}
		nc = 2 * col - nc;
		if (nc <= MAX-1)
		{
			a[loop][nc] +=i;
		}
	}
	//a[line][col] = 0;
	/*
	if(i==1)a[line][col]+=2;
	else a[line][col]-=2;
	*/
}
void display_matrix(int a[][MAX])//正方形矩阵
{
	int loopi;
	int loopj;
	for(loopi = 0;loopi < MAX;loopi++)
	{
		for(loopj = 0;loopj<MAX;loopj++)
		{
			printf(" %d ",a[loopi][loopj]);
		}
		printf("\n");
	}	
}
int place_queen(int a[][MAX],int line)
{
	count++;
	int col;
	int res;
	for(col = 0;col < MAX;col++)
	{
		if(!a[line][col])
		{
			set_points_i(a,line,col,1);
			if(line == MAX-1)
			{
				display_matrix(a);//  succeed 加上return会出现负值
				success++;
			}
			if(line<MAX-1)place_queen(a,line+1);
			set_points_i(a,line,col,-1);
		}
	}
	return 0;
}
int a[MAX][MAX];
void main(void)
{
	place_queen(a,0);
	printf("Success:%d\n",success);
}

第二版的代码略微做了修改，只关心每个N-1的棋盘，并且在置为的时候也只处理后续需要的，性能应该会有少许提升，我在实现代码的时候是画了棋盘的观察棋子坐标顺序的所以在理解的时候应该是边画边理解，在wiki上面关于该问题的代码简单看了一下，他的实现思路和我这里不太一样，没有细看，但是感觉他的更加抽象，代码也更加简洁，联想到在知乎上很多人贴的十几行就能实现的代码。我表示啊，人跟人思考的维度真是很不一样，对于大神只能膜拜了：）

转载请注明来源链接 http://just4fun.im/2017/11/19/八皇后与任性的百度/ 尊重知识,谢谢:)