謎題:將 1~9 這九個不重複的整數填入 3×3 的表格,使得每一列、每一行以及兩條對角線上的數字之和都相同。
策略:窮舉搜尋——列出所有整數排列方案,再逐一過濾。亮點在於遞歸函式 getPermutation 的設計;文末另外提供幾種非遞歸的全排列演算法。
// 遞歸版全排列:直觀但資源消耗大
function getPermutation(arr) {
if (arr.length == 1) { return [arr]; }
var permutation = [];
for (var i = 0; i < arr.length; i++) {
var firstEle = arr[i]; // 取出第一個元素
var arrClone = arr.slice(0); // 複製陣列
arrClone.splice(i, 1); // 移除該元素,縮小規模
var childPermutation = getPermutation(arrClone); // 遞歸
for (var j = 0; j < childPermutation.length; j++) {
childPermutation[j].unshift(firstEle); // 把取出的元素插回去
}
permutation = permutation.concat(childPermutation);
}
return permutation;
}
// 驗證是否為幻方
function validateCandidate(candidate) {
var sum = candidate[0] + candidate[1] + candidate[2];
for (var i = 0; i < 3; i++) {
if (!(sumOfLine(candidate, i) == sum && sumOfColumn(candidate, i) == sum)) {
return false;
}
}
return sumOfDiagonal(candidate, true) == sum && sumOfDiagonal(candidate, false) == sum;
}
function sumOfLine(candidate, line) {
return candidate[line * 3] + candidate[line * 3 + 1] + candidate[line * 3 + 2];
}
function sumOfColumn(candidate, col) {
return candidate[col] + candidate[col + 3] + candidate[col + 6];
}
function sumOfDiagonal(candidate, isForwardSlash) {
return isForwardSlash ? candidate[2] + candidate[4] + candidate[6]
: candidate[0] + candidate[4] + candidate[8];
}
var permutation = getPermutation([1,2,3,4,5,6,7,8,9]);
var candidate;
for (var i = 0; i < permutation.length; i++) {
candidate = permutation[i];
if (validateCandidate(candidate)) { break; } else { candidate = null; }
}
console.log(candidate ? candidate : 'No valid result found');
/* 演算法示例(以 4 個元素 ["a","b","c","d"] 為例,共循環 4! = 24 次):
* 假設 index = 13,因為共 4 個元素,故迭代 4 次:
* 第 1 次:13 / 1,商 13,餘 0 → 第 1 個元素插入位置 0,得 ["a"]
* 第 2 次:13 / 2,商 6,餘 1 → 第 2 個元素插入位置 1,得 ["a","b"]
* 第 3 次:6 / 3,商 2,餘 0 → 第 3 個元素插入位置 0,得 ["c","a","b"]
* 第 4 次:2 / 4,商 0,餘 2 → 第 4 個元素插入位置 2,得 ["c","a","d","b"]
*/
function perm(arr) {
var result = new Array(arr.length);
var fac = 1;
for (var i = 2; i <= arr.length; i++) fac *= i; // 排列總數
for (var index = 0; index < fac; index++) { // 每個 index 對應一個排列
var t = index;
for (i = 1; i <= arr.length; i++) { // 決定每個數的位置
var w = t % i;
for (var j = i - 1; j > w; j--) result[j] = result[j - 1]; // 移位留空
result[w] = arr[i - 1];
t = Math.floor(t / i);
}
if (validateCandidate(result)) { console.log(result); break; }
}
}
perm([1,2,3,4,5,6,7,8,9]);
// 以「位置編碼」陣列做回溯,index[n] 表示第 n 個位置放了哪個元素
function seek(index, n) {
var flag = false, m = n;
do {
index[n]++; // 設定當前位置的元素
if (index[n] == index.length) {
index[n--] = -1; // 已無位置可用,回退
} else if (!(function () {
for (var i = 0; i < n; i++) {
if (index[i] == index[n]) return true; // 與前面衝突
}
return false;
})()) {
if (m == n) flag = true; // 找到一個完整排列
else n++; // 位置後移
}
} while (!flag && n >= 0);
return flag;
}
function perm(arr) {
var index = new Array(arr.length);
for (var i = 0; i < index.length; i++) index[i] = -1;
for (i = 0; i < index.length - 1; i++) seek(index, i); // 初始化為 1,2,3,...,-1
while (seek(index, index.length - 1)) {
var temp = [];
for (i = 0; i < index.length; i++) temp.push(arr[index[i]]);
if (validateCandidate(temp)) { console.log(temp); break; }
}
}
perm([1,2,3,4,5,6,7,8,9]);
/* 全排列(非遞歸求順序)演算法
* 1、建立位置陣列,對位置做排列,成功後轉為元素的排列;
* 2、設 P 是 1~n 的一個全排列 p1,p2...pn:
* (1) 從尾部開始,找出第一個比右邊小的位置索引 j,即 j = max{i | pi < pi+1}
* (2) 在 pj 右邊找出所有比 pj 大的位置中最小的索引 k
* (3) 交換 pj 與 pk
* (4) 將 pj+1...pn 翻轉,得到下一個排列 p'
*
* 例:24310 的下一個排列
* (1) 由右至左找出第一個比右邊小的數字 → 2
* (2) 在 2 之後找出比 2 大且最小者 → 3
* (3) 交換 2 與 3 → 34210
* (4) 翻轉 3 之後的所有數字(4210 → 0124)→ 30124
*/
function swap(arr, i, j) {
var t = arr[i]; arr[i] = arr[j]; arr[j] = t;
}
function sort(index) {
// 從尾端找出第一個「左邊小於右邊」的位置 j
for (var j = index.length - 2; j >= 0 && index[j] > index[j + 1]; j--) ;
if (j < 0) return false; // 已完成全部排列
// 找出比 j 位置的值大的最小者 k(由尾端往前找)
for (var k = index.length - 1; index[k] < index[j]; k--) ;
swap(index, j, k);
// 翻轉 j+1 到尾端
for (j = j + 1, k = index.length - 1; j < k; j++, k--) swap(index, j, k);
return true;
}
function perm(arr) {
var index = new Array(arr.length);
for (var i = 0; i < index.length; i++) index[i] = i;
do {
var temp = [];
for (i = 0; i < index.length; i++) temp.push(arr[index[i]]);
if (validateCandidate(temp)) { console.log(temp); break; }
} while (sort(index));
}
perm([1,2,3,4,5,6,7,8,9]);
三種非遞歸解法的取捨很明顯:求模法能直接跳到第 N 個排列,適合需要隨機取樣的場合;回溯法概念最貼近遞歸;字典序法則是實務上最常用的一種,因為它能以「 continually 取下一個」的方式逐個產出,記憶體用量固定。
不過就這個題目而言,窮舉 362,880 個排列其實是殺雞用牛刀。三階幻方的中心格必定是 5(因為所有幻和為 15,而 5 被四條線共用),由此出發做剪枝,可以瞬間把搜尋空間縮到幾千個候選;幻方的本質解法更可直接用 Siamese 法(奇階幻方演算法)一步填完。這也是algorthm 設計上常見的取捨:暴力法好寫好驗證,但一旦理解問題的結構對稱性,往往能少做幾個數量級的工作。