Opret en Sudoku Solver i Java
1. Oversigt
I denne artikel skal vi se på Sudoku-puslespil og algoritmer, der bruges til at løse det.
Dernæst implementerer vi løsninger i Java. Den første løsning vil være et simpelt brute-force angreb. Den anden bruger Dancing Links-teknikken.
Lad os huske på, at fokus vi fokuserer på algoritmerne og ikke på OOP-designet.
2. Sudoku Puzzle
Kort sagt, Sudoku er et kombinatorisk nummerplaceringspuslespil med 9 x 9 cellegitter delvist udfyldt med tal fra 1 til 9. Målet er at udfylde resterende, tomme felter med resten af numre, så hver række og kolonne kun har en nummer af hver art.
Hvad mere er, hver 3 x 3 underafsnit af nettet kan ikke have noget nummer også duplikeret. Sværhedsgraden stiger naturligvis med antallet af tomme felter i hvert bræt.
2.1. Test Board
For at gøre vores løsning mere interessant og validere algoritmen skal vi bruge "verdens hårdeste 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 bestyrelse
Og for at ødelægge løsningen hurtigt - det korrekt løste puslespil giver os 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 23. Backtracking algoritme
3.1. Introduktion
Backtracking-algoritme forsøger at løse gåden ved at teste hver celle for en gyldig løsning.
Hvis der ikke er nogen overtrædelse af begrænsninger, flyttes algoritmen til den næste celle, udfylder alle mulige løsninger og gentager alle kontroller.
Hvis der er en overtrædelse, øges det celleværdien. Én gang når celleværdien 9, og der er stadig en overtrædelse, så bevæger algoritmen sig tilbage til den forrige celle og øger værdien af den celle.
Den prøver alle mulige løsninger.
3.2. Opløsning
Lad os først og fremmest definere vores tavle som et todimensionelt array af heltal. Vi bruger 0 som vores tomme celle.
int [] [] bord = {{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}};Lad os oprette en løse() metode, der tager bestyrelse som inputparameter og gentages gennem rækker, kolonner og værdier, der tester hver celle for en gyldig løsning:
privat boolsk løs (int [] [] bord) {for (int række = BOARD_START_INDEX; række <BOARD_SIZE; række ++) {for (int kolonne = BOARD_START_INDEX; kolonne <BOARD_SIZE; kolonne ++) {hvis (bord [række] [kolonne] = = NO_VALUE) {for (int k = MIN_VALUE; k <= MAX_VALUE; k ++) {board [række] [kolonne] = k; hvis (isValid (bord, række, kolonne) && løse (bord)) {returner sand; } bord [række] [kolonne] = NO_VALUE; } returner falsk; }}} returner sandt; }En anden metode, som vi havde brug for, er er gyldig() metode, som skal kontrollere Sudoku-begrænsninger, dvs. kontrollere, om rækken, kolonnen og 3 x 3-gitteret er gyldige:
privat boolsk isValid (int [] [] tavle, int række, int kolonne) {return (rækkeConstraint (bord, række) && columnConstraint (bord, kolonne) && underafsnitConstraint (bord, række, kolonne)) }Disse tre kontroller er relativt ens. Lad os først starte med rækkekontrol:
privat boolsk rækkeConstraint (int [] [] board, int row) {boolean [] constraint = new boolean [BOARD_SIZE]; returnere IntStream.range (BOARD_START_INDEX, BOARD_SIZE) .allMatch (kolonne -> checkConstraint (bord, række, begrænsning, kolonne)); }Dernæst bruger vi næsten identisk kode til at validere kolonne:
privat boolsk columnConstraint (int [] [] board, int column) {boolean [] constraint = new boolean [BOARD_SIZE]; returner IntStream.range (BOARD_START_INDEX, BOARD_SIZE) .allMatch (række -> checkConstraint (bord, række, begrænsning, kolonne)); }Desuden er vi nødt til at validere 3 x 3 underafsnit:
privat boolsk underafsnitConstraint (int [] [] board, int row, int column) {boolean [] constraint = new boolean [BOARD_SIZE]; int subsectionRowStart = (række / 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)) returner false; }} returner sandt; }Endelig har vi brug for en checkConstraint () metode:
boolsk checkConstraint (int [] [] bord, int række, boolsk [] begrænsning, int kolonne) {if (bord [række] [kolonne]! = NO_VALUE) {hvis (! begrænsning [bord [række] [kolonne] - 1 ]) {begrænsning [bord [række] [kolonne] - 1] = sand; } andet {returner falsk; }} returner sandt; }Én gang er alt det gjort er gyldig() metode kan simpelthen vende tilbage rigtigt.
Vi er næsten klar til at teste løsningen nu. Algoritmen er færdig. Det vender imidlertid tilbage rigtigt eller falsk kun.
Derfor skal vi visuelt kontrollere tavlen, bare for at udskrive resultatet. Tilsyneladende er dette ikke en del af algoritmen.
privat ugyldigt printBoard () {for (int række = BOARD_START_INDEX; række <BOARD_SIZE; række ++) {for (int kolonne = BOARD_START_INDEX; kolonne <BOARD_SIZE; kolonne ++) {System.out.print (bord [række] [kolonne] + "" ); } System.out.println (); }}Vi har med succes implementeret backtracking-algoritme, der løser Sudoku-puslespillet!
Der er åbenbart plads til forbedringer, da algoritmen naivt kontrollerer hver mulige kombination igen og igen (selvom vi ved, at den særlige løsning er ugyldig).
4. Dansende links
4.1. Præcis dækning
Lad os se på en anden løsning. Sudoku kan beskrives som et nøjagtigt dækningsproblem, som kan repræsenteres ved incidensmatrix, der viser forholdet mellem to objekter.
For eksempel, hvis vi tager tal fra 1 til 7 og samlingen af sæt 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}
Vores mål er at vælge sådanne undersæt, at hvert nummer kun er der en gang, og ingen gentages, deraf navnet.
Vi kan repræsentere problemet ved hjælp af en matrix, hvor kolonner er tal og rækker er sæt:
| 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 |Underindsamling S * = {B, D, F} er nøjagtig 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øjagtigt en 1 i alle valgte rækker.
4.2. Algoritme X
Algoritme X er en “Prøve-og-fejl tilgang” for at finde alle løsninger på det nøjagtige dækningsproblem, dvs. starte med vores eksempler på samling S = {A, B, C, D, E, F}, find underindsamling S * = {B, D, F}.
Algoritme X fungerer som følger:
- Hvis matrixen EN har ingen kolonner, den aktuelle delvise løsning er en gyldig løsning;
afslut med succes, ellers skal du vælge en kolonne c (deterministisk)
- Vælg en række r sådan at ENr, c = 1 (ikke-bestemmende, dvs. prøv alle muligheder)
- Inkluder række r i delopløsningen
- For hver kolonne j sådan at ENr, j = 1, for hver række jeg sådan at ENjeg, j = 1,
slet række jeg fra matrix EN ogslet kolonne j fra matrix EN
- Gentag denne algoritme rekursivt på den reducerede matrix EN
En effektiv implementering af Algorithm X er Dancing Links algoritme (forkortet DLX) foreslået af Dr. Donald Knuth.
Følgende løsning er stærkt inspireret af denne Java-implementering.
4.3. Præcis dækningsproblem
Først skal vi oprette en matrix, der repræsenterer Sudoku-puslespil som et nøjagtigt dækningsproblem. Matrixen vil have 9 ^ 3 rækker, dvs. en række for hver enkelt mulige position (9 rækker x 9 kolonner) af hvert mulige tal (9 tal).
Kolonner repræsenterer tavlen (igen 9 x 9) ganget med antallet af begrænsninger.
Vi har allerede defineret tre begrænsninger:
- hver række vil kun have et nummer af hver slags
- hver kolonne vil kun have et nummer af hver art
- hvert underafsnit vil kun have et nummer af hver art
Derudover er der implicit fjerde begrænsning:
- kun et nummer kan være i en celle
Dette giver fire begrænsninger i alt og derfor 9 x 9 x 4 kolonner i Matrixen med eksakt omslag:
privat statisk int BOARD_SIZE = 9; privat statisk int SUBSECTION_SIZE = 3; privat statisk int NO_VALUE = 0; privat statisk 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 række, int kolonne, int num) {return (række - 1) * BOARD_SIZE * BOARD_SIZE + (kolonne - 1) * BOARD_SIZE + (num - 1); }privat boolsk [] [] createExactCoverBoard () {boolean [] [] 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); returner omslagBord; } privat int checkSubsectionConstraint (boolsk [] [] coverBoard, int hBase) {for (int række = COVER_START_INDEX; række <= BOARD_SIZE; række + = 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 (række + rækkeDelta, kolonne + kolonneDelta, n); coverBoard [index] [hBase] = sand; }}}}} 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 række = COVER_START_INDEX; række <= BOARD_SIZE; række ++) {int indeks = getIndex (række, kolonne, n); coverBoard [index] [hBase] = sand; }}} returner hBase; } privat int checkRowConstraint (boolsk [] [] coverBoard, int hBase) {for (int række = COVER_START_INDEX; række <= 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 (række, kolonne, n); coverBoard [index] [hBase] = sand; }}} returner hBase; } privat int checkCellConstraint (boolsk [] [] coverBoard, int hBase) {for (int række = COVER_START_INDEX; række <= BOARD_SIZE; række ++) {for (int kolonne = COVER_START_INDEX; kolonne <= BOARD_SIZE; kolonne ++, hBase ++) {for ( int n = COVER_START_INDEX; n <= BOARD_SIZE; n ++) {int index = getIndex (række, kolonne, n); coverBoard [index] [hBase] = sand; }}} returner hBase; }Dernæst skal vi opdatere det nyoprettede bord med vores oprindelige puslespillayout:
privat boolsk [] [] initializeExactCoverBoard (int [] [] board) {boolean [] [] coverBoard = createExactCoverBoard (); for (int række = COVER_START_INDEX; række <= BOARD_SIZE; række ++) {for (int kolonne = COVER_START_INDEX; kolonne <= BOARD_SIZE; kolonne ++) {int n = bord [række - 1] [kolonne - 1]; hvis (n! = NO_VALUE) {for (int num = MIN_VALUE; num <= MAX_VALUE; num ++) {hvis (num! = n) {Arrays.fill (coverBoard [getIndex (række, kolonne, num)], falsk); }}}}} returner coverBoard; }Vi er klar til at gå videre til næste fase nu. Lad os oprette to klasser, der forbinder vores celler sammen.
4.4. Dansende knude
Dancing Links algoritme fungerer på en grundlæggende observation, at efter operation på dobbeltkoblede lister over noder:
node.prev.next = node.next node.next.prev = node.prevfjerner noden, mens:
node.prev = node node.next = nodegendanner noden.
Hver node i DLX er knyttet til noden til venstre, højre, op og ned.
DancingNode klasse har alle de operationer, der er nødvendige for at tilføje 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; returknude } DancingNode hookRight (DancingNode node) {node.R = this.R; node.R.L = node; node.L = dette; this.R = node; returknude } ugyldig unlinkLR () {this.L.R = this.R; this.R.L = this.L; } ugyldigt relinkLR () {this.L.R = this.R.L = dette; } ugyldig unlinkUD () {this.U.D = this.D; this.D.U = this.U; } ugyldigt relinkUD () {this.U.D = this.D.U = this; } DancingNode () {L = R = U = D = dette; } DancingNode (ColumnNode c) {dette (); C = c; }}4.5. Kolonneknude
KolonneNode klasse vil linke kolonner sammen:
klasse ColumnNode udvider DancingNode {int størrelse; Strengnavn; ColumnNode (streng n) {super (); størrelse = 0; navn = n; C = dette; } ugyldigt 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--; }}} ugyldigt afdækning () {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
Dernæst skal vi oprette et gitter bestående af vores DancingNode og KolonneNode genstande:
privat ColumnNode makeDLXBoard (boolsk [] [] gitter) {int COLS = gitter [0] .længde; 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 (col); hvis (prev == null) prev = newNode; col.U.hookDown (newNode); prev = prev.hookRight (newNode); col.størrelse ++; }}} headerNode.size = COLS; return headerNode; }Vi bruger heuristisk søgning til at finde kolonner og returnere et undersæt af matrixen:
privat 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; }Endelig kan vi rekursivt søge efter svaret:
privat ugyldig søgning (int k) {if (header.R == header) {handleSolution (svar); } andet {ColumnNode c = selectColumnNodeHeuristic (); c. dække (); for (DancingNode r = c.D; r! = c; r = r.D) {answer.add (r); til (DancingNode j = r.R; j! = r; j = j.R) {j.C.cover (); } søg (k + 1); r = svar. fjern (svar.størrelse () - 1); c = r.C; til (DancingNode j = r.L; j! = r; j = j.L) {j.C.uncover (); }} c.uncover (); }}Hvis der ikke er flere kolonner, kan vi udskrive det løste Sudoku-kort.
5. Benchmarks
Vi kan sammenligne disse to forskellige algoritmer ved at køre dem på den samme computer (på denne måde kan vi undgå forskelle i komponenter, hastigheden på CPU eller RAM osv.). De faktiske tidspunkter vil variere fra computer til computer.
Vi skal dog kunne se relative resultater, og dette vil fortælle os, hvilken algoritme der kører hurtigere.
Backtracking-algoritmen tager cirka 250 ms at løse brættet.
Hvis vi sammenligner dette med Dancing Links, der tager omkring 50 ms, kan vi se en klar vinder. Dancing Links er omkring fem gange hurtigere, når man løser dette særlige eksempel.
6. Konklusion
I denne vejledning har vi diskuteret to løsninger til et sudoku-puslespil med kernen Java. Backtracking-algoritmen, som er en brute-force-algoritme, kan nemt løse standard 9 × 9-puslespillet.
Den lidt mere komplicerede Dancing Links-algoritme er også blevet diskuteret. Begge løser de hårdeste gåder inden for få sekunder.
Endelig, som altid, kan koden, der blev brugt under diskussionen, findes på GitHub.
