Sudoku Generator

So funktioniert das Script

Das Script hat drei große Aufgaben: Es baut das Gitter aus 81 Eingabefeldern, es erzeugt ein vollständig gelöstes Sudoku, und es blendet davon je nach Schwierigkeitsgrad einen Teil der Zahlen wieder aus. Der Clou liegt im mittleren Teil — ein gültiges Sudoku entsteht hier nicht durch Ausprobieren, sondern durch geschicktes Verschieben.

function mischen(liste) {
  let tmp, rand;
  for (let i = 0; i < liste.length; i++) {
    rand = Math.floor(Math.random() * liste.length);
    tmp = liste[i];
    liste[i] = liste[rand];
    liste[rand] = tmp;
  }
}

Der Werkzeugkasten des Scripts: Diese Funktion bringt die Elemente einer Liste in eine zufällige Reihenfolge. Sie geht jeden Platz einmal durch, würfelt einen zweiten Platz aus und vertauscht die beiden über die Hilfsvariable tmp — ohne diesen Zwischenspeicher würde man den ersten Wert beim Zuweisen überschreiben. Im Original hing die Funktion als Array.prototype.shuffle an allen Arrays des Dokuments; als eigenständige Funktion kommt sie fremden Scripts auf der Seite nicht in die Quere.

const reihe = [1, 2, 3, 4, 5, 6, 7, 8, 9];
mischen(reihe);
for (let i = 1; i <= 81; i++) {
  felder[i - 1] = reihe[(i - 1) % 9];
  if (i % 9 === 0) { /* Reihe um drei Stellen weiterdrehen */ }
  if (i % 27 === 0) { /* zusätzlich um eine Stelle weiterdrehen */ }
}

So entsteht das Grundmuster. Die erste Zeile des Sudokus ist einfach eine zufällig gemischte Folge der Zahlen 1 bis 9. Für jede weitere Zeile wird dieselbe Folge um drei Stellen nach links gedreht: Die ersten drei Zahlen wandern ans Ende. Nach drei Zeilen — also am Ende eines Blockbandes, erkennbar an i % 27 === 0 — kommt noch eine Drehung um eine einzelne Stelle dazu. Wer die Zeilen untereinander schreibt, sieht sofort, warum das aufgeht: In jeder Spalte und in jedem 3×3-Block landet dadurch jede Ziffer genau einmal. Der Rest-Operator % ist hier das Taktmaß: Er liefert den Rest einer Division und wird deshalb immer dann 0, wenn eine Zeile oder ein Band voll ist.

for (let i = 0; i <= 8; i++) { zwischen[i] = felder[betr_reihe_1 * 9 + i]; }
for (let i = 0; i <= 8; i++) { felder[betr_reihe_1 * 9 + i] = felder[betr_reihe_2 * 9 + i]; }
for (let i = 0; i <= 8; i++) { felder[betr_reihe_2 * 9 + i] = zwischen[i]; }

Das Grundmuster sieht noch sehr regelmäßig aus, deshalb wird es 400-mal durchgeschüttelt. Bei jedem Durchgang entscheidet der Zufall, ob zwei Zeilen, zwei Spalten oder zwei ganze Blockbänder getauscht werden. Der gezeigte Ausschnitt ist der Zeilentausch — wieder mit einem Zwischenspeicher, diesmal für neun Werte. Entscheidend ist, dass nur innerhalb desselben Dreierblocks getauscht wird (Zeile 0 nur mit 1 oder 2, Zeile 3 nur mit 4 oder 5 und so weiter). Genau das sind die Vertauschungen, bei denen ein gültiges Sudoku gültig bleibt. Alle 81 Zahlen stehen dabei hintereinander in einem einzigen Array felder; die Formel zeile * 9 + spalte rechnet die zweidimensionale Position in diesen einen Index um — ein Muster, das euch bei Spielfeldern ständig begegnen wird.

let number = 36;
if (document.getElementById("sudokuSchw1").checked) { number = 30; }
...
const welche = [];
for (let i = 1; i <= 81; i++) { welche.push(i); }
mischen(welche);

Jetzt kommt der Schwierigkeitsgrad ins Spiel. number ist die Anzahl der Zahlen, die stehen bleiben sollen — 36, 30, 26 oder 22, je nachdem, welcher Radioknopf gerade ausgewählt ist. welche ist eine Liste aller 81 Feldnummern, kräftig durchgemischt: eine Art Lostrommel. Aus ihr werden anschließend so viele Nummern gezogen, wie Zahlen sichtbar bleiben sollen, und nur diese Felder werden gefüllt — alle anderen bleiben leer. welche.shift() entfernt dabei das vorderste Los, damit keine Nummer zweimal gezogen wird.

loesung = felder.slice();

function loesen() {
  for (let i = 1; i <= 81; i++) {
    zelle(i).value = loesung[i - 1];
  }
}

Weil das Script die komplette Lösung ohnehin schon berechnet hat, muss es zum Lösen nichts knobeln: Es legt sich mit felder.slice() eine Kopie der 81 Zahlen beiseite und schreibt sie auf Knopfdruck einfach in die Felder. Ohne slice() hätte man nur einen zweiten Namen für dieselbe Liste — Arrays werden in JavaScript nicht kopiert, wenn man sie zuweist. Das Original hat die Lösung stattdessen in 81 unsichtbaren Eingabefeldern geparkt; eine Variable tut es genauso und spart 81 Elemente im Dokument.

Zum Anpassen: Die vier Zahlen 36, 30, 26 und 22 legen fest, wie viele Ziffern die Schwierigkeitsgrade vorgeben — wer es härter mag, setzt sie herunter. Ganz oben steht außerdem die Einstellung sudokuStatus; auf 3 gesetzt, gibt der Generator das Sudoku vollständig aus, was zum Ausprobieren und Nachvollziehen praktisch ist.