全排列的應用：正方體的組成與八皇后
前言
給定一個含有8個數字的數組，判斷有沒有可能把這8個數字分別放到正方體的8個頂點上，使得正方體上三組相對面上的4個頂點的和都相等。
本文就跟大家分享下這個問題的解決方案，歡迎各位感興趣的開發者閱讀本文。
正方體的組成
初次看到這個問題，很多開發者可能會比較蒙，一時間無法找到切入點。那我們就先畫個正方體出來，給每個頂點標記a1, a2 ,a3 ,...., a8。如下圖所示：
iShot_2023-06-26_07.36.45
實現思路
有了圖之后，我們在做進一步的分析，這個正方體有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
有了這些條件后，再次結合題意，我們可知：只需要將8個數字分別放入正方體的8個頂點中，判斷三組相對面的頂點和是否都相等，這個問題就解決了。
8個數字分別放到8個頂點上，所有數字都有可能放入任意一個頂點。換言之就是求這8個數字的所有排列，我的另一篇文章實現字符串的排列算法詳細講解了這個算法的實現思路，此處不過多贅述。
分析到這里，我們就得出了一個完整的實現思路：
- 求出給定數組中8個數字的所有排列
- 遍歷所有排列，將每個排列中的元素映射到變量中(a1, a2, ..., a8)
- 判斷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的棋盤上放置八個皇后，使得它們彼此之間不會互相攻擊（即不在同一行、同一列或同一對角線上），總共有多少種擺法？如下圖所示列舉了其中一種擺法：
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]，這個問題就得到了解決。
我們來寫一下實現思路：
- 定義皇后數組，分別用0～7對這個數組進行初始化
- 求出這個數組的所有排列
- 遍歷所有排列，判斷每一個排列是否滿足不在同一對角線的條件
- 遍歷滿足條件的排列，對棋盤進行填充（將皇后放置在棋盤上）
實現代碼
我們將上述思路轉換為代碼，如下所示：
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, "種擺法");
示例代碼
本文用到的代碼完整版請移步：
- ArrayOfStrings.ts
- ArrayOfStrings-test.ts
