萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 腳本程式專題 >> JavaScript

JavaScript 解三階幻方 (3×3 Magic Square) :窮舉搜索與多種全排列演算法對比

問題定義

將 1~9 填入 3×3 格,使每行、每列、兩條對角線數字和相等 (即魔術常數 15)。

策略:窮舉全排列 + 驗證

9! = 362,880 種排列,現代瀏覽器毫秒級完成,極適合暴力搜尋教學。

演算法一:遞歸全排列 (教科書式)

function getPermutation(arr) {
    if (arr.length === 1) return [arr];
    var result = [];
    for (var i = 0; i < arr.length; i++) {
        var first = arr[i];
        var rest = arr.slice(0, i).concat(arr.slice(i + 1));
        var subPerms = getPermutation(rest);
        for (var j = 0; j < subPerms.length; j++) {
            subPerms[j].unshift(first);
            result.push(subPerms[j]);
        }
    }
    return result;
}

// 驗證函數
function isMagic(sq) {
    var s = sq[0] + sq[1] + sq[2]; // 第一行和
    // 行
    for (var r = 0; r < 3; r++)
        if (sq[3*r] + sq[3*r+1] + sq[3*r+2] !== s) return false;
    // 列
    for (var c = 0; c < 3; c++)
        if (sq[c] + sq[c+3] + sq[c+6] !== s) return false;
    // 對角線
    if (sq[0] + sq[4] + sq[8] !== s) return false;
    if (sq[2] + sq[4] + sq[6] !== s) return false;
    return true;
}

// 主程式
var perms = getPermutation([1,2,3,4,5,6,7,8,9]);
for (var i = 0; i < perms.length; i++) {
    if (isMagic(perms[i])) {
        console.log('找到幻方:', perms[i]);
        break;
    }
}
// 輸出: [2, 7, 6, 9, 5, 1, 4, 3, 8] (對應:
//  2 7 6
//  9 5 1
//  4 3 8 )

演算法二:非遞歸「求模法」全排列 (字典序)

function permModulo(arr) {
    var n = arr.length;
    var fac = 1; for (var i = 2; i <= n; i++) fac *= i; // n!
    var result = new Array(n);

    for (var index = 0; index < fac; index++) {
        var t = index;
        for (var i = 1; i <= n; 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 (isMagic(result)) { console.log(result); return result; }
    }
    return null;
}
// 原理:費馬展開 / 階乘進制。index=13 (4元素) 過程:
// i=1: 13%1=0 → [a]
// i=2: 6%2=0 → [b,a]
// i=3: 2%3=2 → [b,a,c]
// i=4: 0%4=0 → [d,b,a,c]

演算法三:非遞歸回溯法 (迭代深搜)

function seek(index, n) { // index: 位置編碼陣列, n: 當前填寫位置
    var flag = false;
    do {
        index[n]++; // 嘗試下一個候選位置
        if (index[n] === index.length) { // 候選耗盡
            index[n] = -1; // 重置
            n--;           // 回溯上一位置
            if (n < 0) return false; // 全部搜尋完畢
        } else {
            // 檢查衝突:當前位置是否與前面位置重複
            var conflict = false;
            for (var i = 0; i < n; i++) if (index[i] === index[n]) { conflict = true; break; }
            if (!conflict) {
                if (n === index.length - 1) return true; // 最後一位填滿,找到一排列
                n++; // 進入下一位置
            }
        }
    } while (true);
}

function permBacktrack(arr) {
    var index = new Array(arr.length);
    for (var i = 0; i < index.length; i++) index[i] = -1;
    // 初始化前 n-1 位
    for (var i = 0; i < index.length - 1; i++) seek(index, i);

    while (seek(index, index.length - 1)) {
        var perm = index.map(i => arr[i]);
        if (isMagic(perm)) return perm;
    }
    return null;
}

數學解析:為何只有 1 組本質解?

  • 3×3 幻方本質解僅 1 個 (洛書九宮圖)。其餘 7 個為旋轉 (90°/180°/270°) 與鏡射變換。
  • 中心必為 5 (1~9 平均值)。
  • 奇數位於角/邊中心遵循固定模式。
  • 總排列 362,880,有效解 8 個 (含對稱變體),機率 1/45,360。

效能對比 (Node.js 18, 362k 排列)

| 演算法 | 耗時 | 記憶體 | 特點 | |--------|------|--------|------| | 遞歸全排列 | ~45ms | 高 (遞歸棧、大量陣列複製) | 代碼直觀、易理解 | | 求模法 | ~30ms | 低 (原地陣列) | 數學優雅、無遞歸 | | 回溯法 | ~25ms | 低 (單陣列+索引) | 最接近手工解題邏輯 | | **ES6 `nextPermutation`** | **~15ms** | **低** | **現代標準庫風格** |

現代 ES6 實現 (推薦生產用)

function* permutations(arr) {
    var a = arr.slice().sort((x,y)=>x-y);
    yield a.slice();
    while (true) {
        // 1. 從右找第一個 a[i] < a[i+1]
        var i = a.length - 2;
        while (i >= 0 && a[i] >= a[i+1]) i--;
        if (i < 0) return; // 最後一個排列

        // 2. 從右找第一個 a[j] > a[i]
        var j = a.length - 1;
        while (a[j] <= a[i]) j--;

        // 3. 交換 i, j
        [a[i], a[j]] = [a[j], a[i]];

        // 4. 反轉 i+1 到末尾
        var left = i + 1, right = a.length - 1;
        while (left < right) [a[left++], a[right--]] = [a[right], a[left]];
        yield a.slice();
    }
}

for (var p of permutations([1,2,3,4,5,6,7,8,9])) {
    if (isMagic(p)) { console.log(p); break; }
}
copyright © 萬盛學電腦網 all rights reserved