StartseiteZahlenrätselSudokuSkripteKlasse: sudoku_generateMethode: generate()

Methode: generate()

  1. <?php

  2. function generate() {
  3.   $this->arrLoesung = $this->arrZeilen;
  4.   $this->schemaNr = rand(0,count($this->arrSchema)-1);
  5.   for ($x=0;$x<9;$x++) {
  6.   for ($y=0;$y<9;$y++) {
  7.   if (!($this->arrSchema[$this->schemaNr][$x] & pow(2,$y)))
  8.   $this->arrZeilen[$x][$y] = '';
  9.   }
  10.   }
  11.   $this->arrRaetsel = $this->arrZeilen;
  12.   $this->solve();
  13.   $this->check();
  14.   while ('unfinished' == $this->status) {
  15.   $rd1 = rand(0,8);
  16.   $rd2 = rand(0,8);
  17.   while (10 > $this->arrZeilen[$rd1][$rd2]) {
  18.   $rd2++;
  19.   if ($rd2 == 9) {
  20.   $rd2 = 0;
  21.   $rd1++;
  22.   if (9 == $rd1)
  23.   $rd1 = 0;
  24.   }
  25.   }
  26.   $this->arrRaetsel[$rd1][$rd2] = $this->arrLoesung[$rd1][$rd2];
  27.   $rd1 = rand(0,8);
  28.   $rd2 = rand(0,8);
  29.   while ('' == $this->arrRaetsel[$rd1][$rd2]) {
  30.   $rd2++;
  31.   if ($rd2 == 9) {
  32.   $rd2 = 0;
  33.   $rd1++;
  34.   if (9 == $rd1)
  35.   $rd1 = 0;
  36.   }
  37.   }
  38.   $this->arrRaetsel[$rd1][$rd2] = '';
  39.   $this->arrZeilen = $this->arrRaetsel;
  40.   $this->solve();
  41.   $this->check();
  42.   $this->count = 0;
  43.   for ($x=0;$x<9;$x++) {
  44.   for ($y=0;$y<9;$y++) {
  45.   if (10 < $this->arrZeilen[$x][$y])
  46.   $this->count++;
  47.   }
  48.   }
  49.   if ($this->count > $this->lastCount) {
  50.   $this->arrRaetsel = $this->arrLast;
  51.   } else {
  52.   $this->arrLast = $this->arrRaetsel;
  53.   $this->lastCount = $this->count;
  54.   }
  55.   if (25 < time()-$this->chkTime)
  56.   break;
  57.   }
  58.   $this->arrZeilen = $this->arrRaetsel;
  59.   if ('finished' == $this->status) {
  60.   $this->status = 'generated';
  61.   } else {
  62.   for ($x=0;$x<9;$x++) {
  63.   for ($y=0;$y<9;$y++)
  64.   $this->arrZeilen[$x][$y] = '';
  65.   }
  66.   $this->status = 'not_generated';
  67.   }
  68.   $this->dauer();
  69. }

  70. ?>

Die Methode sudoku_generate::generate() erstellt aus einem gelösten Sudoku ein Sudoku-Rätsel, das durch Logik lösbar ist.
Zuerst wird die vom User eingegebene Lösung des Sudokus gespeichert.
Dann wird ein Vorgaben-Schema zufällig ausgewählt.
Als nächstes werden alle Zahlen gelöscht, die nicht im Schema vorgegeben sind.
Nun ist in $arrZeilen ein Rätsel gespeichert, von dem ein Backup gemacht wird.
Dann wird nun versucht, das Rätsel durch Logik zu lösen. Danach wird das Ergebnis geprüft.
In der Regel wird das Schema nicht genau auf das eingegebene Sudoku passen. Deshalb werden so lange die Vorgaben verändert, bis das Rätsel durch Logik lösbar ist.
Dazu wird zuerst wird in einem Feld, in dem mehrere Werte möglich sind, die richtige Zahl gespeichert.
Danach wird in einem Feld, in dem bereits eine Zahl vorgegeben war, diese gelöscht. Dadurch bleibt die Anzahl der vorgegebenen Zahlen konstant.
Mit dem geänderten Schema wird dann versucht, das Sudoku-Rätsel zu lösen.
Als nächstes wird überprüft, ob dieses neue oder das vorige Schema "besser" war, also bei welchem Schema mehr Zahlen eindeutig waren.
Sollte dieses Skript länger als 25 Sekunden ausgeführt werden, wird es unterbrochen.
Die Vorgaben werden wieder in $arrZeilen gespeichert, damit sie später ausgegeben werden können.
Danach wird überprüft, ob die Generierung erfolgreich war. Dem entsprechend wird später das Ergebnis ausgegeben.
Zum Schluss wird die Dauer der Generierung berechnet. Da die Generierung stark vom Zufall abhängt, kann es zu hohen Ausführungszeiten kommen.

Links:

Ausblenden