N皇后c语言实现方法

N皇后问题是经典的回溯问题，在N×N格的棋盘上放置N个皇后,要求每个皇后不能够互相攻击，即每个皇后所在行所在列，还有对角线上不能够有第二个皇后(这不就是一山不容二虎，除非...一公一母?)。

N皇后适用回溯法进行解答。

在讲解N皇后前，我们先来简单的说明一下何为回溯法：

回溯法就是试探性走路，当你在走迷宫时，面临分岔路口（假设每条路上都是没有分叉口），左右摇摆不定，不知如何去走，那么你肯定会选择其中一条路走下去，走不通，怎么办？就只能苦逼的回来再走另一条路，回溯法就是重复这个过程，将所有的解都解出来位置。

（好像一点都不简洁...）

看一下回溯法的基本模板：

void  backtracking(参数){

         if(终止条件）{

            收集结果

             return  ；}

          for(循环：一般都是集合元素（你需要进行循环）){

               进行你需要的 *** 作

               递归函数

               撤销上一步 *** 作 ；}

          return ;

}

如果你有些不懂以上的模块，就点击超链接 ，移步到哔哩哔哩，让卡尔老师带你理解回溯法。

在你理解了回溯法之后，你应该就知道回溯法的适用范围了（组合，排列，切割，棋盘...不理解也没事，这不标出来了）

现在，已经有了工具的你，要开始思考了，如何解题了。

若是思考出来了，就可以return了，如果不理解，就请客官听听这种思路：

N皇后的规则：每个皇后所在行所在列，还有对角线上不能够有第二个皇后。

不能在同行？不能在同列？不能在它对角线上？（判断放置位置？）

怎么办？这样办，我们从两个兜中抽出两个你想要多长多长的一维数组（开玩笑，适度长就可以了），再加个变量,用来标记

eg: row[10] , line[10] ，temp=0(这位可是老熟人了，想必你已经在其它地方与它不期而遇好多次了)。

每放一个N皇后，我们就将它的位置行和列分别记录在两个数组，聪明的你一定知道，前者存行，后者存列，然后呢？就将temp++，就可以将下一个能放皇后坐标的地方找出来，再存放两个数组里。

你想一想，这有什么用呢？

存的有行有列了，是不是就可以碰到他们就绕开了？这是不是就可以保证在不同行，不同列了？

是不是有了皇后的坐标了？那就好避免在它的对角线了，众所周知，对角线上的数，其位置与中心位置的行之差的绝对值是等于列之差的绝对值的， |行之差| == |列之差|

怎么选择下一个位置，就要提到绕不开的结 for(;;)老哥了，聪明的你必然想到了，这就对应到回溯法的模板的内容了，你进行遍历部分位置，然后进行判定是否可以放置，判定方法你已经知晓了。

各个部分基本上已经解决了，就剩下理一遍思路：

1.先用个for开始第一行的遍历（也只需要第一行，你品一品就明白了）

2.利用for进行下一个位置的寻找，找到进行记录坐标，没有找到，就继续

3.重复2的 *** 作

4.如果到头或者找到一种解，就进行返回上一步，进行下一步撤销 *** 作继续寻找。

5.程序结束

以下就是c语言代码实现：

#include"stdio.h"
#include"math.h"
int row[10],line[10];  //用来记录皇后放置的位置
int temp=0,solve=0;    //用来记录放置几个皇后，有多少个解
int n;

int  judge(int i,int j)    //判断是否能够放下皇后，不是你心里的那位
{
   int k; 
   for(k=0;k

欢迎分享，转载请注明来源：内存溢出

原文地址: https://outofmemory.cn/langs/674838.html