全排列的應(yīng)用：正方體的組成與八皇后
前言
給定一個含有8個數(shù)字的數(shù)組，判斷有沒有可能把這8個數(shù)字分別放到正方體的8個頂點(diǎn)上，使得正方體上三組相對面上的4個頂點(diǎn)的和都相等。
本文就跟大家分享下這個問題的解決方案，歡迎各位感興趣的開發(fā)者閱讀本文。
正方體的組成
初次看到這個問題，很多開發(fā)者可能會比較蒙，一時間無法找到切入點(diǎn)。那我們就先畫個正方體出來，給每個頂點(diǎn)標(biāo)記a1, a2 ,a3 ,...., a8。如下圖所示：
iShot_2023-06-26_07.36.45
實(shí)現(xiàn)思路
有了圖之后，我們在做進(jìn)一步的分析，這個正方體有6個面，3組相對的面（上下、前后、左右）：
- a1, a2, a4, a3 | a5, a6, a8, a7
- a1, a5, a6, a2 | a3, a4, a8, a7
- a1, a3, a7, a5 | a2, a4, a8, a6
有了這些條件后，再次結(jié)合題意，我們可知：只需要將8個數(shù)字分別放入正方體的8個頂點(diǎn)中，判斷三組相對面的頂點(diǎn)和是否都相等，這個問題就解決了。
8個數(shù)字分別放到8個頂點(diǎn)上，所有數(shù)字都有可能放入任意一個頂點(diǎn)。換言之就是求這8個數(shù)字的所有排列，我的另一篇文章實(shí)現(xiàn)字符串的排列算法詳細(xì)講解了這個算法的實(shí)現(xiàn)思路，此處不過多贅述。
分析到這里，我們就得出了一個完整的實(shí)現(xiàn)思路：
- 求出給定數(shù)組中8個數(shù)字的所有排列
- 遍歷所有排列，將每個排列中的元素映射到變量中(a1, a2, ..., a8)
- 判斷8個點(diǎn)組成的三組相對面的頂點(diǎn)和是否相等
實(shí)現(xiàn)代碼
分析出思路后，我們就可以將上述思路轉(zhuǎn)換成代碼了，如下所示：
/**
* 能否構(gòu)成正方體
* @param nums
*/
public isCubePossible(nums: Array<number>): boolean {
if (nums.length !== 8) {
return false;
}
// 獲取8個點(diǎn)的所有排列
const list = this.permute(nums.join(""));
for (let i = 0; i < list.length; i++) {
// 將當(dāng)前組合中的點(diǎn)轉(zhuǎn)為number類型放入item
const item: Array<number> = [];
for (let j = 0; j < list[i].length; j++) {
item.push(+list[i][j]);
}
// 從當(dāng)前組合中獲取正方體的8個點(diǎn)
const [a1, a2, a3, a4, a5, a6, a7, a8] = item;
// 判斷正方體三組相對面上的點(diǎn)相加是否相等
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方法的具體實(shí)現(xiàn)，對此感興趣的開發(fā)者請移步：ArrayOfStrings.ts
八皇后問題
在一個8*8的棋盤上放置八個皇后，使得它們彼此之間不會互相攻擊（即不在同一行、同一列或同一對角線上），總共有多少種擺法？如下圖所示列舉了其中一種擺法：
iShot_2023-06-26_11.40.41
實(shí)現(xiàn)思路
分析題目后 ，我們知道了兩個皇后不能處在同一行，那么肯定是每個皇后獨(dú)占一行。那我們就先把皇后定義出來，用一個數(shù)組來表示皇后在棋盤上的列號，分別用0～7（棋盤上有8個皇后）對這個數(shù)組進(jìn)行初始化。
棋盤上每一行所放置的皇后，它都可以放在這一行的任意位置。很顯然，這也需要用到全排列求出它的所有放置組合。因?yàn)槲覀冇玫牟煌瑪?shù)字對數(shù)組進(jìn)行的初始化，所以任意兩個皇后肯定不同列。
因此，我們只需要判斷每一組排列對應(yīng)的8個皇后是不是在同一條對角線上，即：對于數(shù)組的兩個下標(biāo)i和j，是否有i-j === queens[i] - queens[j] || j-i === queens[j] - queens[i]，這個問題就得到了解決。
我們來寫一下實(shí)現(xiàn)思路：
- 定義皇后數(shù)組，分別用0～7對這個數(shù)組進(jìn)行初始化
- 求出這個數(shù)組的所有排列
- 遍歷所有排列，判斷每一個排列是否滿足不在同一對角線的條件
- 遍歷滿足條件的排列，對棋盤進(jìn)行填充（將皇后放置在棋盤上）
實(shí)現(xiàn)代碼
我們將上述思路轉(zhuǎn)換為代碼，如下所示：
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類型的，這里需要將其轉(zhuǎn)為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;
}
/**
* 判斷當(dāng)前組合是否滿足排列要求（不在對角線上）
* @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;
}測試用例
我們用一個例子來校驗(yàn)下上述代碼能否正常執(zhí)行。
const arrayOfStrings = new ArrayOfStrings();
console.log(
"能否構(gòu)成正方體",
arrayOfStrings.isCubePossible([1, 2, 3, 4, 5, 6, 7, 8])
);
console.log("八皇后問題有", arrayOfStrings.eightQueens().length, "種擺法");
示例代碼
本文用到的代碼完整版請移步：
- ArrayOfStrings.ts
- ArrayOfStrings-test.ts
