Generador Sudoku JS: biyección y factoriales

Generador de Sudoku en JavaScript: De intercambios a biyección factorial

Los desarrolladores de juegos y aplicaciones enfrentan frecuentemente el reto de generar cuadrículas de Sudoku únicas. En lugar de abordar el problema NP-difícil del backtracking, un enfoque más eficiente utiliza transformaciones geométricas sobre una cuadrícula base válida. El algoritmo evolucionó desde simples mezclas de arreglos hasta una biyección matemática que genera 609.492.049.920 configuraciones únicas a partir de un solo patrón.

La cuadrícula base contiene cada dígito del 1 al 9 exactamente una vez por fila, columna y bloque 3×3. Las transformaciones válidas preservan esta invariante:

• Permutar filas dentro de un bloque 3×3
• Permutar columnas dentro de un bloque 3×3
• Permutar bloques de filas (3×9)
• Permutar bloques de columnas (9×3)
• Permutación global de dígitos

Primera iteración: Mezcla con semilla

El método inicial utilizaba una semilla hexadecimal de 18 caracteres para generar bits que determinaban la secuencia de intercambios. El algoritmo Mulberry32 proporcionaba un PRNG determinista.

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, b2 * 3 + i); 
    }
  }
};

Se aplicó una matriz de 24 procedimientos de intercambio en tres pasadas usando una máscara de bits derivada de la semilla. Problema: patrones fijos de dígitos dentro de los bloques generaban repetición visual.

Segunda iteración: Intercambios globales de dígitos

Añadir 8 transformaciones swapDigits(d1, d2) eliminó estos patrones. La función escanea toda la cuadrícula, intercambiando todas las instancias de un dígito con otro:

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

Tres pasadas con desplazamientos diferentes (0, 13, 29) módulo la longitud del array de procedimientos aseguraron un comportamiento caótico. Operaciones no conmutativas garantizaron diversidad.

Tercera iteración: Biyección factorial

La versión final abandonó las mutaciones de arreglos a favor de cálculo directo. Total de transformaciones únicas:

• Permutar 9 dígitos: 9! = 362.880
• Permutar 3 bloques de filas: 3! = 6
• Permutar 3 bloques de columnas: 3! = 6
• Permutaciones de filas dentro de 3 bloques: (3!)^3 = 216
• Permutaciones de columnas dentro de 3 bloques: (3!)^3 = 216

Total: 9! × 3! × 3! × (3!)^3 × (3!)^3 = 609.492.049.920

Una semilla hexadecimal de 18 caracteres se convierte en BigInt, luego se aplica módulo MAX_PERMUTATIONS. El número N se descompone en sistema numérico factorial:

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

// En 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);
// ... restantes permutaciones de bloques y líneas

Para cada celda [r][c], se calculan las coordenadas originales mediante índices de permutación de bloque e intra-bloque. El valor se toma de BASE_GRID[oldR][oldC] y se mapea a través de pDigits.

Ventajas clave

• Determinismo: Una semilla siempre genera una cuadrícula única
• Eficiencia: O(N) sin mutaciones de arreglos — ideal para generación en tiempo real
• Unicidad: 6×10¹¹ variantes eliminan colisiones con semillas de 18 caracteres
• Validez: Todas las transformaciones preservan las invariantes del Sudoku
• Portabilidad: La cuadrícula queda completamente definida por la semilla — perfecta para compartir entre jugadores

— Editorial Team