Sudoku JS Generator: Bijektion und Fakultäten

Sudoku-Generator in JavaScript: Von Swaps zur Faktoriellen Bijektion

Entwickler von Spielen und Apps stehen oft vor der Herausforderung, eindeutige Sudoku-Felder zu generieren. Anstatt das NP-schwere Backtracking-Problem anzugehen, bietet ein effizienterer Ansatz geometrische Transformationen auf einer Basis-Grid. Der Algorithmus entwickelte sich von einfachen Array-Shufflings hin zu einer mathematischen Bijektion, die aus einem einzigen Template 609.492.049.920 einzigartige Konfigurationen erzeugt.

Das Grundgrid enthält jede Ziffer 1–9 genau einmal pro Zeile, Spalte und 3×3-Block. Gültige Transformationen bewahren diese Invariante:

• Permutation von Zeilen innerhalb eines 3×3-Blocks
• Permutation von Spalten innerhalb eines 3×3-Blocks
• Permutation von Zeilenblöcken (3×9)
• Permutation von Spaltenblöcken (9×3)
• Globale Ziffernpermutation

Erste Iteration: Gezielter Shuffle

Die erste Methode nutzte einen 18-stelligen Hex-Seed, um Bits zu generieren, die die Reihenfolge der Vertauschungen bestimmten. Der Mulberry32-Algorithmus lieferte einen deterministischen 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); 
    }
  }
};

Ein Array mit 24 Vertauschungsoperationen wurde in drei Durchgängen mit einem aus dem Seed abgeleiteten Bitmask angewandt. Problem: Fixe Zahlenmuster innerhalb der Blöcke führten zu visueller Wiederholung.

Zweite Iteration: Globale Ziffernvertauschungen

Durch Hinzufügen von 8 swapDigits(d1, d2)-Transformationen wurden diese Muster eliminiert. Die Funktion durchsucht das gesamte Grid und tauscht alle Vorkommen einer Ziffer gegen eine andere aus:

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

Drei Durchgänge mit unterschiedlichen Offset-Werten (0, 13, 29) modulo der Länge des Operationsarrays sorgten für chaotisches Verhalten. Nicht-kommutative Operationen garantierten Vielfalt.

Dritte Iteration: Faktorielle Bijektion

Die finale Version verzichtete auf Array-Modifikationen zugunsten direkter Berechnung. Gesamtanzahl eindeutiger Transformationen:

• Permutation der 9 Ziffern: 9! = 362.880
• Permutation der 3 Zeilenblöcke: 3! = 6
• Permutation der 3 Spaltenblöcke: 3! = 6
• Zeilenpermutation innerhalb der 3 Blöcke: (3!)^3 = 216
• Spaltenpermutation innerhalb der 3 Blöcke: (3!)^3 = 216

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

Ein 18-stelliger Hex-Seed wird in BigInt umgewandelt und dann modulo MAX_PERMUTATIONS berechnet. Die Zahl N wird im Fakultätszahlensystem entschlüsselt:

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

// In 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);
// ... verbleibende Block- und Zeilenpermutationen

Für jedes Feld [r][c] werden die ursprünglichen Koordinaten über Block- und Intra-Block-Permutationsindizes berechnet. Der Wert stammt aus BASE_GRID[oldR][oldC] und wird über pDigits abgebildet.

Hauptvorteile

• Determinismus: Ein Seed erzeugt immer ein eindeutiges Grid
• Effizienz: O(N) ohne Array-Modifikationen – ideal für Echtzeit-Generierung
• Einzigartigkeit: 6×10¹¹ Varianten vermeiden Kollisionen bei 18-stelligen Seeds
• Gültigkeit: Alle Transformationen bewahren die Sudoku-Invarianten
• Portabilität: Das Grid ist vollständig durch den Seed bestimmt – perfekt für Spieler-zu-Spieler-Teilen

— Editorial Team