给定一个含有 8 个数字的数组，判断有没有可能把这 8 个数字分别放到正方体的 8 个顶点上，使得正方体上三组相对面上的 4 个顶点的和都相等。
本文就跟大家分享下这个问题的解决方案，欢迎各位感兴趣的开发者阅读本文。
初次看到这个问题，很多开发者可能会比较蒙，一时间无法找到切入点。那我们就先画个正方体出来，给每个顶点标记 a1, a2 ,a3 ,...., a8 。如下图所示：
有了图之后，我们在做进一步的分析，这个正方体有 6 个面，3 组相对的面（上下、前后、左右）：
有了这些条件后，再次结合题意，我们可知：只需要将 8 个数字分别放入正方体的 8 个顶点中，判断三组相对面的顶点和是否都相等，这个问题就解决了。
8 个数字分别放到 8 个顶点上，所有数字都有可能放入任意一个顶点。换言之就是求这 8 个数字的所有排列，我的另一篇文章实现字符串的排列算法详细讲解了这个算法的实现思路，此处不过多赘述。
分析到这里，我们就得出了一个完整的实现思路：
分析出思路后，我们就可以将上述思路转换成代码了，如下所示：
/**
* 能否构成正方体
* @param nums
*/
public isCubePossible(nums: Array<number>): boolean {
if (nums.length !== 8) {
return false;
}
// 获取 8 个点的所有排列
const list = this.permute(nums.join(""));
for (let i = 0; i < list.length; i++) {
// 将当前组合中的点转为 number 类型放入 item
const item: Array<number> = [];
for (let j = 0; j < list[i].length; j++) {
item.push(+list[i][j]);
}
// 从当前组合中获取正方体的 8 个点
const [a1, a2, a3, a4, a5, a6, a7, a8] = item;
// 判断正方体三组相对面上的点相加是否相等
if (
a1 + a2 + a4 + a3 === a5 + a6 + a8 + a7 &&
a1 + a5 + a6 + a2 === a3 + a4 + a8 + a7 &&
a1 + a3 + a7 + a5 === a2 + a4 + a8 + a6
) {
return true;
}
}
return false;
}
上述代码中没有列举
permute方法的具体实现，对此感兴趣的开发者请移步：ArrayOfStrings.ts
在一个 8*8 的棋盘上放置八个皇后，使得它们彼此之间不会互相攻击（即不在同一行、同一列或同一对角线上），总共有多少种摆法？如下图所示列举了其中一种摆法：
分析题目后 ，我们知道了两个皇后不能处在同一行，那么肯定是每个皇后独占一行。那我们就先把皇后定义出来，用一个数组来表示皇后在棋盘上的列号，分别用 0 ～ 7 （棋盘上有 8 个皇后）对这个数组进行初始化。
棋盘上每一行所放置的皇后，它都可以放在这一行的任意位置。很显然，这也需要用到全排列求出它的所有放置组合。因为我们用的不同数字对数组进行的初始化，所以任意两个皇后肯定不同列。
因此，我们只需要判断每一组排列对应的 8 个皇后是不是在同一条对角线上，即：对于数组的两个下标 i 和 j ，是否有i-j === queens[i] - queens[j] || j-i === queens[j] - queens[i]，这个问题就得到了解决。
我们来写一下实现思路：
我们将上述思路转换为代码，如下所示：
public eightQueens(): Array<Array<Array<number>>> {
const queens = [0, 1, 2, 3, 4, 5, 6, 7];
const solutions: Array<Array<Array<number>>> = [];
// 获取所有组合
const list = this.permute(queens.join(""));
for (let i = 0; i < list.length; i++) {
// 求出的组合中元素值为 string 类型的，这里需要将其转为 number 类型
const item: Array<number> = [];
for (let j = 0; j < list[i].length; j++) {
item.push(+list[i][j]);
}
// 不在对角线上
if (this.isValidPlacement(item)) {
const solution: Array<Array<number>> = [];
// 遍历此组合，取出皇后的摆放位置
for (let j = 0; j < item.length; j++) {
const col = item[j];
const row: Array<number> = Array(8).fill(0);
row[col] = 1;
solution.push(row);
}
solutions.push(solution);
}
}
return solutions;
}
/**
* 判断当前组合是否满足排列要求（不在对角线上）
* @param queens
* @private
*/
private isValidPlacement(queens: Array<number>) {
for (let i = 0; i < queens.length; i++) {
for (let j = i + 1; j < queens.length; j++) {
if (Math.abs(queens[i] - queens[j]) === Math.abs(i - j)) {
// 在对角线上
return false;
}
}
}
return true;
}
我们用一个例子来校验下上述代码能否正常执行。
const arrayOfStrings = new ArrayOfStrings();
console.log(
"能否构成正方体",
arrayOfStrings.isCubePossible([1, 2, 3, 4, 5, 6, 7, 8])
);
console.log("八皇后问题有", arrayOfStrings.eightQueens().length, "种摆法");
本文用到的代码完整版请移步：
至此，文章就分享完毕了。
我是神奇的程序员，一位前端开发工程师。
如果你对我感兴趣，请移步我的个人网站，进一步了解。
这是一个专为移动设备优化的页面（即为了让你能够在 Google 搜索结果里秒开这个页面），如果你希望参与 V2EX 社区的讨论，你可以继续到 V2EX 上打开本讨论主题的完整版本。
V2EX 是创意工作者们的社区，是一个分享自己正在做的有趣事物、交流想法，可以遇见新朋友甚至新机会的地方。
V2EX is a community of developers, designers and creative people.