Sudoku: Problem reloaded von MikΣ, 22.01.2006 00:42

Sudoku: Problem reloaded

MikΣ 22.01.2006 00:42

Mittlerweile hab ich also ein funktionierendes Script (siehe hier anhängendes Posting). Dabei ist das Problem die Performance, nur 1/4 der Aufrufe führen auf meiner 800 MHz-Gurke in weniger als 5 Sekunden zur Ausgabe, auf dem Testgrund werden gerne mal die 15 Sekunden Exekutions-Zeit ergebnislos überschritten (sicher ein noch langsamerer Prozessor).

Der einzige für mich derzeit noch denkbare Ansatz ist dieser:

Es wird nicht nach 500, sondern nach 50 Versuchen neu probiert und das auch nicht jeweils von Anfang an, sondern ab dem Anfang des zuletzt begonnenen Drittels, also

||||||||||||| |---|---|---| -> hier,

-1-	-2-	-3-

---	---	---
-4-	-5-	-6-
---	---	---

---	---	---
-7-	-8-	-9-
---	---	---

Erste Frage: Gehe ich in der Annahme überhaupt recht, dass das die Performance nennenswert verbessert? Immerhin wird weniger oft geprüft (der Wert 500 oben hat sich allerdings als sinnvoll erwiesen) und es wird auch nicht jedes Mal ganz von Anfang an angefangen.

Die Frage ergibt sich daraus, dass es aber gar nicht funktioniert! :-D :-/

Hier der komplette Code:


<?php


// Zeilen

$z[1] = array("-",0,0,0,0,0,0,0,0,0);
$z[2] = array("-",0,0,0,0,0,0,0,0,0);
$z[3] = array("-",0,0,0,0,0,0,0,0,0);
$z[4] = array("-",0,0,0,0,0,0,0,0,0);
$z[5] = array("-",0,0,0,0,0,0,0,0,0);
$z[6] = array("-",0,0,0,0,0,0,0,0,0);
$z[7] = array("-",0,0,0,0,0,0,0,0,0);
$z[8] = array("-",0,0,0,0,0,0,0,0,0);
$z[9] = array("-",0,0,0,0,0,0,0,0,0);

// Spalten

$s[1] = array("-",0,0,0,0,0,0,0,0,0);
$s[2] = array("-",0,0,0,0,0,0,0,0,0);
$s[3] = array("-",0,0,0,0,0,0,0,0,0);
$s[4] = array("-",0,0,0,0,0,0,0,0,0);
$s[5] = array("-",0,0,0,0,0,0,0,0,0);
$s[6] = array("-",0,0,0,0,0,0,0,0,0);
$s[7] = array("-",0,0,0,0,0,0,0,0,0);
$s[8] = array("-",0,0,0,0,0,0,0,0,0);
$s[9] = array("-",0,0,0,0,0,0,0,0,0);

// Quadrate

$q[1] = array("-",0,0,0,0,0,0,0,0,0);
$q[2] = array("-",0,0,0,0,0,0,0,0,0);
$q[3] = array("-",0,0,0,0,0,0,0,0,0);
$q[4] = array("-",0,0,0,0,0,0,0,0,0);
$q[5] = array("-",0,0,0,0,0,0,0,0,0);
$q[6] = array("-",0,0,0,0,0,0,0,0,0);
$q[7] = array("-",0,0,0,0,0,0,0,0,0);
$q[8] = array("-",0,0,0,0,0,0,0,0,0);
$q[9] = array("-",0,0,0,0,0,0,0,0,0);

// Fueller

// 9 x fuer 9 Zeilen

$count = 1;
while ($count <= 9)
 {

// 9 x fuer 9 Spalten

 $unterbrecher = 1;

 $c=1;
 while ($c <= 9)
  {

// Bestimmung des aktuellen Quadrates $qc
// |---|---|---|
// |-1-|-2-|-3-|
// |---|---|---|
// |-4-|-5-|-6-|
// |---|---|---|
// |-7-|-8-|-9-|
// |---|---|---|

  if ($count < 4)
   {
   if ($c < 4) $qc = 1;
   if ($c < 7 && $c > 3) $qc = 2;
   if ($c > 6) $qc = 3;
   }
  if ($count < 7 && $count > 3)
   {
   if ($c < 4) $qc = 4;
   if ($c < 7 && $c > 3) $qc = 5;
   if ($c > 6) $qc = 6;
   }
  if ($count > 6)
   {
   if ($c < 4) $qc = 7;
   if ($c < 7 && $c > 3) $qc = 8;
   if ($c > 6) $qc = 9;
   }

// Erzeugung der fortlaufenden Nummer $qSum
// im Array für das aktuelle Quadrat ($q[x])
// |---|
// |123|
// |456|
// |789|
// |---|

  if ($count == 1 || $count == 4 || $count == 7) $qSumA = 0;
  if ($count == 2 || $count == 5 || $count == 8) $qSumA = 3;
  if ($count == 3 || $count == 6 || $count == 9) $qSumA = 6;

  if ($c < 4) $qSumB = $c;
  if ($c > 6) $qSumB = $c - 6;
  if ($c > 3 && $c < 7) $qSumB = $c - 3;

  $qSum = $qSumA + $qSumB;

// Zufallszahl

  srand((double)microtime()*1000000);
  $a = rand(1,9);

// wenn die nicht in akt. Zeile, Spalte, Quadrat vorhanden,
// in akt. Zeile, Spalte, Quadrat zufuegen

  if (!in_array($a, $z[$count]) && !in_array($a, $s[$c]) && !in_array($a, $q[$qc]))
   {

   $z[$count][$c] = $a;
   $s[$c][$count] = $a;
   $q[$qc][$qSum] = $a;

   $c++;
   }

// nach 50 Versuchen des Zufuegens das aktuelle Quadrat-Paket loeschen

   else
    {
    $unterbrecher++;
    if ($unterbrecher == 50)
     {

// feststellen, wieviele Zeilen backgetrackt werden muessen

    $cNeu = $count;
    if ($count == 2 || $count == 5 || $count == 8) $cNeu = $count - 1;
    if ($count == 3 || $count == 6 || $count == 9) $cNeu = $count - 2;
    $rueck = $count - $cNeu;
    $akt = $count - $rueck;

// entsprechende Zeilen, Spalten und Quadrate loeschen

// wenn im ersten Block: Reset!
    if ($akt == 1)
     {

///--v--Anzeige des aktuellen Standes--v--///

echo "<font face=\"monospace\"><center><hr>$akt<hr>";

$cA = 1;
while ($cA <= 9)
 {
 $cB = 1;
 while ($cB <= 9)
  {
  echo $z[$cA][$cB];
  if ($cB == 3 || $cB == 6) echo "|";
  $cB++;
  }
$brech = "<br>";
  if ($cA == 3 || $cA == 6) $brech = "<br>---|---|---<br>";
echo $brech;
 $cA++;
 }

///--^--Anzeige des aktuellen Standes--^--///

// Zeilen

     $z[1] = array("-",0,0,0,0,0,0,0,0,0);
     $z[2] = array("-",0,0,0,0,0,0,0,0,0);
     $z[3] = array("-",0,0,0,0,0,0,0,0,0);

// Spalten

     $s[1] = array("-",0,0,0,0,0,0,0,0,0);
     $s[2] = array("-",0,0,0,0,0,0,0,0,0);
     $s[3] = array("-",0,0,0,0,0,0,0,0,0);
     $s[4] = array("-",0,0,0,0,0,0,0,0,0);
     $s[5] = array("-",0,0,0,0,0,0,0,0,0);
     $s[6] = array("-",0,0,0,0,0,0,0,0,0);
     $s[7] = array("-",0,0,0,0,0,0,0,0,0);
     $s[8] = array("-",0,0,0,0,0,0,0,0,0);
     $s[9] = array("-",0,0,0,0,0,0,0,0,0);

// Quadrate

     $q[1] = array("-",0,0,0,0,0,0,0,0,0);
     $q[2] = array("-",0,0,0,0,0,0,0,0,0);
     $q[3] = array("-",0,0,0,0,0,0,0,0,0);

     $c = 1;
     $count = 1;
     }

// wenn im zweiten Block

    if ($akt > 3 && $akt < 7)
     {

///--v--Anzeige des aktuellen Standes--v--///

echo "<font face=\"monospace\"><center><hr>$akt<hr>";

$cA = 1;
while ($cA <= 9)
 {
 $cB = 1;
 while ($cB <= 9)
  {
  echo $z[$cA][$cB];
  if ($cB == 3 || $cB == 6) echo "|";
  $cB++;
  }
$brech = "<br>";
  if ($cA == 3 || $cA == 6) $brech = "<br>---|---|---<br>";
echo $brech;
 $cA++;
 }

///--^--Anzeige des aktuellen Standes--^--///

// Zeilen

     $z[4] = array("-",0,0,0,0,0,0,0,0,0);
     $z[5] = array("-",0,0,0,0,0,0,0,0,0);
     $z[6] = array("-",0,0,0,0,0,0,0,0,0);

// Spalten

     $s[1][4] = "-"; $s[1][5] = "-"; $s[1][6] = "-";
     $s[2][4] = "-"; $s[2][5] = "-"; $s[2][6] = "-";
     $s[3][4] = "-"; $s[3][5] = "-"; $s[3][6] = "-";
     $s[4][4] = "-"; $s[4][5] = "-"; $s[4][6] = "-";
     $s[5][4] = "-"; $s[5][5] = "-"; $s[5][6] = "-";
     $s[6][4] = "-"; $s[6][5] = "-"; $s[6][6] = "-";
     $s[7][4] = "-"; $s[7][5] = "-"; $s[7][6] = "-";
     $s[8][4] = "-"; $s[8][5] = "-"; $s[8][6] = "-";
     $s[9][4] = "-"; $s[9][5] = "-"; $s[9][6] = "-";

// Quadrate

     $q[4] = array("-",0,0,0,0,0,0,0,0,0);
     $q[5] = array("-",0,0,0,0,0,0,0,0,0);
     $q[6] = array("-",0,0,0,0,0,0,0,0,0);

     $c = 1;
     $count = 4;
     }

// wenn im dritten Block

    if ($akt == 7)
     {

///--v--Anzeige des aktuellen Standes--v--///

echo "<font face=\"monospace\"><center><hr>$akt<hr>";

$cA = 1;
while ($cA <= 9)
 {
 $cB = 1;
 while ($cB <= 9)
  {
  echo $z[$cA][$cB];
  if ($cB == 3 || $cB == 6) echo "|";
  $cB++;
  }
$brech = "<br>";
  if ($cA == 3 || $cA == 6) $brech = "<br>---|---|---<br>";
echo $brech;
 $cA++;
 }

///--^--Anzeige des aktuellen Standes--^--///

// Zeilen

     $z[7] = array("-",0,0,0,0,0,0,0,0,0);
     $z[8] = array("-",0,0,0,0,0,0,0,0,0);
     $z[9] = array("-",0,0,0,0,0,0,0,0,0);

// Spalten

     $s[1][4] = "-"; $s[1][5] = "-"; $s[1][6] = "-";
     $s[2][4] = "-"; $s[2][5] = "-"; $s[2][6] = "-";
     $s[3][4] = "-"; $s[3][5] = "-"; $s[3][6] = "-";
     $s[4][4] = "-"; $s[4][5] = "-"; $s[4][6] = "-";
     $s[5][4] = "-"; $s[5][5] = "-"; $s[5][6] = "-";
     $s[6][4] = "-"; $s[6][5] = "-"; $s[6][6] = "-";
     $s[7][4] = "-"; $s[7][5] = "-"; $s[7][6] = "-";
     $s[8][4] = "-"; $s[8][5] = "-"; $s[8][6] = "-";
     $s[9][4] = "-"; $s[9][5] = "-"; $s[9][6] = "-";


// Quadrate

     $q[7] = array("-",0,0,0,0,0,0,0,0,0);
     $q[8] = array("-",0,0,0,0,0,0,0,0,0);
     $q[9] = array("-",0,0,0,0,0,0,0,0,0);

     $c = 1;
     $count = 7;
     }

     }
    }
  }

 $count++;
 }

// Ausgabe ueber die Zeilen-Arrays

echo "<font face=\"monospace\"><center>";

$cA = 1;
while ($cA <= 9)
 {
 $cB = 1;
 while ($cB <= 9)
  {
  echo $z[$cA][$cB];
  if ($cB == 3 || $cB == 6) echo "|";
  $cB++;
  }
$brech = "<br>";
  if ($cA == 3 || $cA == 6) $brech = "<br>---|---|---<br>";
echo $brech;
 $cA++;
 }

?>

Das Script läuft nie durch, zumindest nicht mit einer Exekutions-Zeit < 2 Minuten. Es ist also wie bei meinem ersten Problem, mit . Irgendwo hier liegt der Fehler:


// wenn im zweiten Block

    if ($akt > 3 && $akt < 7)
     {

// Zeilen

     $z[4] = array("-",0,0,0,0,0,0,0,0,0);
     $z[5] = array("-",0,0,0,0,0,0,0,0,0);
     $z[6] = array("-",0,0,0,0,0,0,0,0,0);

// vermutlich liegt im folgenden Teil das Problem
// hier werden in den Spalten-Arrays die letzten
// Einträge entfernt, also im Array Spalten[x]
// die Einträge 4, 5, und 6:

     $s[1][4] = "-"; $s[1][5] = "-"; $s[1][6] = "-";
     $s[2][4] = "-"; $s[2][5] = "-"; $s[2][6] = "-";
     $s[3][4] = "-"; $s[3][5] = "-"; $s[3][6] = "-";
     $s[4][4] = "-"; $s[4][5] = "-"; $s[4][6] = "-";
     $s[5][4] = "-"; $s[5][5] = "-"; $s[5][6] = "-";
     $s[6][4] = "-"; $s[6][5] = "-"; $s[6][6] = "-";
     $s[7][4] = "-"; $s[7][5] = "-"; $s[7][6] = "-";
     $s[8][4] = "-"; $s[8][5] = "-"; $s[8][6] = "-";
     $s[9][4] = "-"; $s[9][5] = "-"; $s[9][6] = "-";

// Quadrate

     $q[4] = array("-",0,0,0,0,0,0,0,0,0);
     $q[5] = array("-",0,0,0,0,0,0,0,0,0);
     $q[6] = array("-",0,0,0,0,0,0,0,0,0);

     $c = 1;
     $count = 4;
     }

Mit Glück läuft das Script manchmal bis in die letzte Quadrat-Zeile, hängt sich aber allerspätestens da auf. Durch die erste Zeile kommt es jeweils ohne Probleme.

Überseh ich was??

Schönen Gruß,

Mike

Beitrag melden

– Informationen zu den Bewertungsregeln

SELFHTML Forum - Ergänzung zur Dokumentation Übersicht

MikΣ: Sudoku: Problem reloaded

Beitrag lesen

Sudoku: Problem reloaded

Sudoku

Sudoku, jetzt mit Link

Sudoku, noch ein Link

Sudoku

Sudoku: Problem reloaded

Sudoku: Funktioniert