Sudoku

[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