Generator sudoku JS: bijekcja i silnie

Generator sudoku w JavaScript: od przestawiania do bijekcji faktorialnej

Programiści gier i aplikacji często napotykają problem generowania unikalnych siatek sudoku. Zamiast rozwiązywać trudne zadanie NP przez backtracking, lepiej stosować transformacje geometryczne do podstawowej poprawnej siatki. Algorytm ewoluował od prostego mieszania tablic do matematycznej bijekcji zapewniającej 609 492 049 920 unikalnych kombinacji z jednego wzoru.

Podstawowa siatka zawiera każdą cyfrę od 1 do 9 dokładnie raz w wierszach, kolumnach i blokach 3×3. Dozwolone transformacje zachowują tę niezmienniczość:

• Przestawienie wierszy w obrębie bloku 3×3
• Przestawienie kolumn w obrębie bloku 3×3
• Przestawienie bloków wierszy (3×9)
• Przestawienie bloków kolumn (9×3)
• Globalne przestawienie cyfr

Pierwsza iteracja: seedowane mieszanie

Początkowe podejście wykorzystywało 18-znakowy kod hex do generowania bitów określających sekwencję zamian. Algorytm Mulberry32 zapewniał deterministyczny 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, b1 * 3 + i); 
    }
  }
};

Tablica składająca się z 24 procedur zamian była stosowana w trzech przejściach z maską bitową z seedu. Problem: stała struktura cyfr w blokach tworzyła widoczne wzory.

Druga iteracja: globalne zamiany cyfr

Dodanie 8 transformacji swapDigits(d1, d2) usunęło wzory. Funkcja przechodzi przez całą siatkę, zamieniając wszystkie wystąpienia jednej cyfry na drugą:

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

Trzy przejścia z różnymi przesunięciami (0, 13, 29) modulo długości tablicy procedur zapewniły chaotyczność. Niekomutatywność operacji zagwarantowała różnorodność.

Trzecia iteracja: bijekcja faktorialna

Ostateczna wersja zrezygnowała z modyfikacji tablic na rzecz bezpośredniego obliczania. Łączna liczba unikalnych transformacji:

• Przestawienie 9 cyfr: 9! = 362 880
• Przestawienie 3 bloków wierszy: 3! = 6
• Przestawienie 3 bloków kolumn: 3! = 6
• Przestawienia wierszy wewnątrz 3 bloków: (3!)^3 = 216
• Przestawienia kolumn wewnątrz 3 bloków: (3!)^3 = 216

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

18-znakowy kod hex konwertowany jest na BigInt, a następnie brany jest resztę z dzielenia przez MAX_PERMUTATIONS. Liczba N rozkładana jest w systemie liczbowym faktorialnym:

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

// W 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);
// ... pozostałe przestawienia bloków i linii

Dla każdej komórki [r][c] obliczane są oryginalne współrzędne za pomocą indeksów przestawień bloków i linii wewnątrz nich. Wartość pobierana jest z BASE_GRID[oldR][oldC] i mapowana przez pDigits.

Co jest ważne

• Determinizm: jeden seed zawsze generuje jedną unikalną siatkę
• Efektywność: O(N) bez modyfikacji tablic, idealne do generacji w czasie rzeczywistym
• Unikalność: 6×10¹¹ możliwości eliminuje kolizje przy 18-znakowym seedzie
• Poprawność: wszystkie transformacje zachowują inwarianty sudoku
• Przenośność: siatka całkowicie deterministyczna przez seed umożliwia wymianę między graczami

— Editorial Team