Rask algoritme for å løse sudoku er Algorithm X av Donald Knuth. Du representerer løsning av sudoku som eksakt dekselproblem og bruker deretter Algoritme X for å løse EC-problem. Bruk deretter DLX som effektiv implementering av Algoritme X.
Det er en flott forklaring på wikipedia om hvordan du bruker nøyaktig dekning for å løse sudoku.
Jeg kan fortelle deg at DLX er ekstremt rask fost-løsende sudoku i er ofte brukt i den raskeste algoritmen.
http://www.setbb.com/phpbb/index.php?mforum=sudoku er et flott forum med sannsynligvis de beste sudoku-programmererne.
Mellom å fylle rutene med bare ett valg og gå fullstendig rekursivt på brettet er det mer avanserte handlinger du kan gjøre. La oss ta at "region" er én rad, én kolonne, eller én kvadratisk region (3x3 eller 4x4).
Taktikk 1
Hvis det er K kvadrater i et område som bare kan ta identiske K-tall (for eksempel to kvadrater som bare kan ta 2 og 5, eller tre kvadrater som bare kan ta 1, 7 og 8), så kan alle andre kvadrater i det området t ta de spesifikke tallene. Du må iterere hver region for å luke ut "tatte" tall, slik at du kan finne en firkant med bare ett logisk valg (for eksempel kan tredje rute med 2, 4 og 5 logisk bare ta 4, eller fjerde rute med 1, 3, 7 og 8 kan logisk sett bare ta 3).
Dette må løses med iterasjon hvis du ser på følgende eksempel. En region har kvadrater med disse mulige tallene:
A:1 2 3
B:2 3
C:2 3 4 5
D:4 5
E:4 5
Algoritmen skal oppdage at rutene D og E inneholder tallene 4 og 5, så 4 og 5 er ekskludert fra andre ruter i regionen. Algoritmen oppdager da at rutene B og C inneholder tallene 2 og 3, og ekskluderer dem fra andre ruter. Dette etterlater rute A med bare nummer 1.
Taktikk 2
Hvis et tall forekommer i området i bare én rute, så inneholder den ruten logisk det tallet.
Taktikk 3
Taktikk 1 og 2 er bare spesielle tilfeller av taktikk 3 med K-ruter med bare K identiske tall. Du kan ha K-ruter og et sett med K-tall, og disse K-rutene kan inneholde en hvilken som helst delmengde av disse K-tallene. Tenk på følgende eksempel på en region:
A:12
B:2 3
C:13
D:1 2 3 4
Kvadrater A, B og C kan bare inneholde tallene 1, 2 og 3. Det er K for K. Det betyr at enhver annen rute logisk sett ikke kan inneholde disse tallene, noe som etterlater rute D med bare tallet 4.
Taktikk 2 er et spesielt tilfelle av taktikk 3 når K =N - 1.
Taktikk 4
Dra nytte av regioner som overlapper hverandre. Anta at et tall bare kan eksistere i visse firkanter i regionen. Hvis alle disse rutene tilhører en annen overlappende region, bør dette tallet ekskluderes fra alle andre ruter i denne andre regionen.
Taktikk 5
Cache-resultater. Alle regioner skal ha et "skittent" flagg som angir at noe i regionen har endret seg fra forrige gang regionen ble behandlet. Du trenger ikke å behandle regionen med dette flagget ikke angitt.
Mennesker bruker alle disse taktikkene, og hater virkelig å gjette et tall, fordi tilbakesporing er en virkelig smerte. Faktisk er vanskelighetsgraden til et brett målt med det minste antall gjetninger man må gjøre for å løse brettet. For de fleste "ekstreme" brett er en god gjetning nok.