Sudoku optimering

3-8 gange er ingenting. det er andre steder der skal optimeres hvis det skal batte noget.

resten er optimeret og det er også kun denne optimering jeg er interesseret i.
Jeg er nede på 0.4 millisekund.

Nej det er resten pokkerme ikke:

recursive_method(X, Y)
  short allowed = is_allowed( X, Y );  // check all 9 med eet kald
  for a = 1 to 9;
    if ( (allowed & 1<<a) != 0 )
      board[X][Y] = a;
      recursive_method(X+1, Y);
                    // jeg går ud fra du smider en exception når du er færdig

nedsætter antallet af subroutinekald fra 18 til 10
nedsætter antallet af 2D indexeringer fra 9*21+n til 20+n

og de tests der skal udføres indeni is_allowed bliver såvidt jeg kan se også simplere. (du skal blot sørge for at allerede brugte tal in række X og kolonne Y og gruppe X,Y ikke har deres bit sat i den short der returneres.)

mvh JakobA

Min pseudo-kode er kun en simpel beskrivelse af at jeg bruger recursive backtracking. Det er ikke en egentlig beskrivelse af hvordan testene virker. Som før nævnt er det eneste jeg er ude efter at finde ud af hvordan jeg kan teste for hvordan mit "board" virker.
Desuden lignede min kode lidt det du skrev. Men det havde dårligere performance end det jeg bruger nu.
Men som førnævnt er det altså KUN hvordan jeg checker for hvordan boardet skal vende...

OK. Så må jeg nok vige pladsen for jeg ser ikke nogen måde at forudsige hvilken vej der er bedst at gå.

Sudoku er helt symmetrisk mht rækker og søjler, men det kan have en vis virkning i hvilken rækkefølge du tester i din is_allowed.

Der er andre ting man kan overveje, om som andre allerede har overvejet (google er din ven....), såsom i hvert trin at starte med at lede efter de felter, hvor der kun er een mulighed, og tage den som næste felt. Dvs du ikke skal tage felterne i en på forhånd given rækkefølge. Det koster lidt at lede efter felter med een mulighed, men til gengæld gør man rekursionstræet mindre. Andre har prøvet, og jeg mener ikke konklusionen er helt klar.

Når du siger du kan klare det på 0.4 ms er det vel en konkret sudoku-opgave - der burde være forskel på nemme og svære i løsningstid.

Erik >> Det har du så ganske ret i.
Det er en opgave vi blev stillet i skolen(for at vise vi kan backtracke), hvorefter der så er gået sport i at lave den bedste algoritme og test-sekvens. Med opgaven var givet en sudoku-opgave. Af uforklalige årsager var min algoritme hurtigst, indtil vi opdagede at jeg løste den omvendt.
Vi troede så at det kunne hjælpe at tælle blanke felter i første række, kontra første kolonne, da der var en væsentlig forskel i det antal. Men det gjorde sig ikke gældende på andre opgaver.
Nu tester jeg rækker og kolonner i samme metode og firkanter i en seperat da det skar lidt af tiden i alle tilfælde.

Mener du at det vil hjælpe at tælle antal muligheder i de første 3 felter? Det forslag har nemlig også været oppe, men vi ville mene det tager alt for lang tid iforhold til hvad der er sparet.

At lave en "intelligent" test af opgaven som du foreslår har alt for store omkostninger, hvertfald på de lette opgaver, men som før nævnt har det ret stor betydning hvordan brædtet vender, og en test af første række/kolonne betyder stort set intet for løsningstiden.