全排列的应用：正方体的组成与八皇后

给定一个含有8个数字的数组，判断有没有可能把这8个数字分别放到正方体的8个顶点上，使得正方体上三组相对面上的4个顶点的和都相等。,本文就跟大家分享下这个问题的解决方案，欢迎各位感兴趣的开发者阅读本文。,初次看到这个问题，很多开发者可能会比较蒙，一时间无法找到切入点。那我们就先画个正方体出来，给每个顶点标记a1, a2 ,a3 ,…., a8。如下图所示：,,iShot_2023-06-26_07.36.45,有了图之后，我们在做进一步的分析，这个正方体有6个面，3组相对的面（上下、前后、左右）：,有了这些条件后，再次结合题意，我们可知：只需要将8个数字分别放入正方体的8个顶点中，判断三组相对面的顶点和是否都相等，这个问题就解决了。,8个数字分别放到8个顶点上，所有数字都有可能放入任意一个顶点。换言之就是求这8个数字的所有排列，我的另一篇文章实现字符串的排列算法详细讲解了这个算法的实现思路，此处不过多赘述。,分析到这里，我们就得出了一个完整的实现思路：,分析出思路后，我们就可以将上述思路转换成代码了，如下所示：,在一个8*8的棋盘上放置八个皇后，使得它们彼此之间不会互相攻击（即不在同一行、同一列或同一对角线上），总共有多少种摆法？如下图所示列举了其中一种摆法：,,iShot_2023-06-26_11.40.41,分析题目后 ，我们知道了两个皇后不能处在同一行，那么肯定是每个皇后独占一行。那我们就先把皇后定义出来，用一个数组来表示皇后在棋盘上的列号，分别用0～7（棋盘上有8个皇后）对这个数组进行初始化。,棋盘上每一行所放置的皇后，它都可以放在这一行的任意位置。很显然，这也需要用到全排列求出它的所有放置组合。因为我们用的不同数字对数组进行的初始化，所以任意两个皇后肯定不同列。,因此，我们只需要判断每一组排列对应的8个皇后是不是在同一条对角线上，即：对于数组的两个下标i和j，是否有i-j === queens[i] – queens[j] || j-i === queens[j] – queens[i]，这个问题就得到了解决。,我们来写一下实现思路：,我们将上述思路转换为代码，如下所示：,我们用一个例子来校验下上述代码能否正常执行。,,,本文用到的代码完整版请移步：