Sudoku

[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