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

[Jörg Lorenz]

Hi Mike,

ich würde ja gerne ein Sudoku-Spiel programmieren, krieg das aber nicht auf die Reihe.

kennst Du Dich mit VBA aus? Hier ist ein (noch stark zu verbessernder) Lösungsansatz:

http://www.vba-beispiele.de/?details=552

Der untere Teil dürfte Dich nicht interessieren, da er nur zur Formatierung dient.

Viele Grüße

Jörg

[MikΣ]

Moin Jörg,

ich würde ja gerne ein Sudoku-Spiel programmieren, krieg das aber nicht auf die Reihe.

kennst Du Dich mit VBA aus?

nein, aber trotzdem danke!

Schönen Gruß,

Mike

[Swen Wacker]

Moin,

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!)

gefühlte Antwort:
Ich denke, dass ist kein "erstmal", sondern die grundlegende Arbeit. Erst ein komplettes Sudoku erstellen, dann eine festgelegte Zahl an wieder gelöschten Felder schaffen, um so das zu lösende Sudoku anzubieten.
Die Anzahl der freien Felder (und das Verhältnis der Mindest-/Höchstanzahl der Möglichkeiten je Feld / bzw. mögliches Vorkommen einer Zahl in einer Spalte, Reihe, Quadrat) bestimmt dann den Schwierigkeitsgrad.

Viele Grüße

Swen Wacker

[seth]

gudn tach!

Wenn ich mich richtig verstehe, dann verwende ich die Backtracking-Methode im 1. "Weg"

mit dem unterschied, dass du keinen backtracking-algorithmus verwendest. ;-)

bei dir koennte z.b. folgende konstellation auftreten:

482|695|173
914|532|867
368|759|412
123|846|59_<-in dieses feld passt nichts mehr, das script sucht trotzdem weiter... bis zum manuellen abbruch.

an dieser stelle muesste nun backtracking erfolgen.

prost
seth

[MikΣ]

Moin seth,

Wenn ich mich richtig verstehe, dann verwende ich die Backtracking-Methode im 1. "Weg"

mit dem unterschied, dass du keinen backtracking-algorithmus verwendest. ;-)

bei dir koennte z.b. folgende konstellation auftreten:

482|695|173
914|532|867
368|759|412
123|846|59_<-in dieses feld passt nichts mehr, das script sucht trotzdem weiter... bis zum manuellen abbruch.

an dieser stelle muesste nun backtracking erfolgen.

an dieser Stelle fühlte ich mich erstmal wohlig erleuchtet! :-D Herzlichsten Dank für die Erklärung, das habe ich inzwischen angepasst, das Script ausgebaut und es funktioniert jetzt auch. Allerdings ist die Performance unter aller Sau, auf dem Testgrund geht fast gar nichts - wenn nix kommt, ggf. die Seite nochmal erfrischen. Auf nem schnelleren Rechner ist es erträglich - muss ich noch dran schrauben, mein "Backtracking" läuft derzeit so, dass einfach mal von vorne angefangen wird, wenn 500 Versuche in einer Zeile zu nix führten. lol

Danke!

Mike

[seth]

gudn tach Mike!

mein "Backtracking" läuft derzeit so, dass einfach mal von vorne angefangen wird, wenn 500 Versuche in einer Zeile zu nix führten. lol

hmm, das ist wahrlich nicht besonders effizient. ;-)

grober vorschlag in pseudo-code:

  
function belege_zelle(zelle, wert){  
  // belege eine zelle mit einem wert.  
  // also: belege spalte, zeile, subquadrat  
}  
function wert_zulaessig_in_zelle(zelle, wert){  
  // pruefe, ob eine uebergebene zelle mit dem uebergebenen wert zulaessig ist.  
  // also: pruefe zeile, pruefe spalte, pruefe subquadrat  
  return ("zulaessig")?1:0;  
}  
function zelle_belegbar(zelle){  
  // pruefe, ob eine uebergebene zelle ueberhaupt mit einem wert zulaessig belegbar ist.  
  // also sowas wie: nicht belegbar, falls wert_zulaessig_in_zelle(zelle, 1..9)=0  
  return ("zelle belegbar")?1:0;  
}  
function wandere_durchs_feld(aktuelle_zelle){  
  // das soll die start-funktion (bzw. hauptfunktion) werden  
  if(aktuelle_zelle=82. zelle){  
    // abbruch, geschafft, yippieh!  
  }else{  
    if(zelle_belegbar(aktuelle_zelle)){  
      // generiere zufallswert $a  
      while(!wert_zulaessig_in_zelle(aktuelle_zelle, $a)){  
        // generiere zufallswert $a  
      }  
      belege_zelle(aktuelle_zelle, $a);  
      // und jetzt folgt der rekursions-, also der backtrackingschritt  
      wandere_durchs_feld(naechste_zelle);  
    }  
  }  
}  
function wandere_durchs_feld(erste zelle);  

hab's jetzt bloss so hingeschmiert, aber so aehnlich sollte das afais funzen.

prost
seth

[MikΣ]

Moin seth,

mein "Backtracking" läuft derzeit so, dass einfach mal von vorne angefangen wird, wenn 500 Versuche in einer Zeile zu nix führten. lol

hmm, das ist wahrlich nicht besonders effizient. ;-)

aber immerhin besonder ineffizient! :-D

grober vorschlag in pseudo-code:

Tja, danke für den Versuch, das Problem liegt im

// also: pruefe zeile, pruefe spalte, pruefe

  
Wie sollte ich das denn prüfen? Ich prüfe ja in meinem Script auch Zeile, Spalte und Quadrat. Wie soll ich da das von Dir erkannte Problem im Vorhinein vermeiden?  
  
Für einen Deiner Blicke auf mein jüngstes Verbrechen wäre ich dankbar.  
  
  
Schönen Gruß,  
  
Mike

[seth]

gudn tach Mike!

grober vorschlag in pseudo-code:

Tja, danke für den Versuch, das Problem liegt im

// also: pruefe zeile, pruefe spalte, pruefe

Wie sollte ich das denn prüfen? Ich prüfe ja in meinem Script auch Zeile, Spalte und Quadrat.

mehr als das, was du bereits mit in_array tust, sollte in dieser funktion auch gar nicht geschehen

Wie soll ich da das von Dir erkannte Problem im Vorhinein vermeiden?

z.b. durch eine rekursive funktion, d.h. eine funktion, die sich selbst aufruft. auf diese weise realisiert man oft backtracking.

Für einen Deiner Blicke auf mein jüngstes Verbrechen wäre ich dankbar.

erst mal was ganz anderes:
mir faellt auf, dass du gaenzlich auf function und for verzichtest, dafuer aber z.b. (das im kontext fast schon exotisch anmutende) in_array verwendest. auch sonst ist der stil recht ungewoehnlich. dass du ein haufen copy&paste-arbeit haettest sparen koennen, durch sowas wie $s=$z; (statt s[0..9]=array(bla)) ist dir klar?
insgesamt habe ich den eindruck, als habest du bisher sehr wenig programmier-erfahrung, aber trotzdem (oder infolgedessen?) recht interessante ideen.

allerdings habe ich nicht die zeit, mir den kompletten code von vorne bis hinten anzuschauen, sondern kann dir nur tipps allgemeinerer natur geben.

dein script habe ich mal ausprobiert und nach 2 minuten abgebrochen, beim zweiten, vierten und fuenften durchlauf kamen dann jeweils vernuenftige ergebnisse nach jeweils ca. 15 sekunden heraus. beim dritten kam wieder (auch nach >1 min.) nix. der sechste durchgang lieferte nach ca. 1,5 min. ein ergebnis.
also das geht schneller. ;-)

ich empfehle dir, erstmal fuer ein paar stunden die finger von deinem programm zu lassen und erstmal handbuecher zu studieren zu den folgenden themen:
php functions (falls du des englischen nicht so maechtig bist, ersetze im url das "en" durch "de". ich empfehle allerdings eher die englische fassung),
php control structures,
wie backtracking anschaulich funktioniert, zeigt das labyrinth-bsp. imho recht gut.

spiel dann mal ein bissl mit rekursiven funktionen herum und fang dann an, auf papier dir gedanken zu machen, wie du an dein problem herangehen moechtest.
der knackpunkt ist die funktion, die ich wandere_durchs_feld genannt hatte.

ich habe sie hier mal etwas weiter ausgebaut und verwende wieder keinen richtigen php-code, sondern einen hoffentlich uebersichtlicheren pseudo-code:

  
function wandere_durchs_feld($feld, $aktuelle_zelle){  
  $geschafft=0; // rueckgabewert der funktion; wenn geschafft==1, dann ist eine loesung gefunden worden  
  if($aktuelle_zelle==81+1){  
    ausgabe($feld);  
    $geschafft=1;  
  }else{  
    if(zelle_belegbar($feld, $aktuelle_zelle)){  
      // erstelle neun eimer (fuer jede zahl einen) und initialisiere sie mit 0  
      // die eimer werden auf 1 gesetzt, wenn die jeweilige zahl nicht gewaehlt weden darf, weil sie nicht passt, oder weil sie schon mal ausprobiert wurde.  
      $bucket[1..9]=0;  
      while(!$geschafft){  
        // generiere zufallswert  
        $rnd = rand(1, 9); // erzeuge eine zufallszahl  
        // solange  
        //   der eimer der momentan ausgelosten zahl voll (==1) ist oder  
        //   der wert in der zelle nicht stehen darf, weil er sich mit den bisherigen zahlen (in zeile, spalte und subquadrat) beisst,  
        //     durchlaufe die folgende schleife  
        while($bucket[$rnd]==1 || !wert_zulaessig_in_zelle($feld, $akt_koord[0], $akt_koord[1], $rnd)){  
          $bucket[$rnd]=1; // setze den eimer der aktuell ausgelosten zahl auf 1  
          if($bucket[1..9]==1) return 0; // alle eimer voll? dann hoere auf weiterzuprobieren.  
          $rnd = rand(1, 9); // ansonsten lose eine neue zahl aus  
        }  
        $bucket[$rnd]=1; // setze den eimer der _neuen_ ausgelosten zahl auf 1  
        $feld[$aktuelle_zelle]=$rnd; // belege aktuelle zelle  
        // rekursions-/backtrackingschritt  
        $geschafft=wandere_durchs_feld($feld, $aktuelle_zelle+1);  
      }  
    }  
  }  
  return $geschafft;  
}  
// aufruf mit  
wandere_durchs_feld($feld, 0);  
// $feld ist irgendeine passende datenstruktur, z.b. bei dir z.b. $z, $c, $q.

nach der oben genannten lektuere gehe dieses beispiel mal schritt fuer schritt durch. vielleicht mal fuer den fall 4x4 (statt 9x9)

prost
seth

[JürgenB]

Hallo MikΣ,

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!)

so: <http://www.j-berkemeier.de/Sudoku.html@Title=Online Sudoku>.
Das Spiel und die beiden Generatoren sind in Javascript geschrieben. Der Quellcode liegt also bei. Viel Spaß beim lesen.

Gruß, Jürgen

[JürgenB]

Hallo

besser so: Online Sudoku.

Gruß, Jürgen

[lulu]

Huhu

hier noch ein Link
http://www.sudokusolver.co.uk/index.html

Viele Grüße

lulu

[MikΣ]

Moin Jürgen,

besser so: Online Sudoku.

die schnelle Variante ist ne feine Sache, allerdings mag ich mich da nicht durch das weitreichend kommentarlose Script baggern.. Ist doch von Dir, oder? Worin besteht denn der wesentliche Unterschied zur langsamen Variante, die sogar noch einen Hauch länger braucht, als meine?

Schönen Gruß,

Mike

[JürgenB]

Hallo MikΣ,

die schnelle Variante erzeugt die 1. Zeile per Zufall. Für die zweite wird die erste um 3 Felder verschoben, für die 3. um 6, für die 4. um 1, für die 5. um 4, usw.. Wenn also die 1. Zeile zur Veranschaulichung die Zahlen geordnet enthält, sieht das ganze so aus:

1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 3 4 5 6 7 8 9 1
5 6 7 8 9 1 2 3 4
8 9 1 2 3 4 5 6 7
3 4 5 6 7 8 9 1 2
6 7 8 9 1 2 3 4 5
9 1 2 3 4 5 6 7 8

Danach werden Spalten, Zeilen und Dreiergruppen noch so gemischt, dass die Regeln nicht verletzt werden. Leider ist das so erzeugte Sudoku leicht zu durchschauen. Lediglich in der 16*16 Variante ist es brauchbar.

Die 2. Variante ist manchmal schon recht langsam, da Javascript alles andere als schnell ist. Normalerweise bleibt man aber unter 5 s. Ich habe aber noch einige Ideen, wie es besser gehen könnte.

Ziel war ein Sudoku, dass ohne Serverunterstützung auskommt und daher auch offline funktioniert.

Gruß, Jürgen

[MikΣ]

Moin Jürgen,

die schnelle Variante erzeugt die 1. Zeile per Zufall. Für die zweite wird die erste um 3 Felder verschoben, für die 3. um 6, für die 4. um 1, für die 5. um 4, usw..

verstehe, eine durchaus unbefriedigende Lösung..

Die 2. Variante ist manchmal schon recht langsam, da Javascript alles andere als schnell ist. Normalerweise bleibt man aber unter 5 s.

Dann hängt das wohl vom Prozessor ab und Du hast einen schnellen: Bei mir läuft es im Schnitt 15 Sekunden, nie schneller als 10, manchmal länger als 30..

Ich habe aber noch einige Ideen, wie es besser gehen könnte.

Mir sind sie ausgegangen.. Schade, dass ich bei Deinem Script so gar nicht durchblicke.

Schönen Gruß,

Mike

[JürgenB]

Hallo MikΣ,

auch ich habe einige Zeit gebraucht, bis der (langsame) Algorithmus lief. Meine Version blieb am Anfang meistens hängen. Ich habe mir dann aber bei den Berechnungen immer wieder das gerade aktuelle Feld ausgeben lassen (single step mit alert) und so z.B. gesehen, dass der Algorithmus "oszillierte", d.h er schaffte z.B. 70 Felder, kam nicht weiter, ging einige Schritte zurück und vor, um dann wieder an der gleichen Stelle zu landen.
Ich habe jetzt von php keine Ahnung, aber versuch irgendwie, dem Programm bei der Arbeit zuzusehen. So merkst du recht schnell, wo es hakt.

Gruß, Jürgen

[MikΣ]

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

[MikΣ]

  
<?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 500 Versuchen des Zufuegens den ganzen Vorgang neu starten  
  
   else  
    {  
    $unterbrecher++;  
    if ($unterbrecher == 500)  
     {  
  
// 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);  
  
$count=1;  
$c=1;  
     }  
    }  
  }  
  
 $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++;  
 }  
  
?>  

[JürgenB]

Hallo MikΣ,

wenn ich mir dein Script so ansehe, finde ich, du solltest unbedingt die for-Schleife und die Konstruktion if / else if / else in deinen Sprachschatz aufnehmen. Das Script wird dadurch bestimmt viel kürzer und möglicherweise auch performanter.

Gruß, Jürgen

PS: Spielst du auch Sudoku oder programmierst du es nur? Mir hat das Programmieren deutlich mehr Spaß gemacht, als das Spielen.

[seth]

gudn tach!

bevor der thread im archiv verschwindet, moechte ich noch sagen, dass ich mich am samstag ein bissl mit der thematik auseinandergesetzt habe und dabei mit erstaunen etwas festgestellt habe, was vielleicht auch andere erstaunen koennte, aber ihnen wahrscheinlich eher einfach woscht-egal sein wird.

eine frage bei sudoku ist ja die nach einer gescheiten datenstuktur, um moeglichst geschickt die verschiedenen bedingungen (fuer zeilen, spalten, subquadrate) ueberpruefen zu koennen.

ich legte mal den naiven ansatz zugrunde, das feld in einem 2d-array (9x9) zu speichern, wobei die erste komponente die zeile und die zweite die spalte repraesentieren sollte, also z.b.

(0,0) (0,1) (0,2) ... (0,8)
(1,0) (1,1) (1,2) ... (1,8)
  .                     .
  .                     .
  .                     .
(8,0) (8,1) (8,2) ... (8,8)

eine umrechnung in eine (lexikografische 1d-)liste stellt kein problem dar. was jedoch macht man mit den subquadraten?

da gaebe es nun sehr viele moeglichkeiten, die einem spontan einfallen koennten, z.b. nach dem gleichen muster wie oben ein 4d-array (zeile, spalte, subzeile, subspalte) oder ein 3d-array (zeile, spalte, #subquadrat (lexikografisch nummeriert)) oder eben einfach ein 2d-array mit verschachtelter lexikografischer anordnung (#subquadrat, #subelement). letzteres waere also

(0,0) (0,1) (0,2) | (1,0) ... (2,2)
(0,3) (0,4) (0,5) | (1,3) ... (2,5)
(0,6) (0,7) (0,8) | (1,6) ... (2,8)
------------------+----------------
(3,0) (3,1) (3,2) | (4,0) ... (5,2)
  .               .             .
  .               .             .
  .               .             .
(6,6) (6,7) (6,8) | (7,6) ... (8,8)

so, und die umrechnung?

ha, und das ist das mich zunaechst verblueffende:

die abbildung

[latex]f:[0,\ldots,8]^2\to[0,\ldots,8]^2, \left({x \atop y}\right)\mapsto f\left({x \atop y}\right)=\left({3\cdot x/3+y/3\atop 3\cdot x%3+y%3}\right)[/latex],
wobei / die ganzzahlige division ist und % der modulo-operator,
die vom ersten beispiel (zeilen-spalten-koordinaten) ins letzte (subquadrat, subelement) umrechnet, ist selbstinvers, d.h. man nimmt dieselbe formel um die koordinaten in die entgegensetzte richtung zu transformieren, oder kurz: f(f(x,y))=(x,y). wer haette das gedacht?
freut sich jemand mit mir? kommen jetzt so kommentare wie "ach, das haett' ich dir auch gleich sagen koennen!" oder "ei, das sieht man doch!"? oder hatte ich doch eher mit meiner woscht-egal-vermutung recht? ich denke ja letzteres. mir egal. ich find's toll.

prost
seth

[JürgenB]

Hallo seth,

noch einer, den das Sudokuprogrammierfieber gepackt hat.

Vieleicht verstehe ich deinen Ansatz auch nicht, aber er kommt mir recht kompliziert vor. Zum Überprüfen musst du doch nur wissen, zu welcher Spalte, zu welcher Zeile und zu welchem Block das Feld gehört. Zeile und Spalte sind klar:

f(z,s) -> f(z,i), i=0...8 bzw. f(i,s), i=0...8

Beim Block ist es nur etwas komplizierter:

is=Math.floor(z/3)*3;ie=is+3; (in JS)
js=Math.floor(s/3)*3;je=js+3;

f(z,s) -> f(i,j), i=is...ie und j=js...je;

Aber vieleicht meinen wir ja das selbe.

Gruß, Jürgen

[seth]

gudn tach Jürgen!

Vieleicht verstehe ich deinen Ansatz auch nicht, aber er kommt mir recht kompliziert vor.

ist nicht kompliziert.

Zum Überprüfen musst du doch nur wissen, zu welcher Spalte, zu welcher Zeile und zu welchem Block das Feld gehört. Zeile und Spalte sind klar:

f(z,s) -> f(z,i), i=0...8 bzw. f(i,s), i=0...8

ja. (habe ich ebenso gemeint)

Beim Block ist es nur etwas komplizierter:

ja, zunaechst hat man da mal verschiedene moeglichkeiten der indizierung.
z.b. in dem von mir genannten 4d-array [0,...,2]^4 koennte man eine transformation wie folgt angeben:
[0,...,8]^2     -> [0,...,2]^4
(zeile, spalte) -> (zeilenstreifen, spaltenstreifen, zeile im subquadrat, spalte im subquadrat)
(x,y)->(a,b,c,d)
mit
a=x/3   \ diese beiden groessen legen
b=y/3   / das subquadrat fest
c=x%3   \ d=y%3   / und die beiden das element innerhalb des subquadrates,

wobei mit "streifen" jeweils die breite eines subquadrates gemeint ist. man hat also ein grobes und ein feines raster.
"/" bezeichne wieder die ganzzahlige division.

die umkehrabbildung waere ebenfalls sehr unkompliziert:
(a,b,c,d)->(x,y)
x=3*a+c
y=3*b+d

aaaber: das ist langweilig.

is=Math.floor(z/3)*3;ie=is+3;
js=Math.floor(s/3)*3;je=js+3;

f(z,s) -> f(i,j), i=is...ie und j=js...je;

Aber vieleicht meinen wir ja das selbe.

hmm, weiss nicht.
da z ja eine zahl von 0 bis 8 ist, ist somit
is=Math.floor(z/3)*3 eine zahl von 0 bis 2
ie=is+3 ist folglich eine zahl von 3 bis 5

f(z,s) -> f(i,j), i=is...ie und j=js...je;

hier laufen i und j jeweils von 0 bis 3 (oder 2 bis 4 oder 3 bis 5)
was fuer mich so aussieht, als wuerden manche elemente nie getroffen? wie nummerierst du die subquadrate?

naja, ich finde an der von mir beschrieben ueberfuehrungsfunktion so toll, dass die umgekehrte rechnung, also die ueberfuehrung von "subquadratischen" koordinaten in die gewoehnliche zeilen-spalten-koordinaten, auf genau die gleiche weise erfolgt.

am beispiel wird's vielleicht klarer:

  
// die folgende funktion dient nur der umrechnung zeilen-spalten nach subquadratischen koordinaten _und_ auch zurueck!  
// slen=3 ist die laenge eines subquadrates  
function subquadr_umrechnung($x, $y, $slen){  
  return array($slen*floor($x/$slen)+$y/$slen, $slen*($x%$slen)+$y%$slen);  
}  
  
// die folgende funktion ueberprueft nur, ob eine uebergebene zelle mit dem uebergebenen wert gefuellt werden darf.  
// $feld ist ein 2d-array.  
// die zu checkende zelle ist $feld[$zeile][$spalte]  
function wert_zulaessig_in_zelle($feld, $zeile, $spalte, $wert){  
  $zulaessig=1;                          // initialisiere die zelle erstmal als zulaessig  
  $feldlaenge=count($feld);              // also ... = 9  
  $subqulaenge=round(sqrt($feldlaenge)); // = 3 die breite eines subwuadrates  
    // konvertierung von zeilen,spalten nach subquadratischen koordinaten (ist selbstinvers)  
  $subqu=subquadr_umrechnung($zeile, $spalte, $subqulaenge);  
    // schleife ueber alle zellen in zeile/spalte/subquadrat, die schon besetzt sind  
  for($i=0; $i<$feldlaenge && $zulaessig; ++$i){  
    if($zulaessig && $i<$spalte) $zulaessig=$feld[$zeile][$i]!=$wert;  // zeilenkriterium  
    if($zulaessig && $i<$zeile)  $zulaessig=$feld[$i][$spalte]!=$wert; // spaltenkriterium  
    if($zulaessig && $i<$subqu[1]){                                    // subquadrate-kriterium  
        // konvertierung von subquadratischen koordinaten nach zeilen,spalten (involution, s.o.)  
      $temp=subquadr_umrechnung($subqu[0], $i, $subqulaenge);  
      $zulaessig=$feld[$temp[0]][$temp[1]]!=$wert;  
    }  
  }  
  return $zulaessig;  
}

prost
seth

[JürgenB]

Hallo seth,

da z ja eine zahl von 0 bis 8 ist, ist somit
is=Math.floor(z/3)*3 eine zahl von 0 bis 2
ie=is+3 ist folglich eine zahl von 3 bis 5

nein. 8/3 ist ~2.7, floor ergibt 2, mal 3 ergibt 6. Die obigen Operationen liefern also genau die Subquadrate.

hier mein Tester:

  
function check_fld(fld,z,s) {  
 var Zahl=fld[z][s];if(Zahl==" ")Zahl=20;  
 var i,is,ie,j,js,je;  
  for(j=0;j<s;j++) if(Zahl==fld[z][j]) return false;  
  for(j=s+1;j<sz2;j++) if(Zahl==fld[z][j]) return false;  
  for(i=0;i<z;i++) if(Zahl==fld[i][s]) return false;  
  for(i=z+1;i<sz2;i++) if(Zahl==fld[i][s]) return false;  
  is=Math.floor(z/sz)*sz;ie=is+sz;  
  js=Math.floor(s/sz)*sz;je=js+sz;  
  for(i=is;i<is+sz;i++) {  
   for(j=js;j<s;j++) if(Zahl==fld[i][j]) return false;  
   for(j=s+1;j<je;j++) if(Zahl==fld[i][j]) return false;  
  }  
  for(i=z+1;i<ie;i++) {  
   for(j=js;j<s;j++) if(Zahl==fld[i][j]) return false;  
   for(j=s+1;j<je;j++) if(Zahl==fld[i][j]) return false;  
  }  
  return true;  
}  

wobei fld die Matrix ist, z.B. 9*9, z und s sind die Zeilen bzw. Spaltennummer des zu testenden Wertes. sz2 ist die Größe der Matrix, z.B 9. Die Sache ist etwas "aufgebläht, da ich die Schleifen vor/über und nach/unter dem Prüffeld laufen lasse und im Block die schon geprüften Zeilen und Spaltenwerte auslasse.

Der Tester ist vieleicht nicht ganz so elegant, aber ich muss, außer bei den Schleifenzählern, nur vergleichen und nicht rechnen. Da diese Funktion beim Berechnen eines Sudokus "fast unendlich" oft aufgerufen wird, ist Schnelligkeit hier besonders wichtig.

Gruß, Jürgen

[seth]

gudn tach!

da z ja eine zahl von 0 bis 8 ist, ist somit
is=Math.floor(z/3)*3 eine zahl von 0 bis 2
ie=is+3 ist folglich eine zahl von 3 bis 5

nein. 8/3 ist ~2.7, floor ergibt 2, mal 3

ich _schwoere_ der faktor 3 stand da eben noch nicht. *huestel* ;-)
hmpf, ok, hab ich total ueberlesen.
richtig ist also
is=Math.floor(z/3)*3 einer der zahlen 0,3,6
ie=is+3 ist folglich einer der zahlen 3,6,9

ergibt 6. Die obigen Operationen liefern also genau die Subquadrate.

dann versteh ich's, allerdings meintest du eher +2 statt +3. in deinem code pruefst du ja auch mit < und nicht mit <=.
<...+3 ist richtig, aber du schriebst in einem vorigen posting i=is...ie;
egal, hab's ja jetzt verstanden.

hier mein Tester: [ code ]

ok.
du kannst uebrigens noch "eine" addition sparen, indem du im vergleich
i<is+sz
is+sz durch ie ersetzt.

und etwas irritiert mich:

angenommen z=s=1.
dann ergaeben sich die variablen
is=0, ie=3,
js=0, je=3
und die schleifen

for(i=0;i<3;i++) {
 for(j=0;j<1;j++) if(Zahl==fld[i][j]) return false;
 for(j=2;j<3;j++) if(Zahl==fld[i][j]) return false;
}
for(i=2;i<3;i++) {
 for(j=0;j<1;j++) if(Zahl==fld[i][j]) return false;
 for(j=2;j<3;j++) if(Zahl==fld[i][j]) return false;
}
wobei die zweite ueberfluessig ist.

afais koenntest du es geschickter machen, da immer nur 4 felder gecheckt werden muessten. das wuerde alle for-schleifen fuer die subquadrate ueberfluessig machen und diese ersetzen durch kleine ganzzahlige umrechnungen. ach so, js kennt ja iirc gar keine integers, also waeren wieder einige float-divisionen im spiel. hmm, aber vielleicht waer's trotzdem schneller?

Die Sache ist etwas "aufgebläht, da ich die Schleifen vor/über und nach/unter dem Prüffeld laufen lasse und im Block die schon geprüften Zeilen und Spaltenwerte auslasse.

ja, das ist z.b. beim vom OP bevorzugten algorithmus nicht noetig. dort muss man nur die "kleineren" spalten/zeilen/subquadrate pruefen.
(dennoch ist selbstverstaendlich der vertausch-algorithmus um einiges schneller.)

Der Tester ist vieleicht nicht ganz so elegant, aber ich muss, außer bei den Schleifenzählern, nur vergleichen und nicht rechnen.

naja, beim koordinaten um_rechnen_ musst schon schon rechnen, sogar mit float-division. (aber immerhin in keiner der schleifen.)

Da diese Funktion beim Berechnen eines Sudokus "fast unendlich" oft aufgerufen wird, ist Schnelligkeit hier besonders wichtig.

haha, "fast unendlich" oft ist gut. unendlich scheint bei dir recht frueh anzufangen. beim 9x9-feld bei dem algorithmus, den der OP programmieren wollte, sind im schnitt bloss ca. 100 (und selten mehr als 200) rekursionsdurchlaeufe noetig. beim 16x16-feld dagegen ist das schon anders. da kommt man zwar oft mit 2000 durchlaeufen aus, man kann aber auch mal 42k durchlaeufe benoetigen (oder ich habe den kram falsch implementiert).

fuer das 9x9-feld braucht der backtracking-algorithmus uebrigens weniger als eine sekunde unter php auf einer 466 MHz-maschine und er liefert bekanntermassen bessere ergebnisse als der verschiebe-algorithmus.

aaaaber um geschwindigkeit ging/geht es mir ja in diesem fall gar nicht, sondern bloss um die tolle eigenschaft dieser abbildung.

prost
seth

[JürgenB]

Hallo seth,

... <...+3 ist richtig, aber du schriebst in einem vorigen posting i=is...ie;

war etwas ungenau beschrieben.

du kannst uebrigens noch "eine" addition sparen, indem du im vergleich
i<is+sz
is+sz durch ie ersetzt.

das sehe ich mir heute abend mal an. Danke für den Tipp.

und etwas irritiert mich:

angenommen z=s=1.
dann ergaeben sich die variablen
is=0, ie=3,
js=0, je=3
und die schleifen

for(i=0;i<3;i++) {
for(j=0;j<1;j++) if(Zahl==fld[i][j]) return false;
for(j=2;j<3;j++) if(Zahl==fld[i][j]) return false;
}
for(i=2;i<3;i++) {
for(j=0;j<1;j++) if(Zahl==fld[i][j]) return false;
for(j=2;j<3;j++) if(Zahl==fld[i][j]) return false;
}
wobei die zweite ueberfluessig ist.

afais koenntest du es geschickter machen, da immer nur 4 felder gecheckt werden muessten. das wuerde alle for-schleifen fuer die subquadrate ueberfluessig machen und diese ersetzen durch kleine ganzzahlige umrechnungen. ach so, js kennt ja iirc gar keine integers, also waeren wieder einige float-divisionen im spiel. hmm, aber vielleicht waer's trotzdem schneller?

Die Sache ist etwas "aufgebläht, da ich die Schleifen vor/über und nach/unter dem Prüffeld laufen lasse und im Block die schon geprüften Zeilen und Spaltenwerte auslasse.

ja, das ist z.b. beim vom OP bevorzugten algorithmus nicht noetig. dort muss man nur die "kleineren" spalten/zeilen/subquadrate pruefen.
(dennoch ist selbstverstaendlich der vertausch-algorithmus um einiges schneller.)

Das Problem ist hier, dass ich die Felder in zufälliger Reihenfolge belege. Daher kann ich nicht Teile des Tests weglassen. Außerdem wird der Test nicht nur beim Erzeugen sondern auch beim Spielen benutzt. Auf Abfragen, wo im Subquadrat ich gerade bin, wollte ich auch verzichten, daher die vielen Schleifen, die auch schon mal nicht durchlaufen werden. Aber eine Abfrage in einer Schleife durch ein if zu ersetzen, bring auch nichts. Zumal die Schleife ja hin und wieder benötigt wird und das if immer da ist.

haha, "fast unendlich" oft ist gut. unendlich scheint bei dir recht frueh anzufangen. beim 9x9-feld bei dem algorithmus, den der OP programmieren wollte, sind im schnitt bloss ca. 100 (und selten mehr als 200) rekursionsdurchlaeufe noetig. beim 16x16-feld dagegen ist das schon anders. da kommt man zwar oft mit 2000 durchlaeufen aus, man kann aber auch mal 42k durchlaeufe benoetigen (oder ich habe den kram falsch implementiert).

fuer das 9x9-feld braucht der backtracking-algorithmus uebrigens weniger als eine sekunde unter php auf einer 466 MHz-maschine und er liefert bekanntermassen bessere ergebnisse als der verschiebe-algorithmus.

Das ist ganz gut. Mein JS-Algorithmus benötigt da auch auf einer 3GHz-Maschine noch um die 5 s. Vieleicht liegt es ja am Javascript. Aber mit 100 Tests bei 81 Feldern komme ich auf keinem Fall hin. Es sind eher (schätze ich mal, solte ich aber mal messen) so um eine Million.

Der Verschiebealgorithmus ist nicht so besonders gut, da leicht zu durchschauen, aber bei Feldern ab 16*16 liefert er schon brauchbare Ergebnisse, vor allem, wenn der Spieler nicht weiß, wie das Feld erzeugt wurde.

aaaaber um geschwindigkeit ging/geht es mir ja in diesem fall gar nicht, sondern bloss um die tolle eigenschaft dieser abbildung.

Stimmt.

Gruß, Jürgen

[seth]

gudn tach!

du kannst uebrigens noch "eine" addition sparen, indem du im vergleich
i<is+sz
is+sz durch ie ersetzt.

das sehe ich mir heute abend mal an. Danke für den Tipp.

sachlage hat sich geaendert, siehe unten

afais koenntest du es geschickter machen, da immer nur 4 felder gecheckt werden muessten. das wuerde alle for-schleifen fuer die subquadrate ueberfluessig machen und diese ersetzen durch kleine ganzzahlige umrechnungen. ach so, js kennt ja iirc gar keine integers, also waeren wieder einige float-divisionen im spiel. hmm, aber vielleicht waer's trotzdem schneller?

oh, oh.
war schon spaet gestern und ich bin zu schnell druebergehuscht. als ich im bett lag ist mir eingefallen, dass du ja nicht bloss 9x9-felder baust, sondern z.b. auch 16x16. die besagten 4 bedingungen waeren bloss fuer den fall 9x9 schneller. im fall 16x16 braeuchte man jedoch 9 bedingungen. insofern ist der ansatz mit deinen vier (inneren) for-schleifen fuer die subquadrate schon ok. jede schleife, so war es wohl auch von dir gedacht, sollte innerhalb eines subquadrates jeweils den bereich oberhalb links des zu testenden feldes, sowie oberhalb rechts entsprechend unten links und rechts abdecken.

dazu sollte dann aber die bedingung in der ersten aeusseren schleife nicht i<is+sz, sondern i<z lauten.

also:

  
for(i=is;i<z;i++){  
   for(j=js;j<s;j++) if(Zahl==fld[i][j]) return false;  
   for(j=s+1;j<je;j++) if(Zahl==fld[i][j]) return false;  
  }  
  for(i=z+1;i<ie;i++){  
   for(j=js;j<s;j++) if(Zahl==fld[i][j]) return false;  
   for(j=s+1;j<je;j++) if(Zahl==fld[i][j]) return false;  
  }  
}

fuer das 9x9-feld braucht der backtracking-algorithmus uebrigens weniger als eine sekunde unter php auf einer 466 MHz-maschine und er liefert bekanntermassen bessere ergebnisse als der verschiebe-algorithmus.

Das ist ganz gut. Mein JS-Algorithmus benötigt da auch auf einer 3GHz-Maschine noch um die 5 s. Vieleicht liegt es ja am Javascript.

ist anzunehmen.

Aber mit 100 Tests bei 81 Feldern komme ich auf keinem Fall hin. Es sind eher (schätze ich mal, solte ich aber mal messen) so um eine Million.

was meinst du mit tests? funktionsaufrufe der checkfunktion oder anzahl der abfragen/schleifen innerhalb dieser funktion?
ich meinte rekursionsdurchlaeufe. die anzahl der funktionsaufrufe der check-funktion duerfte bei mir schaetzungsweise aber immerhin noch weit unter 1000 liegen.

prost
seth

[JürgenB]

Hallo seth,

dazu sollte dann aber die bedingung in der ersten aeusseren schleife nicht i<is+sz, sondern i<z lauten.

stimmt. Habe ich beim Optimieren übersehen.

was meinst du mit tests? funktionsaufrufe der checkfunktion oder anzahl der abfragen/schleifen innerhalb dieser funktion?
ich meinte rekursionsdurchlaeufe. die anzahl der funktionsaufrufe der check-funktion duerfte bei mir schaetzungsweise aber immerhin noch weit unter 1000 liegen.

Mein Algorithmus zum Erzeugen des Sudokus setzt irgendwo eine Zahl und prüft, ob sie regelkonform ist. Wenn nicht, nächste Zahl probieren. Wenn alle Zahlen durchprobiert sind und keine war ok, dann zurück. Es kann also im ungünstigsten Fall vorkommen, das ich neun mal ohne Erfolg teste und erst dann geht es zurück. Hier liegt auf jedem Fall noch Optimierungspotential. Der Algorithmus ist noch längst nicht fertig, aber bis 9*9 liefert er in vertretbarer Zeit ein Ergebnis.

Ich habe das Programmieren (Fortran und C) bei Messtechnik- und Numerikproblemen (PDEs) gelernt. Rekursionen, Backtracing etc. sind (noch) nicht meine Welt.

Übrigens ist das größte Problem bei meinem zufällig erzeugten Sudoku, dass ich nur weiß, dass es lösbar ist. Ob es auch eindeutig ist, weiß ich nicht. Da auch die Felder mit den Vorgaben zufällig ermittelt werden, weiß ich noch nicht einmal, ob es einen eindeutigen Weg zum Ziel gibt, oder ob ich als Spieler viele Möglichkeiten durchprobieren muss.

Gruß, Jürgen

[seth]

gudn tach!

was meinst du mit tests? funktionsaufrufe der checkfunktion oder anzahl der abfragen/schleifen innerhalb dieser funktion?
ich meinte rekursionsdurchlaeufe. die anzahl der funktionsaufrufe der check-funktion duerfte bei mir schaetzungsweise aber immerhin noch weit unter 1000 liegen.

Mein Algorithmus zum Erzeugen des Sudokus setzt irgendwo eine Zahl und prüft, ob sie regelkonform ist. Wenn nicht, nächste Zahl probieren. Wenn alle Zahlen durchprobiert sind und keine war ok, dann zurück.

wohin genau "zurueck"? (erstmal hoert sich das nach backtracking an)
von welchem algorithmus redest du gerade? du hast ja zwei. ich verstand dich in diesem teilthread bisher so, als spraechest du von jenem (schnellen), der in der wikipedia als "3. weg" beschrieben wird.

Ich habe das Programmieren (Fortran und C) bei Messtechnik- und Numerikproblemen (PDEs) gelernt. Rekursionen, Backtracing etc. sind (noch) nicht meine Welt.

ah, ok, das erklaert so ein bissl dein vorgehen. bei mir war es uebrigens anders herum (erst backtracking in basic und pascal und erst viel spaeter num. pdes und ein klein wenig fortran).

Übrigens ist das größte Problem bei meinem zufällig erzeugten Sudoku, dass ich nur weiß, dass es lösbar ist. Ob es [das] auch eindeutig ist, weiß ich nicht.

ich habe das zwar noch nicht gemacht, aber der erste ansatz der mir dazu einfaellt ist folgender:
man koennte beim aufbauen des feldes ab dem x-ten belegten feld _immer_ _alle_ kombinationen durchprobieren und _nicht_ aufhoeren, wenn man _eine_ gueltige loesung gefunden hat. in backtracking-massstaeben gedacht waere das afais recht einfach zu bewaeltigen.
bei deinem schnellen verschiebe-algorithmus ("3. weg") allerdings, kommt man wohl nicht drumherum erst das komplette feld aufzubauen und nachtraeglich sukzessive einzelne felder wieder zu loeschen, wobei man anschliessend (ab der vierten geloeschten zahl) jeweils mit einem loese-algorithmus ueberprueft, ob man mit einer anderen als der urspruenglichen zahl das sudoku ebenfalls loesen koennte.
ist halt recht aufwendig.

Da auch die Felder mit den Vorgaben zufällig ermittelt werden, weiß ich noch nicht einmal, ob es einen eindeutigen Weg zum Ziel gibt, oder ob ich als Spieler viele Möglichkeiten durchprobieren muss.

naja, das ist ja auch egal. hauptsache das problem ist eindeutig loesbar. der rest (also der weg) ist sache des spielers. ist ja beim sudoku-spielen auch so, dass man manchmal im kopf backtracking betreiben muss.

prost
seth

[JürgenB]

Hallo seth,

wohin genau "zurueck"? (erstmal hoert sich das nach backtracking an)
von welchem algorithmus redest du gerade? du hast ja zwei. ich verstand dich in diesem teilthread bisher so, als spraechest du von jenem (schnellen), der in der wikipedia als "3. weg" beschrieben wird.

der schnelle Algorithmus läuft problemlos und schnell. Da werden die Zahlen ja direkt gesetzt, Zeilen, Spalten und Blöcke noch etwas gemischt ohne die Regeln zu verletzen, und das wars. Der langsame Algorithmus, der ein Zufallssudoku erzeugt, ruft die Testroutine so oft auf, da er ja beim zufälligen setzen der Zahlen irgendwann in die Sackgasse läuft und dann was anderes probieren muss.

Gruß, Jürgen

[at]

Hallo.

der schnelle Algorithmus läuft [...] schnell.

Oh.
MfG, at

[Siramon]

Hallo at,

der schnelle Algorithmus läuft [...] schnell.

Bist du hier der Hof-Journalist?

Grüsse
Siramon,
     ja der Penner aus Nr. 14

[at]

Hallo.

Bist du hier der Hof-Journalist?

Nein, ich lese mehr und schreibe weniger. Und mich nur wegen ein paar unzulässiger Verkürzungen schon so zu beschimpfen, finde ich gar nicht nett. Pfui!
MfG, at

[Siramon]

Hallo at,

Nein, ich lese mehr und schreibe weniger. Und mich nur wegen ein paar unzulässiger Verkürzungen schon so zu beschimpfen, finde ich gar nicht nett. Pfui!

:-) Der Hund gehorcht.

Grüsse
Siramon,
     wuff und wech

[Wilhelm Turtschan]

habe d'ehre at

Hallo.

Bist du hier der Hof-Journalist?

Nein, ich lese mehr und schreibe weniger. Und mich nur wegen ein paar unzulässiger Verkürzungen schon so zu beschimpfen, finde ich gar nicht nett. Pfui!

Vielleicht hat der Kollege aus der Schweiz Magenbeschwerden. Liegt doch in der Kuerze eine Wuerze.

man liest sich
Wilhelm

[at]

Hallo.

Vielleicht hat der Kollege aus der Schweiz Magenbeschwerden.

Vielleicht hatte er ja einen Knochen verschluckt.
MfG, at

[seth]

gudn tach at!

der schnelle Algorithmus läuft [...] schnell.

Oh.

von?

prost
seth

[at]

Hallo.

von?

Wegen.
MfG, at

[seth]

gudn tach at!

Oh.

von?

Wegen.

Oliver von(?) Wegen?

prost
seth

[at]

Hallo.

Oliver von(?) Wegen?

Abwegig.
MfG, at