Maak een Sudoku-oplosser in Java

1. Overzicht

In dit artikel gaan we kijken naar de Sudoku-puzzel en algoritmen die worden gebruikt om deze op te lossen.

Vervolgens implementeren we oplossingen in Java. De eerste oplossing is een simpele aanval met brute kracht. De tweede maakt gebruik van de Dancing Links-techniek.

Laten we in gedachten houden dat we ons concentreren op de algoritmen en niet op het OOP-ontwerp.

2. De Sudoku-puzzel

Simpel gezegd, Sudoku is een combinatorische nummerplaatsingspuzzel met 9 x 9 cellenraster gedeeltelijk gevuld met cijfers van 1 tot 9. Het doel is om de resterende, lege velden te vullen met de rest van de cijfers, zodat elke rij en kolom er maar één heeft. aantal van elke soort.

Wat meer is, elke 3 x 3 subsectie van het raster kan ook geen nummer gedupliceerd hebben. De moeilijkheidsgraad stijgt natuurlijk met het aantal lege velden op elk bord.

2.1. Testbord

Om onze oplossing interessanter te maken en het algoritme te valideren, gaan we het "moeilijkste sudoku ter wereld" -bord gebruiken, namelijk:

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

2.2. Opgelost bord

En om de oplossing snel te bederven - de correct opgeloste puzzel geeft ons het volgende resultaat:

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. Invoering

Backtracking-algoritme probeert de puzzel op te lossen door elke cel te testen op een geldige oplossing.

Als er geen overtreding van beperkingen is, gaat het algoritme naar de volgende cel, vult het alle mogelijke oplossingen in en herhaalt het alle controles.

Als er een overtreding is, wordt de celwaarde verhoogd. Eens bereikt de waarde van de cel 9, en er is nog steeds een overtreding, dan gaat het algoritme terug naar de vorige cel en verhoogt het de waarde van die cel.

Het probeert alle mogelijke oplossingen.

3.2. Oplossing

Laten we allereerst ons bord definiëren als een tweedimensionale reeks gehele getallen. We gebruiken 0 als onze lege cel.

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}};

Laten we een oplossen() methode die de bord als de invoerparameter en itereert door rijen, kolommen en waarden om elke cel te testen op een geldige oplossing:

private boolean solution (int [] [] board) {for (int row = BOARD_START_INDEX; row <BOARD_SIZE; row ++) {for (int column = BOARD_START_INDEX; column <BOARD_SIZE; column ++) {if (board [row] [column] = = NO_VALUE) {voor (int k = MIN_VALUE; k <= MAX_VALUE; k ++) {board [rij] [kolom] = k; if (isValid (bord, rij, kolom) && oplossen (bord)) {return true; } bord [rij] [kolom] = NO_VALUE; } return false; }}} retourneert waar; }

Een andere methode die we nodig hadden, is is geldig() methode, die Sudoku-beperkingen gaat controleren, d.w.z. controleer of de rij, kolom en 3 x 3 raster geldig zijn:

private boolean isValid (int [] [] board, int row, int column) {return (rowConstraint (board, row) && columnConstraint (board, column) && subsectionConstraint (board, row, column)); }

Deze drie controles zijn relatief vergelijkbaar. Laten we eerst beginnen met rijcontroles:

private boolean rowConstraint (int [] [] board, int row) {boolean [] constraint = nieuwe boolean [BOARD_SIZE]; retourneer IntStream.range (BOARD_START_INDEX, BOARD_SIZE) .allMatch (kolom -> checkConstraint (bord, rij, beperking, kolom)); }

Vervolgens gebruiken we bijna identieke code om de kolom te valideren:

private boolean columnConstraint (int [] [] board, int column) {boolean [] constraint = nieuwe boolean [BOARD_SIZE]; retourneer IntStream.range (BOARD_START_INDEX, BOARD_SIZE) .allMatch (rij -> checkConstraint (bord, rij, beperking, kolom)); }

Verder moeten we 3 x 3 subsectie valideren:

private boolean subsectionConstraint (int [] [] board, int row, int column) {boolean [] constraint = new boolean [BOARD_SIZE]; int subsectionRowStart = (rij / SUBSECTION_SIZE) * SUBSECTION_SIZE; int subsectionRowEnd = subsectionRowStart + SUBSECTION_SIZE; int subsectionColumnStart = (kolom / 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; }} retourneren waar; }

Ten slotte hebben we een checkConstraint () methode:

boolean checkConstraint (int [] [] board, int row, boolean [] constraint, int column) {if (board [row] [column]! = NO_VALUE) {if (! constraint [board [row] [column] - 1 ]) {beperking [bord [rij] [kolom] - 1] = waar; } else {return false; }} retourneren waar; }

Eens is dat allemaal gebeurd is geldig() methode kan gewoon terugkeren waar.

We zijn nu bijna klaar om de oplossing te testen. Het algoritme is klaar. Het keert echter terug waar of false enkel en alleen.

Om het bord visueel te controleren, hoeven we daarom alleen het resultaat af te drukken. Blijkbaar maakt dit geen deel uit van het algoritme.

private void printBoard () {for (int row = BOARD_START_INDEX; row <BOARD_SIZE; row ++) {for (int column = BOARD_START_INDEX; column <BOARD_SIZE; column ++) {System.out.print (board [row] [column] + "" ); } System.out.println (); }}

We hebben met succes een backtracking-algoritme geïmplementeerd dat de Sudoku-puzzel oplost!

Het is duidelijk dat er ruimte is voor verbeteringen, aangezien het algoritme elke mogelijke combinatie naïef keer op keer controleert (ook al weten we dat de specifieke oplossing ongeldig is).

4. Dansende koppelingen

4.1. Exacte dekking

Laten we naar een andere oplossing kijken. Sudoku kan worden omschreven als een Exact Cover-probleem, dat kan worden weergegeven door een incidentie-matrix die de relatie tussen twee objecten laat zien.

Als we bijvoorbeeld nummers van 1 tot 7 nemen en de verzameling sets S = {A, B, C, D, E, F}, waar:

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

Ons doel is om zulke subsets te selecteren dat elk nummer er maar één keer is en geen enkele wordt herhaald, vandaar de naam.

We kunnen het probleem weergeven met behulp van een matrix, waarin kolommen getallen zijn en rijen sets:

 | 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 |

Deelcollectie S * = {B, D, F} is de exacte 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 |

Elke kolom heeft precies één 1 in alle geselecteerde rijen.

4.2. Algoritme X

Algoritme X is een "Trial-and-error-aanpak" om alle oplossingen voor het exacte dekkingsprobleem te vinden, d.w.z. te beginnen met onze voorbeeldcollectie S = {A, B, C, D, E, F}, vind subcollectie S * = {B, D, F}.

Algoritme X werkt als volgt:

  1. Als de matrix EEN heeft geen kolommen, de huidige deeloplossing is een geldige oplossing;

    succesvol beëindigen, kies anders een kolom c (deterministisch)

  2. Kies een rij r zoals dat EENr, c = 1 (niet-deterministisch, d.w.z. probeer alle mogelijkheden)
  3. Rij opnemen r in de gedeeltelijke oplossing
  4. Voor elke kolom j zoals dat EENr, j = 1, voor elke rij ik zoals dat EENik, j = 1,

    Verwijder rij ik van matrix EEN enkolom verwijderen j van matrix EEN

  5. Herhaal dit algoritme recursief op de verkleinde matrix EEN

Een efficiënte implementatie van het algoritme X is het algoritme Dancing Links (afgekort DLX), voorgesteld door Dr. Donald Knuth.

De volgende oplossing is sterk geïnspireerd door deze Java-implementatie.

4.3. Exact Coverprobleem

Eerst moeten we een matrix maken die de Sudoku-puzzel voorstelt als een Exact Cover-probleem. De matrix heeft 9 ^ 3 rijen, d.w.z. één rij voor elke mogelijke positie (9 rijen x 9 kolommen) van elk mogelijk nummer (9 cijfers).

Kolommen vertegenwoordigen het bord (weer 9 x 9) vermenigvuldigd met het aantal beperkingen.

We hebben al drie beperkingen gedefinieerd:

  • elke rij heeft slechts één nummer van elke soort
  • elke kolom heeft slechts één nummer van elke soort
  • elke onderafdeling heeft slechts één nummer van elke soort

Bovendien is er een impliciete vierde beperking:

  • er kan slechts één nummer in een cel staan

Dit geeft in totaal vier beperkingen en dus 9 x 9 x 4 kolommen in de Exact Cover-matrix:

privé statische int BOARD_SIZE = 9; privé statische int SUBSECTION_SIZE = 3; privé statische int NO_VALUE = 0; privé statische int BEPERKINGEN = 4; privé statische int MIN_VALUE = 1; privé statische int MAX_VALUE = 9; privé statische int COVER_START_INDEX = 1;
private int getIndex (int rij, int kolom, int num) {return (rij - 1) * BOARD_SIZE * BOARD_SIZE + (kolom - 1) * BOARD_SIZE + (num - 1); }
private boolean [] [] createExactCoverBoard () {boolean [] [] coverBoard = nieuwe boolean [BOARD_SIZE * BOARD_SIZE * MAX_VALUE] [BOARD_SIZE * BOARD_SIZE * BEPERKINGEN]; int hBase = 0; hBase = checkCellConstraint (coverBoard, hBase); hBase = checkRowConstraint (coverBoard, hBase); hBase = checkColumnConstraint (coverBoard, hBase); checkSubsectionConstraint (coverBoard, hBase); terugkeer omslagBord; } private int checkSubsectionConstraint (boolean [] [] coverBoard, int hBase) {for (int row = COVER_START_INDEX; rij <= BOARD_SIZE; rij + = SUBSECTION_SIZE) {voor (int column = COVER_START_INDEX; kolom <= BOARD_SIZE; kolom <= BOARD_SIZE; kolom <= BOARD_SIZE; kolom <= BOARD_SIZE; kolom <= BOARD_SIZE; kolom ) {for (int n = COVER_START_INDEX; n <= BOARD_SIZE; n ++, hBase ++) {for (int rowDelta = 0; rowDelta <SUBSECTION_SIZE; rowDelta ++) {voor (int columnDelta = 0; columnDelta <SUBSECTION_SIZE; columnDelta ++) {int index = getIndex (rij + rijDelta, kolom + kolomDelta, n); coverBoard [index] [hBase] = waar; }}}}} retourneer hBase; } private int checkColumnConstraint (boolean [] [] coverBoard, int hBase) {for (int column = COVER_START_INDEX; column <= BOARD_SIZE; c ++) {for (int n = COVER_START_INDEX; n <= BOARD_SIZE; n ++, hBase ++) {voor ( int row = COVER_START_INDEX; rij <= BOARD_SIZE; rij ++) {int index = getIndex (rij, kolom, n); coverBoard [index] [hBase] = waar; }}} retourneer hBase; } private int checkRowConstraint (boolean [] [] coverBoard, int hBase) {for (int row = COVER_START_INDEX; row <= BOARD_SIZE; r ++) {for (int n = COVER_START_INDEX; n <= BOARD_SIZE; n ++, hBase ++) {voor ( int column = COVER_START_INDEX; column <= BOARD_SIZE; column ++) {int index = getIndex (rij, kolom, n); coverBoard [index] [hBase] = waar; }}} retourneer hBase; } private int checkCellConstraint (boolean [] [] coverBoard, int hBase) {for (int row = COVER_START_INDEX; row <= BOARD_SIZE; row ++) {for (int column = COVER_START_INDEX; column <= BOARD_SIZE; column ++, hBase ++) {for ( int n = COVER_START_INDEX; n <= BOARD_SIZE; n ++) {int index = getIndex (rij, kolom, n); coverBoard [index] [hBase] = waar; }}} retourneer hBase; }

Vervolgens moeten we het nieuw gemaakte bord bijwerken met onze oorspronkelijke puzzellay-out:

private boolean [] [] initializeExactCoverBoard (int [] [] board) {boolean [] [] coverBoard = createExactCoverBoard (); for (int row = COVER_START_INDEX; row <= BOARD_SIZE; row ++) {for (int column = COVER_START_INDEX; column <= BOARD_SIZE; column ++) {int n = board [row - 1] [column - 1]; if (n! = NO_VALUE) {for (int num = MIN_VALUE; num <= MAX_VALUE; num ++) {if (num! = n) {Arrays.fill (coverBoard [getIndex (rij, kolom, num)], false); }}}}} geef coverBoard terug; }

We zijn nu klaar om naar de volgende fase te gaan. Laten we twee klassen maken die onze cellen met elkaar verbinden.

4.4. Dansende knoop

Het Dancing Links-algoritme werkt op basis van de basiswaarneming dat de volgende bewerking op dubbel gekoppelde lijsten met knooppunten:

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

verwijdert het knooppunt, terwijl:

node.prev = knooppunt knooppunt.next = knooppunt

herstelt het knooppunt.

Elk knooppunt in DLX is gekoppeld aan het knooppunt links, rechts, omhoog en omlaag.

DancingNode class heeft alle bewerkingen die nodig zijn om knooppunten toe te voegen of te verwijderen:

klasse DancingNode {DancingNode L, R, U, D; ColumnNode C; DancingNode hookDown (DancingNode node) {assert (this.C == node.C); knooppunt.D = this.D; node.D.U = knooppunt; node.U = dit; this.D = knooppunt; terugkeerknooppunt; } DancingNode hookRight (DancingNode-knooppunt) {node.R = this.R; node.R.L = knooppunt; node.L = dit; this.R = knooppunt; terugkeerknooppunt; } void unlinkLR () {this.L.R = this.R; this.R.L = this.L; } void relinkLR () {this.L.R = this.R.L = this; } void unlinkUD () {this.U.D = this.D; this.D.U = this.U; } void relinkUD () {this.U.D = this.D.U = this; } DancingNode () {L = R = U = D = dit; } DancingNode (ColumnNode c) {this (); C = c; }}

4.5. Kolomknooppunt

ColumnNode class zal kolommen aan elkaar koppelen:

klasse ColumnNode breidt DancingNode {int size; String naam; ColumnNode (String n) {super (); maat = 0; naam = n; C = dit; } void cover () {unlinkLR (); voor (DancingNode i = this.D; i! = this; i = i.D) {voor (DancingNode j = i.R; j! = i; j = j.R) {j.unlinkUD (); j.C. maat--; }}} void uncover () {voor (DancingNode i = this.U; i! = this; i = i.U) {voor (DancingNode j = i.L; j! = i; j = j.L) {j.C.size ++; j.relinkUD (); }} relinkLR (); }}

4.6. Oplosser

Vervolgens moeten we een raster maken dat bestaat uit ons DancingNode en ColumnNode voorwerpen:

private ColumnNode makeDLXBoard (boolean [] [] grid) {int COLS = grid [0] .length; ColumnNode headerNode = nieuwe ColumnNode ("header"); Lijst columnNodes = nieuwe ArrayList (); for (int i = 0; i <COLS; i ++) {ColumnNode n = nieuwe ColumnNode (Integer.toString (i)); columnNodes.add (n); headerNode = (ColumnNode) headerNode.hookRight (n); } headerNode = headerNode.R.C; voor (boolean [] aGrid: grid) {DancingNode prev = null; voor (int j = 0; j <COLS; j ++) {if (aGrid [j]) {ColumnNode col = columnNodes.get (j); DancingNode newNode = nieuwe DancingNode (col); if (prev == null) prev = newNode; col.U.hookDown (newNode); prev = prev.hookRight (newNode); col.size ++; }}} headerNode.size = COLS; retourneer headerNode; }

We zullen heuristisch zoeken gebruiken om kolommen te vinden en een subset van de matrix te retourneren:

privé ColumnNode selectColumnNodeHeuristic () {int min = Integer.MAX_VALUE; ColumnNode ret = null; voor (ColumnNode c = (ColumnNode) header.R; c! = header; c = (ColumnNode) c.R) {if (c.size <min) {min = c.size; ret = c; }} retourneren; }

Ten slotte kunnen we recursief zoeken naar het antwoord:

privé ongeldig zoeken (int k) {if (header.R == header) {handleSolution (antwoord); } anders {ColumnNode c = selectColumnNodeHeuristic (); c.cover (); voor (DancingNode r = c.D; r! = c; r = r.D) {answer.add (r); voor (DancingNode j = r.R; j! = r; j = j.R) {j.C.cover (); } zoeken (k + 1); r = answer.remove (answer.size () - 1); c = r.C; voor (DancingNode j = r.L; j! = r; j = j.L) {j.C.uncover (); }} c.uncover (); }}

Als er geen kolommen meer zijn, kunnen we het opgeloste Sudoku-bord afdrukken.

5. Benchmarks

We kunnen die twee verschillende algoritmen vergelijken door ze op dezelfde computer uit te voeren (op deze manier kunnen we verschillen in componenten, de snelheid van CPU of RAM, enz. Vermijden). De daadwerkelijke tijden zullen van computer tot computer verschillen.

We zouden echter relatieve resultaten moeten kunnen zien, en dit zal ons vertellen welk algoritme sneller werkt.

Het Backtracking-algoritme duurt ongeveer 250 ms om het bord op te lossen.

Als we dit vergelijken met de Dancing Links, die ongeveer 50 ms duurt, kunnen we een duidelijke winnaar zien. Dancing Links is ongeveer vijf keer sneller bij het oplossen van dit specifieke voorbeeld.

6. Conclusie

In deze tutorial hebben we twee oplossingen voor een sudoku-puzzel met core Java besproken. Het backtracking-algoritme, een brute-force-algoritme, kan de standaard 9 × 9-puzzel gemakkelijk oplossen.

Het iets meer gecompliceerde Dancing Links-algoritme is ook besproken. Beiden lossen de moeilijkste puzzels binnen enkele seconden op.

Eindelijk, zoals altijd, is de code die tijdens de discussie is gebruikt, te vinden op GitHub.


Populaire Berichten

recente berichten

Copyright streamalism.org 2024
$config[zx-auto] not found$config[zx-overlay] not found