Willkommen auf www.sudokurechner.de.vu

Linkweg: Home / Zahlenrätsel / Sudoku / Skripte / Klasse: sudoku_logic / Methode: solve()

Methode: sudoku_logic::solve()

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

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:

 

© 2006-2012 by Jonas Sandrock - - Impressum - Sitemap