Programmieren lernen

/**
 * sudoku (JavaScript)
 * Autor: phi@gressly.ch 
 * Kurs: Siemens Modul 307: April 2010
 */

function startSudoku() {
  var sudoku = initialisiereSudoku();
  loeseSudoku(sudoku);
}

function initialisiereSudoku() {
  sudoku = new Array(9); // 9 Spalten
  sudoku[0] = new Array(0, 8, 1, 0, 0, 0, 7, 3, 0);
  sudoku[1] = new Array(9, 0, 0, 2, 0, 8, 0, 0, 4);
  sudoku[2] = new Array(6, 0, 0, 0, 0, 0, 0, 0, 8);
  sudoku[3] = new Array(0, 3, 0, 7, 0, 1, 0, 2, 0);
  sudoku[4] = new Array(0, 0, 0, 0, 0, 0, 0, 0, 0);
  sudoku[5] = new Array(0, 9, 0, 5, 0, 2, 0, 1, 0);
  sudoku[6] = new Array(8, 0, 0, 0, 0, 0, 0, 0, 7);
  sudoku[7] = new Array(7, 0, 0, 3, 0, 6, 0, 0, 1);
  sudoku[8] = new Array(0, 4, 5, 0, 0, 0, 6, 9, 0);
  return sudoku;
}

function loeseSudoku(sudoku) {
  if(istRegelVerletzt(sudoku)) { 
    return;
  }
  if(istVoll(sudoku)) {
    ausgabe(sudoku);
    return;
  }
  loeseRekursiv(sudoku);
}

/**
 * Erstelle neue einfachere Sudokus und löse diese mit obigem
 * "Algorithmus".
 */
function loeseRekursiv(sudoku) {
  var zeile  = findeErsteZeileMitLeereintraegen(sudoku);
  var ziffer = findeKleinsteUnbenutzteZifferInZeile(sudoku, zeile);
  var sudokus = erzeugeNeueSudokus(sudoku, zeile, ziffer);
  for(var i = 0; i < sudokus.length; i++) {
    loeseSudoku(sudokus[i]);
  }
}

/**
 * Ist eine der drei Sudoku-Reglen (zeile, spalte, block)
 * verletzt?
 */
function istRegelVerletzt(sudoku) {
  return istEineZeileVerletzt(sudoku)   ||
         istEineSpalteVerletzt(sudoku)  ||
         istEinBlockVerletzt(sudoku);
}

function istEineZeileVerletzt(sudoku) {
  for(var zeile = 0; zeile < 9; zeile++) {
    if(istZeileVerletzt(sudoku, zeile)) {
      return true;
    }
  }
  return false;
}

function istEineSpalteVerletzt(sudoku) {
  for(var spalte = 0; spalte < 9; spalte ++) {
    if(istSpalteVerletzt(sudoku, spalte)) {
      return true;
    }
  }
  return false;
}

function istEinBlockVerletzt(sudoku) {
  for(var xb = 0; xb <= 6; xb = xb + 3) {
    for(var yb = 0; yb <= 6; yb = yb + 3) {
      if(istBlockVerletzt(sudoku, xb, yb)) {
        return true;
      }
    }
  }
  return false;
}

function istZeileVerletzt(sudoku, zeile) {
  for(ziffer = 1; ziffer <= 9; ziffer ++) {
    if(vorkommenEinerZifferInZeile(sudoku, ziffer, zeile) > 1) {
      return true;
    }
  }
  return false;
}

/**
 * Wie oft kommt "ziffer" auf "zeile" vor?
 */
function vorkommenEinerZifferInZeile(sudoku, ziffer, zeile) {
  var vk = 0;
  for(var spalte = 0; spalte <= 8; spalte ++) {
    if(sudoku[spalte][zeile] == ziffer) {
      vk = vk + 1;
    }
  }
  return vk;
}

function istSpalteVerletzt(sudoku, spalte) {
  for(ziffer = 1; ziffer <= 9; ziffer ++) {
    if(vorkommenEinerZifferInSpalte(sudoku, ziffer, spalte) > 1) {
      return true;
    }
  }
  return false;
}

/**
 * Wie oft kommt "ziffer" in "spalte" vor?
 */
function vorkommenEinerZifferInSpalte(sudoku, ziffer, spalte) {
  var vk = 0;
  for(var zeile = 0; zeile <= 8; zeile ++) {
    if(sudoku[spalte][zeile] == ziffer) {
      vk = vk + 1;
    }
  }
  return vk;
}

function istBlockVerletzt(sudoku, xb, yb) {
  for(var ziffer = 1; ziffer <= 9; ziffer ++) {
    if(vorkommenInBlock(sudoku, xb, yb, ziffer) > 1) {
      return true;
    }
  }
  return false;
}

/**
 * Wie oft kommt "ziffer" im 3x3 Kästchen ab (xb, yb) vor?
 */
function vorkommenInBlock(sudoku, xb, yb, ziffer) {
  var vk = 0;
  for(var x = xb; x < xb + 3; x ++) {
    for(var y = yb; y < yb + 3; y++) {
      if(ziffer == sudoku[y][x]) {
        vk = vk + 1;
      }
    }
  }
  return vk;
}

/**
 * Sind alle Felder besetzt? 
 */
function istVoll(sudoku) {
  var total = 0;
  for(var zeile = 0; zeile <= 8; zeile ++) {
    for(var spalte = 0; spalte <= 8; spalte ++) {
      if(sudoku[spalte][zeile] > 0) {
        total = total + 1;
      }
    }
  }
  return 81 == total;
}

function ausgabe(sudoku) {
  var para = document.getElementById("ausgabe");
  var ausgabeString = "";
  for(var zeile = 0; zeile <= 8; zeile ++) {
    for(var spalte = 0; spalte <= 7; spalte ++) {
      ausgabeString += sudoku[spalte][zeile] + " | ";
      if(0 == (spalte + 1) % 3) {
        ausgabeString += "| ";
      }
    }
    ausgabeString += sudoku[8][zeile] + "<br />";
    if(0 == (zeile + 1) % 3) {
      ausgabeString += "---------------------------------------------<br />";
    }
  }
  para.innerHTML = ausgabeString;
}

/**
 * Suche die oberste Zeile, die noch nicht voll besetzt ist.
 */
function findeErsteZeileMitLeereintraegen(sudoku) {
  for(var zeile = 0; zeile <= 8; zeile++) {
    if(hatLeerEintragAufZeile(sudoku, zeile)) {
      return zeile;
    }
  }
}

function hatLeerEintragAufZeile(sudoku, zeile) {
  for(var spalte = 0; spalte <= 8; spalte ++) {
    if(0 == sudoku[spalte][zeile]) {
      return true;
    }
  }
}

function findeKleinsteUnbenutzteZifferInZeile(sudoku, zeile) {
  for(ziffer = 1; ziffer <= 9; ziffer++) {
    if(!kommtZifferAufZeileVor(sudoku, ziffer, zeile)) {
      return ziffer;
    }
  }
}

function kommtZifferAufZeileVor(sudoku, ziffer, zeile) {
  for(var spalte = 0; spalte <= 8; spalte ++) {
    if(ziffer == sudoku[spalte][zeile]) {
      return true;
    }
  }
  return false;
}

/**
 * Erzeuge für jedes freie Feld auf "zeile" ein neues
 * Sudoku mit "ziffer" anstelle des freien Feldes.
 */
function erzeugeNeueSudokus(sudoku, zeile, ziffer) {
  var plaetze = findeAnzahlFreiePlaetze(sudoku, zeile);
  var sudokus = new Array(plaetze);
  var pos = 0;
  for(var spalte = 0; spalte <= 8; spalte ++) {
    if(0 == sudoku[spalte][zeile]) {
      sudokus[pos++] = neuesSudoku(sudoku, zeile, spalte, ziffer);
    }
  }
  return sudokus;
}

/**
 * Wie viele Felder sind auf "zeile" noch frei?
 */
function findeAnzahlFreiePlaetze(sudoku, zeile) {
  var anz = 0;
  for(var spalte = 0; spalte <= 8; spalte++) {
    if(0 == sudoku[spalte][zeile]) {
      anz++;
    }
  }
  return anz;
}

/**
 * Erzeuge aus "sudoku" ein neues (Kopie), das an der Stelle
 * [spalte][zeile] die "ziffer" eingefüllt hat.
 * Alle anderen Werte werden einfach aus "sudoku" kopiert.
 */
function neuesSudoku(sudoku, zeile, spalte, ziffer) {
  var neuesSudoku = new Array(9);
  for(var sp = 0; sp <= 8; sp ++) {
    neuesSudoku[sp] = new Array(9);
    for(var ze = 0; ze <= 8; ze ++) {
      neuesSudoku[sp][ze] = sudoku[sp][ze];
    }
  }
  neuesSudoku[spalte][zeile] = ziffer;
  return neuesSudoku;
}

                

/*------------------------------------------------------*\
|  TODO:                                                 |
|  -- funktion zum setzen von möglichen zellwerten       |
|     (und automatischem lösen)                          |
|  -- kürzere notation für vorgegebene gitter            |
|  -- noch zwei komplett sinnlose todos einfügen         |
\*------------------------------------------------------*/

Array.prototype.hasDuplicates = function() {
  let arr = this.slice();
  // ausgenommen null-stellen
  arr = arr.filter(function(c) {
    return c != null;
  });
  return (new Set(arr)).size != arr.length;
}

let Sudoku = function(initArr) {
  let x, y;
  this.isFilled = false;
  this.isConsistent = false;
  this.isSolved = false;

  // hilfsfunktion für zentralfelder
  function getNeighbours(t, x, y) {
    let out = [];
    for (let i = x-1; i <= x+1; i++)
      for (let j = y-1; j <= y+1; j++)
        out.push(t.grid[i][j]);
    return out;
  }

  this.check = function() {
    /* ausgefüllt? */
    this.isFilled = true;
    for (let x = 0; x < this.grid.length; x++)
      for (let y = 0; y < this.grid.length; y++)
        if (this.grid[x][y] == null) this.isFilled = false;
    /* widerspruchsfrei? */
    // zeilen
    let r = true;
    for (x = 0; x < this.grid.length; x++)
      if (this.grid[x].hasDuplicates()) r = false;
    // spalten
    let c = true;
    for (y = 0; y < this.grid.length; y++) {
      buff = [];
      for (x = 0; x < this.grid.length; x++)
        buff.push(this.grid[x][y]);
      if (buff.hasDuplicates()) c = false;
    }
    // blocks
    let f = true;
    for (x of [
      [1, 1], [1, 4], [1, 7],
      [4, 1], [4, 4], [4, 7],
      [7, 1], [7, 4], [7, 7]
    ]) {
      buff = getNeighbours(this, x[0], x[1]);
      if (buff.hasDuplicates()) f = false;
    }
    /* auswertung */
    this.isConsistent = (r && c && f);
    this.isSolved = (this.isFilled && this.isConsistent);
    if (!this.isFilled) console.info('La sudoko ne jam estas plenita.');
    if (!this.isConsistent)
      console.warn('Duobla cifér en linio, kolón a? sekcio.');
    if (this.isSolved)
      alert('Elkoran gratulon,\nla sudók estas solvita!');
  }

  if (initArr) {
    for (x = 0; x < initArr.length; x++)
      for (y = 0; y < initArr.length; y++)
        if (initArr[x][y] == 0) initArr[x][y] = null;
    this.grid = initArr.slice();
    this.check();
  } else {  // leeres sudoku erstellen
    this.grid = new Array(9).fill(null);
    for (x = 0; x < this.grid.length; x++)
      this.grid[x] = new Array(9).fill(null);
  }

  this.print = function() { console.table(this.grid); }

  this.setCell = function(x, y, val) {
    this.grid[x][y] = val;
    this.check();
  }

  this.getCell = function(x, y) { return this.grid[x][y]; }

  this.delCell = function(x, y) { this.setCell(x, y, null); }
}

/*---------------------------*\
|  TEST 1                     |
|                             |
|  1 2 3   - - -   - - -      |
|  4 5 6   - - -   - - -      |
|  7 8 9   - - -   - - -      |
|                             |
|  - - -   - - -   - - -      |
|  - - -   - - -   - - -      |
|  - - -   - - -   - - -      |
|                             |
|  - - -   - - -   - - -      |
|  - - -   - - -   - - -      |
|  - - -   - - -   - - -      |
\*---------------------------*/
let s1 = new Sudoku();
for (let x of [
  [0, 0, 1], [0, 1, 2], [0, 2, 3],
  [1, 0, 4], [1, 1, 5], [1, 2, 6],
  [2, 0, 7], [2, 1, 8], [2, 2, 9],
]) s1.setCell(x[0], x[1], x[2]);

s1.setCell(3, 0, 1);  // gleiche zahl in gleicher spalte
s1.print();
s1.delCell(3, 0);

s1.setCell(0, 8, 1);  // gleiche zahl in gleicher reihe
s1.print();
s1.delCell(0, 8);

s1.setCell(1, 1, 1);  // gleiche zahl in gleicher zelle
s1.print();

/*--------------------------------------------------------------*\
|  TEST 2                                                        |
\*--------------------------------------------------------------*/
let s2 = new Sudoku([
  [4, 8, 7,   9, 2, 5,   6, 1, 3],
  [6, 9, 1,   7, 4, 3,   2, 5, 8],
  [5, 2, 3,   8, 6, 1,   4, 7, 9],

  [7, 4, 5,   2, 3, 9,   8, 6, 1],
  [9, 1, 2,   6, 0, 8,   5, 3, 4],  // zentralzelle noch unbelegt
  [8, 3, 6,   1, 5, 4,   9, 2, 7],

  [1, 7, 8,   5, 9, 2,   3, 4, 6],
  [2, 6, 4,   3, 8, 7,   1, 9, 5],
  [3, 5, 9,   4, 1, 6,   7, 8, 2]
]);
s2.print();

s2.setCell(4, 4, 7);
                

Lösung von: Lisa Salander (Heidi-Klum-Gymnasium Bottrop)