有趣的数据结构算法12——利用递归解决八皇后问题

迷南。 2021-11-22 09:14 442阅读 0赞

### 有趣的数据结构算法12——利用递归解决八皇后问题 ###

*  题目复述
 *  解题思路
 *  实现代码
 *  GITHUB下载连接

本次教程主要讲述如何利用递归解决八皇后问题，它和汉诺塔一样让人很难过。  
![在这里插入图片描述][20190723145057699.jpg_pic_center]

# 题目复述 #

据说西洋棋手都具有一些比较神奇的技能，上厕所的时候还喜欢想怎么下棋，终于有一天，在刺激气体的刺激下，八皇后问题横空出世。  
这是一个古老而著名的问题，在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问国际象棋上一共有多少个皇后。  
![在这里插入图片描述][20190725100017339.png_pic_center]  
其实是问有多少种摆法。

# 解题思路 #

解题时需要对每一行进行遍历。  
接下来以例子来说明。  
首先遍历第一行，按照**任意两个皇后都不能处于同一行、同一列或同一斜线上的规则**找到可以放下的点，此时找到第一列，放下棋子。  
![示例1][1]  
此时递归调用函数：

EightQueen(row + 1, chess2)

再次遍历第二行，按照规则找到可以放下的点，此时找到第三列，放下棋子。  
![示例2][2]  
再次遍历第三行，按照规则找到可以放下的点，此时找到第五列，放下棋子。  
![示例3][3]  
再次遍历第四行，按照规则找到可以放下的点，此时找到第七列，放下棋子。  
![示例4][4]  
以此类推，继续遍历，直至第一行的八列全都成功遍历。该部分的核心代码为：

for (j = 0; j < 8; j++){
        	//遍历每一行的八列
    	if (noDanger(row, j, chess2))	//判断是否有危险，没有危险则进行下一步
    	{
        
    		for (i = 0; i < 8; i++)		//清除当前行，上一次循环留下的影响，如j=0对j=1的影响。
    			chess2[row][i] = 0;		
    		chess2[row][j] = 1;				//该位置安全，放下一个皇后
    		EightQueen(row + 1, chess2);	//查询下一行情况
    	}
    }

如果有一次成功遍历完成八行，则代表每一行都放下了一个皇后，此时便解决了八皇后问题。  
我们利用函数：

if (8 == row){
        					//如果到达row = 8 则代表第八行的棋盘都已经放上皇后，则所有行都放上了皇后。打印棋盘出来
    	printf("第%d种：\n", ++count);
    	for (i = 0; i < 8; i++){
        
    		for (j = 0; j < 8; j++){
        
    			printf("%d ", chess2[i][j]);
    		}
    		printf("\n");
    	}
    	printf("\n");
    }

将棋盘打印下来。

# 实现代码 #

#include<stdio.h>
    
    int count = 0;
    
    int noDanger(int row, int col, int (*chess)[8]){
        
    	int i,j,flag1 = 0,flag2 = 0,flag3 = 0,flag4 = 0,flag5=0;
    	for (i = 0; i < 8; i++){
        			//判断该列是否有其它皇后
    		if (chess[i][col] != 0){
        	
    			flag1 = 1;
    			break;
    		}
    	}
    	for (i = row, j = col; i >= 0 && j >= 0; i--,j--){
        		//判断左上角是否有其它皇后
    		if (chess[i][j] != 0){
        
    			flag2 = 1;
    			break;
    		}
    	}
    	for (i = row, j = col; i < 8 && j < 8; i++, j++){
        		//判断右下角是否有其它皇后
    		if (chess[i][j] != 0){
        
    			flag3 = 1;
    			break;
    		}
    	}
    	for (i = row, j = col; i >= 0 && j < 8; i--, j++){
        		//判断左下角是否有其它皇后
    		if (chess[i][j] != 0){
        
    			flag4 = 1;
    			break;
    		}
    	}	
    	for (i = row, j = col; i < 8 && j >= 0; i++, j--){
        		//判断右上角是否有其它皇后
    		if (chess[i][j] != 0){
        
    			flag5 = 1;
    			break;
    		}
    	}
    	if (flag1 || flag2 || flag3 || flag4 || flag5){
        			//如果有其它皇后则不满足条件。return 0；
    		return 0;
    	}
    	else{
        
    		return 1;
    	}
    }
    
    void EightQueen(int row,int chess[][8]){
        
    	int chess2[8][8],i,j;
    	for (i = 0; i < 8; i++){
        		//将所有chess赋予局部棋盘chess2，这样可以不改变原chess的值
    		for (j = 0; j < 8; j++){
        
    			chess2[i][j] = chess[i][j];
    		}
    	}
    	if (8 == row){
        					//如果到达row = 8 则代表第八行的棋盘都已经放上皇后，则所有行都放上了皇后。打印棋盘出来
    		printf("第%d种：\n", ++count);
    		for (i = 0; i < 8; i++){
        
    			for (j = 0; j < 8; j++){
        
    				
    				printf("%d ", chess2[i][j]);
    			}
    			printf("\n");
    		}
    		printf("\n");
    	}
    	else{
        
    		for (j = 0; j < 8; j++){
        
    			if (noDanger(row, j, chess2))	//判断是否有危险，没有危险则进行下一步
    			{
        
    				for (i = 0; i < 8; i++)		//清除当前行，上一次循环留下的影响，如j=0对j=1的影响。
    					chess2[row][i] = 0;		
    				chess2[row][j] = 1;				//该位置安全，放下一个皇后
    				EightQueen(row + 1, chess2);	//查询下一行情况
    			}
    		}
    	}
    
    }
    
    void main(){
        
    	int chess[8][8], i, j;
    	for (i = 0; i < 8; i++){
        
    		for (j = 0; j < 8; j++){
        
    			chess[i][j] = 0;				//赋予棋盘初值，全是0；
    		}
    	}
    	EightQueen(0,chess);
    }

# GITHUB下载连接 #

[https://github.com/bubbliiiing/Data-Structure-and-Algorithm][https_github.com_bubbliiiing_Data-Structure-and-Algorithm]

希望得到朋友们的喜欢。  
有问题的朋友可以提问噢。

[20190723145057699.jpg_pic_center]: /images/20211122/79aecdf4a0c246faaa8768a9508aeaf2.png
[20190725100017339.png_pic_center]: /images/20211122/313929dfc47048b5997a98acea394cc2.png
[1]: /images/20211122/11a0962612a545048cf42fd05e481b7b.png
[2]: /images/20211122/091df5c7357f493a9c0ada89829be1a9.png
[3]: /images/20211122/3748af02d89b474f8bd292fe6a356956.png
[4]: /images/20211122/0170c11cdd744c02b1bdba1fd3ed4ac2.png
[https_github.com_bubbliiiing_Data-Structure-and-Algorithm]: https://github.com/bubbliiiing/Data-Structure-and-Algorithm