Sudoku

[MikΣ]

Moin,

ich würde ja gerne ein Sudoku-Spiel programmieren, krieg das aber nicht auf die Reihe. Wenn ich mich richtig verstehe, dann verwende ich die Backtracking-Methode im 1. "Weg", hier mein Ansatz:

  
<?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  
  
 $c=1;  
 while ($c <= 9)  
  {  
  
// Zufallszahl  
  
  srand((double)microtime()*1000000);  
  $a = rand(1,9);  
  
// wenn die weder in der aktuellen Zeile, noch der aktuellen Spalte  
// vorhanden ist, in die aktuelle Zeile zufuegen  
  
  if (!in_array($a, $z[$count]) && !in_array($a, $s[$c]))  
   {  
    $z[$count][$c] = $a;  
    $s[$c][$count] = $a;  
  
// Ausgabe der Zeile mit Trennzeichen - nur zum Pruefen  
    echo $z[$count][$c];  
    if ($c == 3 || $c == 6) echo "|";  
  
    $c++;  
    }  
  }  
echo "<hr>";  
 $count++;  
 }  
  
?>  

Hier ist noch nicht berücksichtigt, dass auch in den 9 großen Quadraten alle 9 Zahlen nur einmal vorkommen dürfen.

Es scheitert aber auch hier schon, da sich das Script (spätestens dann) aufhängt, wenn bei

  
  
// 9 x fuer 9 Zeilen  
  
$count = 1;  
while ($count <= 9)  

eine Zahl > 6 eingesetzt wird (in "$count <= x"). Darunter wird das gewünschte Ergebnis geliefert, also sowohl in den Spalten, als auch in den Zeilen stets verschiedene Zahlen.

Vermutlich hat das Script zuviele Operationen durchzuführen, die ja nochmal potenziert würden, wenn das Backtracking für die großen Quadrate hinzu käme.

Wahrscheinlich ist mein Ansatz sowas wie "naiv", ich wüsste aber auch keinen anderen.

Funktionierende Sudokus:

http://www.sudokufun.com/
http://www.sudoku.name/play-sudoku.php?ln=de

Vorsicht: Sehr hohes Suchtpotential!

Fragesatz:

Wie kann ich ein Script hinbekommen, das mir ein vollständig gefülltes Sudoku erzeugt? (<- Darum geht es mir erstmal, nicht um ein funktionierendes Spiel!)

Schönen Gruß,

Mike