Sudoku JS 生成器：双射和阶乘

JavaScript生成数独：从交换到阶乘双射

游戏和应用开发者常面临生成唯一数独网格的挑战。与其直接解决NP难的回溯问题，更高效的方法是基于基础有效网格进行几何变换。该算法从简单的数组打乱逐步演进为数学上的双射方法，仅用一个模板即可生成609,492,049,920种独特配置。

基础网格中，每行、每列及每个3×3宫格均包含数字1–9各一次。有效的变换操作能保持这一不变性：

• 在3×3宫格内交换行
• 在3×3宫格内交换列
• 交换行块（3×9）
• 交换列块（9×3）
• 全局数字置换

第一版：种子随机打乱

初始方法使用18位十六进制种子生成比特序列，决定交换顺序。Mulberry32算法提供了确定性的伪随机数生成器。

const BASE_GRID = [
  [5,3,4, 6,7,8, 9,1,2],
  [6,7,2, 1,9,5, 3,4,8],
  [1,9,8, 3,4,2, 5,6,7],
  [8,5,9, 7,6,1, 4,2,3],
  [4,2,6, 8,5,3, 7,9,1],
  [7,1,3, 9,2,4, 8,5,6],
  [9,6,1, 5,3,7, 2,8,4],
  [2,8,7, 4,1,9, 6,3,5],
  [3,4,5, 2,8,6, 1,7,9]
];

const Utils = {
  seededRandom: (seed) => {
    return () => {
      let t = seed += 0x6D2B79F5;
      t = Math.imul(t ^ t >>> 15, t | 1);
      t ^= t + Math.imul(t ^ t >>> 7, t | 61);
      return ((t ^ t >>> 14) >>> 0) / 4294967296;
    };
  },
  hexToBits: (hex) => {
    return [...hex].flatMap(char => {
      const v = parseInt(char, 16);
      return [(v >> 3) & 1, (v >> 2) & 1, (v >> 1) & 1, v & 1];
    });
  },
  transforms: {
    swapRows: (g, r1, r2) => { [g[r1], g[r2]] = [g[r2], g[r1]]; },
    swapCols: (g, c1, c2) => { 
      for (let r = 0; r < 9; r++) [g[r][c1], g[r][c2]] = [g[r][c2], g[r][c1]]; 
    }, 
    swapRowBlocks: (g, b1, b2) => { 
      for (let i = 0; i < 3; i++) Utils.transforms.swapRows(g, b1 * 3 + i, b2 * 3 + i); 
    },
    swapColBlocks: (g, b1, b2) => { 
      for (let i = 0; i < 3; i++) Utils.transforms.swapCols(g, b1 * 3 + i, b1 * 3 + i); 
    }
  }
};

使用由种子生成的位掩码，对24个步骤的交换数组执行三轮操作。问题在于：块内固定数字模式导致视觉重复。

第二版：全局数字置换

新增8次 swapDigits(d1, d2) 变换消除了这些模式。该函数扫描整个网格，将一种数字的所有实例与另一种互换：

swapDigits: (g, d1, d2) => {
  for (let r = 0; r < 9; r++) {
    for (let c = 0; c < 9; c++) {
      if (g[r][c] === d1) g[r][c] = d2;
      else if (g[r][c] === d2) g[r][c] = d1;
    }
  }
}

通过三个不同偏移量（0、13、29）对操作数组长度取模，确保行为混沌。非交换性操作保障了多样性。

第三版：阶乘双射

最终版本放弃数组修改，改用直接计算。总共有多少种唯一变换？

• 排列9个数字：9! = 362,880
• 排列3个行块：3! = 6
• 排列3个列块：3! = 6
• 每个块内行排列：(3!)^3 = 216
• 每个块内列排列：(3!)^3 = 216

总计：9! × 3! × 3! × (3!)^3 × (3!)^3 = 609,492,049,920

18位十六进制种子被转换为BigInt，再对 MAX_PERMUTATIONS 取模。编号N通过阶乘数制展开：

const Utils = {
  getPermutation: (arr, k) => {
    let available = [...arr];
    let result = [];
    let fact = 1;
    for (let i = 2; i < available.length; i++) fact *= i;
    for (let i = available.length - 1; i > 0; i--) {
      const idx = Math.floor(k / fact);
      result.push(available[idx]);
      available.splice(idx, 1);
      k %= fact;
      fact /= i;
    }
    result.push(available[0]);
    return result;
  }
};

// 在 generate(seedStr) 中：
const MAX_PERMUTATIONS = 609492049920n;
const seedBigInt = BigInt("0x" + clean);
let N = Number(seedBigInt % MAX_PERMUTATIONS);

const pDigits = Utils.getPermutation([1,2,3,4,5,6,7,8,9], N % 362880); N = Math.floor(N / 362880);
// ... 剩余的块与行列排列

对于每个单元格 [r][c]，通过块内与块内索引计算原始坐标。值来自 BASE_GRID[oldR][oldC]，并经 pDigits 映射后输出。

核心优势

• 确定性：同一种子始终生成唯一网格
• 高效性：O(N)时间复杂度，无需数组修改——适合实时生成
• 唯一性：6×10¹¹种变体，18位种子几乎无碰撞风险
• 有效性：所有变换均保持数独规则不变
• 可移植性：网格完全由种子决定——完美支持玩家间共享

— Editorial Team