递归算法计算八皇后问题（Eight Queen Problem with Recursive Algorithm）

小灰灰 2022-06-15 01:40 148阅读 0赞

## 1.概念 ##

八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。

![Center][]

## 2.实现 ##

#include <stdio.h>
    
    int count = 0;
    int notDanger(int row, int j, int(*chess)[8]);    //判断当前点是否 不在危险位置 
    void EightQueen(int row, int n, int(*chess)[8]);  //递归计算所有皇后位置
    int main()
    {
    	int chess[8][8], i, j;
    	//初始化为全0
    	for (i = 0; i < 8; i++)
    	{
    		for (j = 0; j < 8; j++)
    		{
    			chess[i][j] = 0;
    		}
    	}
    	EightQueen(0, 8, chess);
    	printf("总共有 %d 种解决方法！\n",count);  //每一种可能分割线
    	return 0;
    }
    
    int notDanger(int row, int j, int(*chess)[8])
    {
    	int i, k;
    	int flag1 = 0, flag2 = 0, flag3 = 0, flag4 = 0, flag5 = 0; //是否 有皇后
    
            //判断列（正上正下）方向
    	for (i = 0; i < 8; i++)
    	{
    		if (*(*(chess + i) + j) != 0)
    		{
    			flag1 = 1;
    			break;
    		}
    	}
    	//判断左上方
    	for (i = row, k = j; i >= 0 && k >= 0; i--, k--)
    	{
    		if (*(*(chess + i) + k) != 0)
    		{
    			flag2 = 1;
    			break;
    		}
    	}
    	//判断左下方
    	for (i = row, k = j; i < 8 && k >= 0; i++, k--)
    	{
    		if (*(*(chess + i) + k) != 0)
    		{
    			flag3 = 1;
    			break;
    		}
    	}
    	//判断右上方
    	for (i = row, k = j; i >= 0 && k < 8; i--, k++)
    	{
    		if (*(*(chess + i) + k) != 0)
    		{
    			flag4 = 1;
    			break;
    		}
    	}
    	//判断右下方
    	for (i = row, k = j; i < 8 && k < 8; i++, k++)
    	{
    		if (*(*(chess + i) + k) != 0)
    		{
    			flag5 = 1;
    			break;
    		}
    	}
    
    	//若有一个方向有皇后，就是危险的，返回0,否则安全返回1
    	if (flag1 || flag2 || flag3 || flag4 || flag5)
    	{
    		return 0;
    	}
    	else
    	{
    		return 1;
    	}
    }
    //参数row:起始行
    //参数n:列数
    //参数(*chess)[8]：表示指向棋盘每一行的指针
    void EightQueen(int row, int n, int(*chess)[8])
    {
    	int chess2[8][8]; //存放待输出棋盘格
    	int i, j;
    	for (i = 0; i < 8; i++)
    	{
    		for (j = 0; j < 8; j++)
    		{
    			chess2[i][j] = chess[i][j];
    		}
    	}
    
    	//终止条件
    	if (8 == row)
    	{
    		printf("第 %d 种：\n", count + 1);  
    										
    		for (i = 0; i < 8; i++) //行
    		{
    			for (j = 0; j < 8; j++) //列
    			{
    				printf("%d ", *(*(chess2 + i) + j)); //输出第i行第j列元素
    			}
    			printf("\n");
    		}
    		count++;
    		printf("——————————————\n");  //每一种可能分割线
    	}
    	else
    	{
    		for (j = 0; j < n; j++) //从上到下逐列选择皇后位置
    		{
    			if (notDanger(row, j, chess)) //判断是否 不在危险位置（不在对应点直线斜线上）
    			{
    				for (i = 0; i < 8; i++) //每row行中8个元素均初始化为0
    				{
    					*(*(chess2 + row) + i) = 0;
    				}
    				*(*(chess2 + row) + j) = 1; //row行 notDanger列j 确定为皇后位置******
    
    				EightQueen(row + 1, n, chess2); //递归计算下一行
    			}
    		}
    	}
    }

## 3.结果 ##

........

![Center 1][]

[Center]: /images/20220615/f3dcbdaa1e3044beb5640877abce015c.png
[Center 1]: /images/20220615/dcf575d399614c01ae5cebc34eff40aa.png