Lag en Sudoku Solver i Java

1. Oversikt

I denne artikkelen skal vi se på Sudoku-puslespill og algoritmer som brukes til å løse det.

Deretter implementerer vi løsninger i Java. Den første løsningen vil være et enkelt brute-force-angrep. Den andre vil bruke Dancing Links-teknikken.

La oss huske at fokuset vi skal fokusere på algoritmer og ikke på OOP-design.

2. Sudoku-puslespillet

Enkelt sagt er Sudoku et kombinatorisk nummerplasseringspuslespill med 9 x 9 cellegitter delvis fylt ut med tall fra 1 til 9. Målet er å fylle gjenværende, blanke felt med resten av tallene slik at hver rad og kolonne bare har en antall av hvert slag.

I tillegg kan ikke hvert tredje x 3-del av rutenettet også ha noe nummer duplisert. Vanskelighetsnivået stiger naturlig med antall blanke felt i hvert brett.

2.1. Test Board

For å gjøre løsningen vår mer interessant og for å validere algoritmen, skal vi bruke "verdens hardeste sudoku" -kort, som er:

8 . . . . . . . . . . 3 6 . . . . . . 7 . . 9 . 2 . . . 5 . . . 7 . . . . . . . 4 5 7 . . . . . 1 . . . 3 . . . 1 . . . . 6 8 . . 8 5 . . . 1 . . 9 . . . . 4 . .

2.2. Løst styret

Og for å ødelegge løsningen raskt - det riktig løste puslespillet gir oss følgende resultat:

8 1 2 7 5 3 6 4 9 9 4 3 6 8 2 1 7 5 6 7 5 4 9 1 2 8 3 1 5 4 2 3 7 8 9 6 3 6 9 8 4 5 7 2 1 2 8 7 1 6 9 5 3 4 5 2 1 9 7 4 3 6 8 4 3 8 5 2 6 9 1 7 7 9 6 3 1 8 4 5 2

3. Backtracking-algoritme

3.1. Introduksjon

Backtracking-algoritme prøver å løse puslespillet ved å teste hver celle for en gyldig løsning.

Hvis det ikke er brudd på begrensninger, beveger algoritmen seg til neste celle, fyller ut alle potensielle løsninger og gjentar alle kontroller.

Hvis det er et brudd, øker det celleverdien. En gang når verdien av cellen 9, og det er fortsatt brudd, så beveger algoritmen seg tilbake til forrige celle og øker verdien av den cellen.

Den prøver alle mulige løsninger.

3.2. Løsning

La oss først og fremst definere brettet vårt som et todimensjonalt utvalg av heltall. Vi bruker 0 som vår tomme celle.

int [] [] tavle = {{8, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 3, 6, 0, 0, 0, 0, 0}, {0 , 7, 0, 0, 9, 0, 2, 0, 0}, {0, 5, 0, 0, 0, 7, 0, 0, 0}, {0, 0, 0, 0, 4, 5 , 7, 0, 0}, {0, 0, 0, 1, 0, 0, 0, 3, 0}, {0, 0, 1, 0, 0, 0, 0, 6, 8}, {0 , 0, 8, 5, 0, 0, 0, 1, 0}, {0, 9, 0, 0, 0, 0, 4, 0, 0}};

La oss lage en løse() metoden som tar borde som inngangsparameter og gjentas gjennom rader, kolonner og verdier som tester hver celle for en gyldig løsning:

privat boolsk løs (int [] [] bord) {for (int rad = BOARD_START_INDEX; rad <BOARD_SIZE; rad ++) {for (int kolonne = BOARD_START_INDEX; kolonne <BOARD_SIZE; kolonne ++) {hvis (bord [rad] [kolonne] = = NO_VALUE) {for (int k = MIN_VALUE; k <= MAX_VALUE; k ++) {bord [rad] [kolonne] = k; hvis (isValid (tavle, rad, kolonne) && løse (tavle)) {return true; } bord [rad] [kolonne] = NO_VALUE; } returner falsk; }}} returner sant; }

En annen metode vi trengte er er gyldig() metode, som skal kontrollere Sudoku-begrensninger, dvs. sjekke om raden, kolonnen og 3 x 3-rutenettet er gyldige:

privat boolsk isValid (int [] [] tavle, int rad, int kolonne) {retur (rowConstraint (board, row) && columnConstraint (board, column) && subsectionConstraint (board, row, column)); }

Disse tre kontrollene er relativt like. Først, la oss starte med radkontroller:

privat boolsk rowConstraint (int [] [] tavle, int rad) {boolean [] constraint = new boolean [BOARD_SIZE]; returner IntStream.range (BOARD_START_INDEX, BOARD_SIZE) .allMatch (kolonne -> checkConstraint (bord, rad, begrensning, kolonne)); }

Deretter bruker vi nesten identisk kode for å validere kolonne:

privat boolsk kolonneConstraint (int [] [] tavle, int kolonne) {boolsk [] begrensning = ny boolsk [BOARD_SIZE]; returner IntStream.range (BOARD_START_INDEX, BOARD_SIZE) .allMatch (rad -> sjekkConstraint (bord, rad, begrensning, kolonne)); }

Videre må vi validere 3 x 3 underavsnitt:

privat boolsk underseksjonConstraint (int [] [] tavle, int rad, int kolonne) {boolean [] constraint = new boolean [BOARD_SIZE]; int subsectionRowStart = (rad / SUBSECTION_SIZE) * SUBSECTION_SIZE; int subsectionRowEnd = subsectionRowStart + SUBSECTION_SIZE; int subsectionColumnStart = (kolonne / SUBSECTION_SIZE) * SUBSECTION_SIZE; int subsectionColumnEnd = subsectionColumnStart + SUBSECTION_SIZE; for (int r = subsectionRowStart; r <subsectionRowEnd; r ++) {for (int c = subsectionColumnStart; c <subsectionColumnEnd; c ++) {if (! checkConstraint (board, r, constraint, c)) return false; }} returner sant; }

Til slutt trenger vi en checkConstraint () metode:

boolsk sjekkConstraint (int [] [] tavle, int rad, boolsk [] begrensning, int kolonne) {if (tavle [rad] [kolonne]! = NO_VALUE) {hvis (! begrensning [tavle [rad] [kolonne] - 1 ]) {begrensning [tavle [rad] [kolonne] - 1] = sann; } annet {returner falsk; }} returner sant; }

En gang er alt det gjort er gyldig() metoden kan rett og slett komme tilbake ekte.

Vi er nesten klare til å teste løsningen nå. Algoritmen er ferdig. Imidlertid kommer den tilbake ekte eller falsk kun.

Derfor, for å visuelt sjekke tavlen, trenger vi bare for å skrive ut resultatet. Tilsynelatende er dette ikke en del av algoritmen.

privat ugyldig printBoard () {for (int rad = BOARD_START_INDEX; rad <BOARD_SIZE; rad ++) {for (int kolonne = BOARD_START_INDEX; kolonne <BOARD_SIZE; kolonne ++) {System.out.print (bord [rad] [kolonne] + "" ); } System.out.println (); }}

Vi har vellykket implementert backtracking-algoritme som løser Sudoku-puslespillet!

Det er tydeligvis rom for forbedringer da algoritmen sjekker hver mulige kombinasjon om og om igjen (selv om vi vet at løsningen er ugyldig).

4. Dancing Links

4.1. Nøyaktig deksel

La oss se på en annen løsning. Sudoku kan beskrives som et eksakt dekkproblem, som kan representeres av forekomstmatrise som viser forholdet mellom to objekter.

For eksempel hvis vi tar tall fra 1 til 7 og samlingen av sett S = {A, B, C, D, E, F}, hvor:

  • EN = {1, 4, 7}
  • B = {1, 4}
  • C = {4, 5, 7}
  • D = {3, 5, 6}
  • E = {2, 3, 6, 7}
  • F = {2, 7}

Målet vårt er å velge slike delmengder at hvert nummer er der bare en gang og ingen gjentas, derav navnet.

Vi kan representere problemet ved hjelp av en matrise, der kolonner er tall og rader er sett:

 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | A | 1 | 0 | 0 | 1 | 0 | 0 | 1 | B | 1 | 0 | 0 | 1 | 0 | 0 | 0 | C | 0 | 0 | 0 | 1 | 1 | 0 | 1 | D | 0 | 0 | 1 | 0 | 1 | 1 | 0 | E | 0 | 1 | 1 | 0 | 0 | 1 | 1 | F | 0 | 1 | 0 | 0 | 0 | 0 | 1 |

Delsamling S * = {B, D, F} er nøyaktig omslag:

 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | B | 1 | 0 | 0 | 1 | 0 | 0 | 0 | D | 0 | 0 | 1 | 0 | 1 | 1 | 0 | F | 0 | 1 | 0 | 0 | 0 | 0 | 1 |

Hver kolonne har nøyaktig en 1 i alle valgte rader.

4.2. Algoritme X

Algoritme X er en “Prøving og feiling tilnærming” for å finne alle løsninger på det nøyaktige dekkproblemet, dvs. starte med eksemplet vårt S = {A, B, C, D, E, F}, finn undersamling S * = {B, D, F}.

Algoritme X fungerer som følger:

  1. Hvis matrisen EN har ingen kolonner, den nåværende delløsningen er en gyldig løsning;

    avslutte vellykket, ellers velger du en kolonne c (deterministisk)

  2. Velg en rad r slik at ENr, c = 1 (ikke-bestemmende, dvs. prøv alle muligheter)
  3. Inkluder rad r i delløsningen
  4. For hver kolonne j slik at ENr, j = 1, for hver rad Jeg slik at ENJeg, j = 1,

    slett rad Jeg fra matrise EN ogslett kolonne j fra matrise EN

  5. Gjenta denne algoritmen rekursivt på den reduserte matrisen EN

En effektiv implementering av Algorithm X er Dancing Links algoritme (forkortet DLX) foreslått av Dr. Donald Knuth.

Følgende løsning har blitt sterkt inspirert av denne Java-implementeringen.

4.3. Nøyaktig dekkproblem

Først må vi lage en matrise som vil representere Sudoku-puslespillet som et nøyaktig dekkproblem. Matrisen vil ha 9 ^ 3 rader, dvs. en rad for hver eneste mulige posisjon (9 rader x 9 kolonner) av hvert mulige tall (9 tall).

Kolonner representerer brettet (igjen 9 x 9) multiplisert med antall begrensninger.

Vi har allerede definert tre begrensninger:

  • hver rad vil bare ha ett nummer av hvert slag
  • hver kolonne vil bare ha ett nummer av hvert slag
  • hvert underavsnitt vil bare ha ett nummer av hvert slag

I tillegg er det implisitt fjerde begrensning:

  • bare ett tall kan være i en celle

Dette gir fire begrensninger totalt og derfor 9 x 9 x 4 kolonner i Exact Cover-matrisen:

privat statisk int BOARD_SIZE = 9; privat statisk int SUBSECTION_SIZE = 3; privat statisk int NO_VALUE = 0; private static int CONSTRAINTS = 4; privat statisk int MIN_VALUE = 1; privat statisk int MAX_VALUE = 9; privat statisk int COVER_START_INDEX = 1;
privat int getIndex (int rad, int kolonne, int num) {retur (rad - 1) * BOARD_SIZE * BOARD_SIZE + (kolonne - 1) * BOARD_SIZE + (num - 1); }
privat boolsk [] [] createExactCoverBoard () {boolsk [] [] coverBoard = ny boolsk [BOARD_SIZE * BOARD_SIZE * MAX_VALUE] [BOARD_SIZE * BOARD_SIZE * CONSTRAINTS]; int hBase = 0; hBase = checkCellConstraint (coverBoard, hBase); hBase = checkRowConstraint (coverBoard, hBase); hBase = checkColumnConstraint (coverBoard, hBase); checkSubsectionConstraint (coverBoard, hBase); retur dekkeBord; } privat int checkSubsectionConstraint (boolsk [] [] coverBoard, int hBase) {for (int rad = COVER_START_INDEX; rad <= BOARD_SIZE; rad + = SUBSECTION_SIZE) {for (int kolonne = COVER_START_INDEX; kolonne <= BOARD_SIZE; kolonne + = SUBSECT ) {for (int n = COVER_START_INDEX; n <= BOARD_SIZE; n ++, hBase ++) {for (int rowDelta = 0; rowDelta <SUBSECTION_SIZE; rowDelta ++) {for (int columnDelta = 0; columnDelta <SUBSECTION_SIZE; columnDelta ++) {int index = getIndex (rad + radDelta, kolonne + kolonneDelta, n); coverBoard [index] [hBase] = true; }}}}} returner hBase; } privat int checkColumnConstraint (boolsk [] [] coverBoard, int hBase) {for (int kolonne = COVER_START_INDEX; kolonne <= BOARD_SIZE; c ++) {for (int n = COVER_START_INDEX; n <= BOARD_SIZE; n ++, hBase ++) {for ( int rad = COVER_START_INDEX; rad <= BOARD_SIZE; rad ++) {int indeks = getIndex (rad, kolonne, n); coverBoard [index] [hBase] = true; }}} returner hBase; } privat int checkRowConstraint (boolsk [] [] coverBoard, int hBase) {for (int rad = COVER_START_INDEX; rad <= BOARD_SIZE; r ++) {for (int n = COVER_START_INDEX; n <= BOARD_SIZE; n ++, hBase ++) {for ( int kolonne = COVER_START_INDEX; kolonne <= BOARD_SIZE; kolonne ++) {int indeks = getIndex (rad, kolonne, n); coverBoard [index] [hBase] = true; }}} returner hBase; } privat int checkCellConstraint (boolsk [] [] coverBoard, int hBase) {for (int rad = COVER_START_INDEX; rad <= BOARD_SIZE; rad ++) {for (int kolonne = COVER_START_INDEX; kolonne <= BOARD_SIZE; kolonne ++, hBase ++) {for ( int n = COVER_START_INDEX; n <= BOARD_SIZE; n ++) {int index = getIndex (rad, kolonne, n); coverBoard [index] [hBase] = true; }}} returner hBase; }

Deretter må vi oppdatere det nyopprettede brettet med vårt første puslespilloppsett:

private boolean [] [] initializeExactCoverBoard (int [] [] board) {boolean [] [] coverBoard = createExactCoverBoard (); for (int rad = COVER_START_INDEX; rad <= BOARD_SIZE; rad ++) {for (int kolonne = COVER_START_INDEX; kolonne <= BOARD_SIZE; kolonne ++) {int n = tavle [rad - 1] [kolonne - 1]; if (n! = NO_VALUE) {for (int num = MIN_VALUE; num <= MAX_VALUE; num ++) {if (num! = n) {Arrays.fill (coverBoard [getIndex (rad, kolonne, num)], false); }}}}} returner coverBoard; }

Vi er klare til å gå videre til neste trinn nå. La oss lage to klasser som vil knytte cellene våre sammen.

4.4. Dancing Node

Dancing Links-algoritmen fungerer på en grunnleggende observasjon at følgende operasjon på dobbeltkoblede lister over noder:

node.prev.next = node.next node.next.prev = node.prev

fjerner noden, mens:

node.prev = node node.next = node

gjenoppretter noden.

Hver node i DLX er knyttet til noden til venstre, høyre, opp og ned.

DancingNode klasse vil ha alle operasjoner som trengs for å legge til eller fjerne noder:

klasse DancingNode {DancingNode L, R, U, D; KolonneNode C; DancingNode hookDown (DancingNode node) {assert (this.C == node.C); node.D = denne.D; node.D.U = node; node.U = dette; this.D = node; retur node; } DancingNode hookRight (DancingNode node) {node.R = this.R; node.R.L = node; node.L = dette; this.R = node; retur node; } ugyldig unlinkLR () {this.L.R = this.R; this.R.L = this.L; } ugyldig relinkLR () {this.L.R = this.R.L = dette; } ugyldig unlinkUD () {this.U.D = this.D; this.D.U = this.U; } ugyldig relinkUD () {this.U.D = this.D.U = this; } DancingNode () {L = R = U = D = dette; } DancingNode (ColumnNode c) {this (); C = c; }}

4.5. Kolonneknute

KolonneNode klasse vil koble kolonner sammen:

klasse ColumnNode utvider DancingNode {int størrelse; Strengnavn; KolonneNode (streng n) {super (); størrelse = 0; navn = n; C = dette; } ugyldig omslag () {unlinkLR (); for (DancingNode i = this.D; i! = this; i = i.D) {for (DancingNode j = i.R; j! = i; j = j.R) {j.unlinkUD (); j.C. størrelse--; }}} ugyldig avdekke () {for (DancingNode i = this.U; i! = this; i = i.U) {for (DancingNode j = i.L; j! = i; j = j.L) {j.C.size ++; j.relinkUD (); }} relinkLR (); }}

4.6. Løser

Deretter må vi lage et rutenett som består av vårt DancingNode og KolonneNode gjenstander:

private ColumnNode makeDLXBoard (boolsk [] [] grid) {int COLS = grid [0] .length; ColumnNode headerNode = ny ColumnNode ("header"); Liste columnNodes = ny ArrayList (); for (int i = 0; i <COLS; i ++) {ColumnNode n = new ColumnNode (Integer.toString (i)); columnNodes.add (n); headerNode = (ColumnNode) headerNode.hookRight (n); } headerNode = headerNode.R.C; for (boolsk [] aGrid: grid) {DancingNode prev = null; for (int j = 0; j <COLS; j ++) {if (aGrid [j]) {ColumnNode col = columnNodes.get (j); DancingNode newNode = ny DancingNode (kol); hvis (prev == null) prev = newNode; col.U.hookDown (newNode); prev = prev.hookRight (newNode); col.størrelse ++; }}} headerNode.size = COLS; return headerNode; }

Vi bruker heuristisk søk ​​for å finne kolonner og returnere et delsett av matrisen:

private ColumnNode selectColumnNodeHeuristic () {int min = Integer.MAX_VALUE; ColumnNode ret = null; for (ColumnNode c = (ColumnNode) header.R; c! = header; c = (ColumnNode) c.R) {if (c.størrelse <min) {min = c.størrelse; ret = c; }} returnere ret; }

Til slutt kan vi rekursivt søke etter svaret:

privat tomt søk (int k) {if (header.R == header) {handleSolution (svar); } annet {ColumnNode c = selectColumnNodeHeuristic (); c.cover (); for (DancingNode r = c.D; r! = c; r = r.D) {answer.add (r); for (DancingNode j = r.R; j! = r; j = j.R) {j.C.cover (); } søk (k + 1); r = svar. fjern (svar.størrelse () - 1); c = r.C; for (DancingNode j = r.L; j! = r; j = j.L) {j.C.uncover (); }} c.uncover (); }}

Hvis det ikke er flere kolonner, kan vi skrive ut det løste Sudoku-kortet.

5. Referanser

Vi kan sammenligne de to forskjellige algoritmene ved å kjøre dem på samme datamaskin (på denne måten kan vi unngå forskjeller i komponenter, hastigheten på CPU eller RAM, etc.). De faktiske tidene vil variere fra datamaskin til datamaskin.

Vi skal imidlertid kunne se relative resultater, og dette vil fortelle oss hvilken algoritme som går raskere.

Backtracking-algoritmen tar rundt 250 ms å løse brettet.

Hvis vi sammenligner dette med Dancing Links, som tar rundt 50 ms, kan vi se en klar vinner. Dancing Links er omtrent fem ganger raskere når du løser dette eksemplet.

6. Konklusjon

I denne opplæringen har vi diskutert to løsninger på et sudoku-puslespill med Java-kjerne. Backtracking-algoritmen, som er en brute-force-algoritme, kan enkelt løse standard 9 × 9-puslespillet.

Den litt mer kompliserte Dancing Links-algoritmen har også blitt diskutert. Begge løser de vanskeligste oppgavene på få sekunder.

Til slutt, som alltid, finner du koden som ble brukt under diskusjonen på GitHub.