八皇后问题回溯法（八皇后问题）

大家好，我是小夏，我来为大家解答以上问题。八皇后问题回溯法，八皇后问题很多人还不知道，现在让我们一起来看看吧！

1、先声明我们根据条件可以知道皇后肯定是每行都有且只有一个所以我们创建一个数组x[t]让数组角标表示八皇后的行，用这个角标对应的数组值来确定这个皇后在这行的那一列。

2、我们用递归来做：

3、这问题要求皇后所在的位置必须和其他皇后的位置不在同一行、列还有 把两个皇后看成点其|斜率|=1

4、所以我们就要写这个限定条件用一个函数来实现：函数内对没一个已经放好的皇后的位置进行判断，所以就要有个循环。

5、我们既然是用递归来解决问题那就要把这个问题分成一个个相同的小问题来实现对吧！

6、这小问题是什么呢，不难发现我们要在8*8的方格里放好8个皇后那我们就要知道在8（列）*7（行）是怎么放的在有我们事先写好的判断函数放好最后行就搞定了；以此类推我们要知道8*7的怎么方的我们就要知道8*6是怎么样的就好了。。。。。。

7、所以我们是以一行怎么放作为一个单元

8、那好我们就去建一个可以放好一行的函数backtrack（int t）里面的t表示是第几行，在main函数调用的时候第一次传进来的是0也就是从第一行开始判断。

9、我们就开始写函数体了：

10、       没一行有8个位置可以放每一个位置我们都要去判断一下所以我们就用循环来搞定。

11、       在这个循环里面我们让x[t]=i也就是从这一行的第一个开始判断。放好后就要去判断

12、       是否符合条件。如果符合条件我们就在调用这个函数本身backtrack不过穿进去的参数

13、       是t+1也就是下一行的意思。

14、在进行判断下一行之前我们要判断一下t是不是等于8也就是已经是最后一行了，如果是最后一行了我们就可以将其进行输出。打印8*8的矩阵（提示在写一个函数）皇后的位置用1表示出来没有的用0表示。

15、这是我自己的体会 ;  里面可能有写表述不当的地方要是不懂可以来问我！（第一次回答这么长的问题）

本文到此讲解完毕了，希望对大家有帮助。