Generátor sudoku JS: bijekce a faktoriály

Generátor sudoku v JavaScriptu: od prohození k faktoriální bijekci

Vývojáři her a aplikací často řeší úkol generování unikátních sudoku. Místo náročného zpětného způsobu (backtracking) je efektivnější použít geometrické transformace na základní platnou mřížku. Algoritmus se vyvinul od jednoduchých prohození polí do matematické bijekce, která z jednoho vzoru poskytuje 609 492 049 920 unikátních kombinací.

Základní mřížka obsahuje každou číslici 1–9 právě jednou ve sloupcích, řádcích i blokových 3×3 čtvercích. Povolené transformace zachovávají tuto invariantnost:

• Prohození řádků uvnitř bloku 3×3
• Prohození sloupců uvnitř bloku 3×3
• Prohození bloků řádků (3×9)
• Prohození bloků sloupců (9×3)
• Globální prohození číslic

První iterace: seedované prohození

Původní přístup používal 18-znakový hexa-seed pro generování bitů určujících pořadí prohození. Algoritmus Mulberry32 zajišťoval deterministický PRNG.

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

Pole 24 operací prohození se aplikuje ve třech průchodech s bitovou maskou ze seedu. Problematika: pevné složení číslic v blocích vytvářelo vizuální vzory.

Druhá iterace: globální prohození číslic

Přidáním 8 transformací swapDigits(d1, d2) byly tyto vzory odstraněny. Funkce projde celou mřížkou a nahradí všechny výskyty jedné číslice druhou:

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

Tři průchody s různými posuny (0, 13, 29) podle délky pole operací zaručily chaotičnost. Nekomutativita operací zabezpečila rozmanitost.

Třetí iterace: faktoriální bijekce

Konečná verze opustila mutace polí ve prospěch přímého výpočtu. Celkový počet unikátních transformací:

• Permutace 9 číslic: 9! = 362 880
• Permutace 3 bloků řádků: 3! = 6
• Permutace 3 bloků sloupců: 3! = 6
• Permutace řádků uvnitř 3 bloků: (3!)^3 = 216
• Permutace sloupců uvnitř 3 bloků: (3!)^3 = 216

Celkem: 9! × 3! × 3! × (3!)^3 × (3!)^3 = 609 492 049 920

18-znakový hexa-seed se převede na BigInt, vezme se zbytek po dělení MAX_PERMUTATIONS. Číslo N se rozbalí do faktoriální soustavy:

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

// V 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);
// ... ostatní permutace bloků a řádků

Pro každou buňku [r][c] se spočítají původní souřadnice pomocí indexů permutací bloků a řádků uvnitř nich. Hodnota se bere z BASE_GRID[oldR][oldC] a mapuje se prostřednictvím pDigits.

Co je důležité

• Determinismus: jeden seed vždy generuje jednu unikátní mřížku
• Efektivita: O(N) bez mutací polí, vhodné pro real-time generování
• Unikátnost: 6×10¹¹ variant vylučuje kolize při 18-znakovém seedu
• Platnost: všechny transformace zachovávají sudoku-invarianty
• Přenositelnost: mřížka je plně deterministická podle seedu – lze sdílet mezi hráči

— Editorial Team