StartseiteZahlenrätselSudokuSkripteKlasse: sudoku_logicMethode: solve()

Methode: solve()

  1. <?php

  2. function solve() {
  3.   //Backup
  4.   $this->arrBackup = $this->arrZeilen;
  5.   //Felder, fuer die mehrere Werte gespeichert sind, werden geloescht
  6.   for ($x=0;$x<9;$x++) {
  7.   for ($y=0;$y<9;$y++) {
  8.   if (9 < $this->arrZeilen[$x][$y])
  9.   $this->arrZeilen[$x][$y] = '';
  10.   }
  11.   }
  12.   //Arrays aktualisieren
  13.   $this->aktualisieren();
  14.   //Berechnung
  15.   for ($x=0;$x<9;$x++) {
  16.   $arrTmp = $this->arrZeilen[$x];
  17.   //Alle moeglichen Werte werden in die Zeilen-Arrays eingetragen
  18.   for ($y=0;$y<9;$y++) {
  19.   for ($z=1;$z<10;$z++) {
  20.   $tmp = 3*floor($x/3)+floor($y/3);
  21.   if ('' == $arrTmp[$y]
  22.   && !in_array($z,$arrTmp)
  23.   && !in_array($z,$this->arrSpalten[$y])
  24.   && !in_array($z,$this->arrFelder[$tmp])) {
  25.   $this->arrZeilen[$x][$y] .= $z;
  26.   }
  27.   }
  28.   }
  29.   //Wenn Zahlen nur einmal in einem Zeilen-Array existieren,
  30.   //dann werden sie gespeichert
  31.   for ($z=1;$z<10;$z++) {
  32.   $tmp = 0;
  33.   for ($y=0;$y<9;$y++) {
  34.   if (ereg($z,$this->arrZeilen[$x][$y]))
  35.   $tmp++;
  36.   }
  37.   if (1 == $tmp) {
  38.   for ($y=0;$y<9;$y++) {
  39.   if (ereg($z,$this->arrZeilen[$x][$y])) {
  40.   $this->arrZeilen[$x][$y] = $z;
  41.   break;
  42.   }
  43.   }
  44.   }
  45.   }
  46.   }
  47.   //Spalten-Arrays werden aktualisiert
  48.   $this->aktualisieren(1);
  49.   for ($x=0;$x<9;$x++) {
  50.   //Wenn Zahlen nur einmal in einem Spalten-Array existieren,
  51.   //dann werden sie gespeichert
  52.   for ($z=1;$z<10;$z++) {
  53.   $tmp = 0;
  54.   for ($y=0;$y<9;$y++) {
  55.   if (ereg($z,$this->arrSpalten[$x][$y]))
  56.   $tmp++;
  57.   }
  58.   if (1 == $tmp) {
  59.   for ($y=0;$y<9;$y++) {
  60.   if (ereg($z,$this->arrSpalten[$x][$y])) {
  61.   $this->arrSpalten[$x][$y] = $z;
  62.   break;
  63.   }
  64.   }
  65.   }
  66.   }
  67.   }
  68.   //Ermittelte Werte werden wieder in den Zeilen-Arrays gespeichert
  69.   for ($x=0;$x<9;$x++) {
  70.   for ($y=0;$y<9;$y++)
  71.   $this->arrZeilen[$y][$x] = $this->arrSpalten[$x][$y];
  72.   }
  73.   //Feld-Arrays werden aktualisiert
  74.   $this->aktualisieren(2);
  75.   for ($x=0;$x<9;$x++) {
  76.   //Wenn Zahlen nur einmal in einem Feld-Array existieren,
  77.   //dann werden sie gespeichert
  78.   for ($z=1;$z<10;$z++) {
  79.   $tmp = 0;
  80.   for ($y=0;$y<9;$y++) {
  81.   if (ereg($z,$this->arrFelder[$x][$y]))
  82.   $tmp++;
  83.   }
  84.   if (1 == $tmp) {
  85.   for ($y=0;$y<9;$y++) {
  86.   if (ereg($z,$this->arrFelder[$x][$y])) {
  87.   $this->arrFelder[$x][$y] = $z;
  88.   break;
  89.   }
  90.   }
  91.   }
  92.   }
  93.   }
  94.   //Ermittelte Werte werden wieder in den Zeilen-Arrays gespeichert
  95.   for ($x=0;$x<9;$x++) {
  96.   for ($y=0;$y<9;$y++) {
  97.   $tmp1 = 3*floor($x/3)+floor($y/3);
  98.   $tmp2 = -9*floor($x/3)+$x*3+$y%3;
  99.   $this->arrZeilen[$tmp1][$tmp2] = $this->arrFelder[$x][$y];
  100.   }
  101.   }
  102.   //Wenn mindestens ein Wert errechnet wurde, so wird die Funktion
  103.   //erneut aufgerufen
  104.   if ($this->arrZeilen != $this->arrBackup)
  105.   $this->solve();
  106. }

  107. ?>

Die Methode sudoku_logic::solve() versucht, durch logische Verfahren das Ergebnis des eingegebenen Sudoku-Rätsels zu finden.
Zuerst werden die Werte von $arrZeilen in $arrBackup gespeichert.
Dann werden alle Werte aus den Feldern, in denen noch mehrere Zahlen möglich sind, gelöscht.
Damit man nun die Zeilen mit den Spalten und Feldern vergleichen kann, müssen nun die Werte aus $arrZeilen in $arrSpalten und $arrFelder geschrieben werden.
Dann werden zuerst alle Werte, die in einem Eingabefeld möglich sind, in $arrZeilen gespeichert. Dazu darf die entsprechende Zahl weder in dem Zeilen-Array, noch im entsprechen Spalten- oder Feld-Array vorkommen. Alle möglichen Werte werden hintereinander gespeichert. Sind z.B. die Zahlen 1, 4 und 8 in einem Feld möglich, so erhält das Feld den Wert "148".
Danach wird überprüft, ob eine Zahl nur einmal in einem Zeilen-Array möglich ist. Sollte das der Fall sein, so wird diese Zahl gespeichert.
Als nächstes werden die Werte aus $arrZeilen in $arrSpalten geschrieben. $mode=1 gibt an, dass nur die Spalten-Arrays aktualisiert werden. Auf diese Weise wird keine Serverleistung verschwendet.
Anschließend wird das Gleiche mit den Spalten-Arrays gemacht.
Danach werden die Werte aus den Spalten-Arrays zurück in die Zeilen-Arrays geschrieben um dann in die Feld-Arrays geschrieben zu werden. Durch $mode=2 werden nur die Feld-Arrays aktualisiert, was ebenfalls Serverleistung sparen soll.
Das Gleiche wird mit den Feld-Arrays gemacht.
Die Werte aus den Feld-Arrays werden zurück in die Zeilen-Arrays geschrieben. Sie können gerne die Berechnung der Array-Schlüssel $tmp1 und $tmp2 nachprüfen. Allen, die dazu keine Lust haben, kann ich sagen, dass es funktioniert.
Zuletzt wird $arrZeilen mit $arrBackup verglichen. Sollte seit dem Anfang der Methode ein neuer Wert errechnet worden sein, dann wird die Methode erneut aufgerufen. Die Methode ist also rekursiv. Erst, wenn sich einmal nichts geändert hat, wird die Methode abgebrochen. Dies ist der Fall, wenn entweder das Rätsel komplett errechnet wurde oder der Algorithmus durch reine Logik nicht mehr weiter kommt.

Links:

Ausblenden