Sudoku

[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