題目:將 1~9 這九個不重複的整數填入 3×3 的方格,使得每一列、每一行以及兩條對角線上的數字總和都相等。
策略:窮舉搜尋。先列出所有可能的填法(也就是 1~9 的全排列,共 9! = 362880 種),再逐一過濾出符合條件的答案。
本文的看點在於四種全排列實作的對比:遞迴、求模法、回溯法,以及字典序下一個排列法。
不管是哪一種排列演算法,最後都需要同一組驗證邏輯:
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];
}
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;
}
思路優雅,但代價是把 36 萬個排列全部存在記憶體裡,非常耗資源。實務上應該改成「找到一組就停」的寫法。
這個演算法很巧妙:把「第 n 個排列」直接映射成一組餘數。
以 4 個元素 ["a","b","c","d"]、index = 13 為例,共需迭代 4 次:
["a"]["a","b"]["c","a","b"]["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++) {
var t = index;
for (var 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;
}
}
}
用一個「位置陣列」記錄每個元素被放在第幾個位置,逐一嘗試並偵測衝突:
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);
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;
}
}
}
這是最經典也最有效率的做法。給定一個排列,求下一個排列的四個步驟:
j = max{i | p[i] < p[i+1]}例如 24310 的下一個排列:從右往左找到第一個比右邊小的是 2;它後面比 2 大的數中最小的是 3;交換後得 34210;再把 2(現在是 3)後面的 4210 翻轉成 0124,答案是 30124。
function swap(arr, i, j) {
var t = arr[i]; arr[i] = arr[j]; arr[j] = t;
}
function sort(index) {
// 從尾端找出第一個「左邊小於右邊」的位置
var j;
for (j = index.length - 2; j >= 0 && index[j] > index[j + 1]; j--);
if (j < 0) return false; // 已是最大排列,全部列完
// 從尾端找出比 index[j] 大的數中最小的
var k;
for (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]);
順帶一提,三階幻方的答案其實只有 8 組(考慮旋轉與鏡射後本質上只有 1 組),中心格必定是 5,四角必為偶數。知道這些數學性質後,其實可以跳過窮舉直接構造——但從演算法學習的角度,把四種全排列都寫一遍仍然很值得。