將 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;
}
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; }
}