JavaScript 求解三阶幻方（九宫格）的多种算法实现

问题定义与核心思路

三阶幻方的目标是将数字 [1, 2, 3, 4, 5, 6, 7, 8, 9] 进行排列，形成 candidate 数组（映射为 3×3 矩阵）。需满足以下校验条件：

• 常数和: 所有行、列、对角线之和必须等于常数 S = (1+9)*9/2 / 3 = 15。
• 唯一性: 每个数字仅出现一次（由排列生成机制保证）。

通用校验函数如下，判断一个平铺后的数组是否构成有效幻方：

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;
    }
  }
  // 检查两条对角线
  if (sumOfDiagonal(candidate, true) == sum && sumOfDiagonal(candidate, false) == sum) {
    return true;
  }
  return false;
}

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) {
  // isForwardSlash=true 时检查主对角线(0,4,8); false 时检查副对角线(2,4,6)
  return isForwardSlash ? candidate[0] + candidate[4] + candidate[8] : candidate[2] + candidate[4] + candidate[6];
}

方法一：基础递归全排列

这是最直观的暴力破解法。利用递归来生成所有 9! 种可能的组合，然后逐一校验。

第1步：编写递归生成器 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;
}

// 执行主循环
var permutation = getPermutation([1, 2, 3, 4, 5, 6, 7, 8, 9]);
for (var i = 0; i < permutation.length; i++) {
  if (validateCandidate(permutation[i])) {
    console.log('递归法结果:', permutation[i]);
    break; // 找到一个即可结束
  }
}

方法二：状态回溯法（模拟堆栈）

不使用系统调用栈，而是显式维护一个位置索引数组 index 和一个标志位来模拟深度优先搜索。这种方法减少了对象创建，但在最坏情况下仍需遍历大量无效分支。

第1步：实现非递归寻址 seek 函数

seek 负责在当前层级 n 寻找未占用的数字位置。若当前层已满，则重置并退回上一层。

function seek(index, n) {
  var flag = false, m = n; 
  do {
    index[n]++;    // 尝试下一个位置编码
    if (index[n] == index.length) { // 该位置已被所有数字占用
      index[n--] = -1; // 重置当前位置，并退回到上一个位置
    } else {
      // 检查是否与前面已确定的位置冲突
      var conflict = false;
      for (var i = 0; i < n; i++) {
        if (index[i] == index[n]) {
          conflict = true;
          break;
        }
      }
      
      if (!conflict) {
        // 无冲突
        if (m == n) flag = true; // 到达末尾，完成一行排列
        else n++;               // 继续搜索下一层
      }
    }
  } while (!flag && n >= 0);
  return flag;
}

// 主循环
function solveWithBacktrack() {
  var index = new Array(9);
  for(var i=0; i

方法三：非递归全排列（进阶算法）

为了提升效率，可以避开生成全部排列的过程，直接按特定顺序迭代。这里介绍两种成熟的非递归生成排列算法。

第1步：阶乘进制法（Factorial Number System）

原理：任何小于 N! 的整数都可以唯一表示为一个混合进制数。例如 4! = 24。通过除以 1, 2, 3... 的余数，可以直接计算出元素插入的位置。此方法适合随机访问任意第 K 个排列，或者线性遍历。

function permByMod(arr) {
  var result = new Array(arr.length);
  var fac = 1;
  for (var i = 2; i <= arr.length; i++) fac *= i; // 计算 N!
  
  for (var index = 0; index < fac; index++) {
    var t = index;
    for (i = 1; i <= arr.length; i++) {
      var w = t % i;           // 计算当前层的余数，决定插入下标
      // 移位腾出 space
      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;
    }
  }
}

第2步：字典序法（Next Permutation Logic）

这是生成“下一个”排列最高效的算法之一（LeetCode 标准解法）。无需生成全部，只需从初始有序状态开始，一步步推导直到找到目标或穷尽。步骤如下：

1. 从右向左找第一个 index[j] < index[j+1]。
2. 从右向左找第一个 index[k] > index[j]。
3. 交换 j 和 k。
4. 翻转 j+1 到末尾的所有元素。

function swap(arr, i, j) {
  var t = arr[i];
  arr[i] = arr[j];
  arr[j] = t;
}

function getNextPermutation(index) {
  // (1) 从尾部找第一个升序对 j
  var j = index.length - 2;
  while (j >= 0 && index[j] >= index[j + 1]) j--;
  if (j < 0) return false; // 已是最后一个排列，重置并返回失败

  // (2) 从尾部找第一个大于 index[j] 的元素 k
  var k = index.length - 1;
  while (index[k] <= index[j]) k--;

  // (3) 交换 j 和 k
  swap(index, j, k);

  // (4) 翻转 j+1 之后的部分
  for (j++, k = index.length - 1; j < k; j++, k--) {
    swap(index, j, k);
  }
  return true;
}

function permByDictionaryOrder(arr) {
  var index = new Array(arr.length);
  // 初始化为 [0, 1, 2...]
  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 (getNextPermutation(index));
}

总结与对比

以上实现了四种求解三阶幻方的 JS 方案：

• 递归法：代码可读性最好，适合教学演示，但因频繁分配内存，实际运行效率最低。
• 状态回溯法：消除了递归栈开销，但本质仍是 DFS 剪枝，时间复杂度依赖搜索树结构。
• 阶乘法：通过数学映射直接定位，去除了复杂的指针移位判断，适合需要按秩获取排列的场景。
• 字典序法：原地修改数组，空间复杂度 O(1)，且不需要存储所有中间态，是工程实践中生成排列的首选标准算法。

以上就是 JavaScript 解三阶幻方（九宫格）多种算法实现的详细内容，更多关于 JavaScript 数学逻辑与算法优化的资料请关注本站其它相关文章！