八皇后

左手的ㄟ右手 2022-10-01 11:44 160阅读 0赞

# 八皇后 #

## 求解思路 ##

*  可以将八皇后看成全排列问题，因为每次都是在某一行选择某个位置，所以不需要考虑行的问题。每次只需要求出当前行的棋子所在列。所以可以化为全排列问题。
 *  从书上看到的方法：对排列问题进行递归，每次排一行的棋子。并且对已经排的列用flag数组记录，并在递归语句执行完跳出后将它还原（用于对所有结果穷举）。期间设置一个index变量和结果储存数组对求得的结果记录。当index==皇后总数时对结果进行判断，满足条件的输出。
 *  也可以用回溯法进行改进。每次求得下一步要放置的位置都对判断合法性。要是不满足就返回到上一个状态并往下继续进行。
 *  老师上课讲的方法：不用到递归，设置一个数组a记录各个行当前列。循环时，要是当前列未放置，且将棋子放在这个位置处于安全的状态，就跳出子循环，否则当前列数x\[*k*\]++。若x\[*k*\]>=行数也跳出子循环。所以有两种情况是跳出子循环的。
    
     *  a\[*k*\]是超过行数的原因，则将k--,且a\[*k*\]++(这里的k是自减之后的)。
     *  当前棋子处于安全阶段，若k==n(排满棋子)则找到一个序列，否则就将k++,并让a\[k\]=0(k是加一之后的k，让a\[k\]等于0是为了消除之前数据回溯带来的影响)
 *  判断是否安全的方法-->先判断是不是在同一列（行数必不相同），然后判断两点的（行-行）的绝对值是否等于（列-列）的绝对值，若是不想等，则说明两点既不在同一列又不在对角线上。

## 代码 ##

#include<stdio.h>
    #include<math.h>
    #include<stdlib.h>
    int a[100];
    int flag[100];
    int count = 0;
    int isSafe(int k)
    {
    	for (int i = 0; i < k; i++)
    	{//判断是否满足题目要求
    		if (a[i] == a[k] || abs(i - k) == abs(a[i] - a[k]))
    			return 0;
    	}
    	return 1;
    }
    void print(int n)
    {//输出满足要求的方案
    	for (int i = 0; i < n; i++)
    		printf("%d ",a[i]);
    	putchar(10);
    }
    int main()
    {
    	int n;
    	int k = 0;
    	scanf("%d",&n);//输入棋子个数
    	while(a[0]<n)
    	{
    		while (!isSafe(k) && a[k] < n)
    			a[k]++;     //找出满足条件的位置
    		if (a[k] == n)
    		{
    			k--;       //本层未找到合适的位置，回溯
    			a[k]++;    //上一层向下进行
    		}
    		else
    		{
    
    			if (k == n - 1)
    			{
    			//找到满足条件的
    				count++;
    				print(n);
    				a[k]++;   //继续向下一层寻找
    			}
    			else
    			{
    				k++;
    				a[k] = 0;  //消除之前回溯留下的影响
    			}
    		}
    	}
    	printf("\n%d\n",count);
    	system("pause");
    	return 0;
    }
    
    
    复制代码

转载于:https://juejin.im/post/5cc2c6a3518825251165e370