前言

各位和我一样的刚学完递归的小白们，是不是突然遇见了一个大BOSS，八皇后👸🏻问题！！把自信的说着“老子递归学好了！”的你一棒子打回了出生点，就像你刚玩只狼遇到的那个大胖子，刚玩原神遇到的雪山。今天，我就和大家一起学习一下这个著名的八皇后👸🏻问题。

题目介绍

八皇后问题，是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法并输出每一种摆法。

升华：我在做这个东西的时候本来想用人脑将他们摆进去，发现太！麻！烦！可能这就是计算机存在的意义吧！

—————————————————————————————————————————

引入：

不知道大家有没有在前面学习递推的时候学过马拦过河卒的问题没看过的可以点这，这个问题和那个问题都是一个棋类的问题，他们也有相同之处，都是需要用一个数组来表示这个地方有没有被占领，象棋的那个题是马占领的地方需要标记，而这个题是皇后占领的每一行每一列每一个对角线都需要标记。所以我们可以采用一些个数组来表示这个地方被皇后占领了。当然这个题还用到了一个重要的算法就是递归算法和回溯的思想。

—————————————————————————————————————————

解决思路：

1.首先定义三个数组分别表示列被占领，左对角线被占领，和右对角线被占领。因为我们一行一行的放进去所以不用考虑行的问题。👸🏻

2.利用递归算法在没有被占领的地方一行一行的放入我们的皇后。👸🏻

3.利用递归和回溯算法一行一行的放入皇后。👸🏻

__________________________________________________________________________

                                    理论存在，实践开始！

难点1：如何表示对角线被占领？

用数组来表示列被占领很简单，只要让皇后所在的那一列的数组的值都等于0，就可以解决这个问题，但如何用数组来表达对角线呢？？你知道吧！你数一数，这一共有多少个对角线？一共有15条对角线，所以我们可以定义两个数组d1和d2来用来表示两个方向的对角线。如果被占领就是1没有被占领就是0

绿色的就是右对角线，col【】；

紫色的就是左对角线，umcol【】；

如何在摆放的时候来确定哪一行哪一列呢？

这样定义十五行太好定义了但是想要表示就难了，我们来研究一下这个东西。

看下图，如这个第五列第三行的这个女皇，这个皇后占领了这两个对角线， 如何来表示上对角线（皇后👸🏻的左上和右下从右上脚开始1、2、3、4、5...）

通过这两个公式就能得到当前皇后所在的两条斜线是否有其他的皇后

col[u-i+n]=?;uncol[u+i]=?

至于为什么可以这样算出来呢，看下图就知道了：

uncol【u+i】//行加列，算出左对角线是否皇后：

 这样我们不就可以用行标和列标来表示他所在的左对角线了嘛，神器吧！！

希望各位xdm都把这个背过说实话我要是自己推我也推不出来这个玩意！！

右对角线：用行-列+n就会神奇的发现变成了下面这个样子：

col【u-i+n】：

版权声明：本文为CSDN博主「孤独时代的c0re」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。

原文链接：https://blog.csdn.net/m0_63830846/article/details/123927967