Stvorite Sudoku Solver u Javi

1. Pregled

U ovom ćemo članku pogledati Sudoku zagonetku i algoritme koji se koriste za njezino rješavanje.

Dalje ćemo implementirati rješenja na Javi. Prvo rješenje bit će jednostavan grubi napad. Drugi će koristiti tehniku ​​Plesne veze.

Imajmo na umu da ćemo se fokusirati na algoritme, a ne na dizajn OOP-a.

2. Sudoku slagalica

Jednostavno rečeno, Sudoku je kombinacijska slagalica za postavljanje brojeva s mrežom ćelija 9 x 9, djelomično ispunjenom brojevima od 1 do 9. Cilj je ispuniti preostala, prazna polja ostatkom brojeva, tako da će svaki redak i stupac imati samo jedan broj svake vrste.

Štoviše, svaki 3 x 3 pododjeljak mreže ne može imati dupliciran broj. Razina težine prirodno raste s brojem praznih polja na svakoj ploči.

2.1. Ispitna ploča

Da bismo učinili naše rješenje zanimljivijim i potvrdili algoritam, koristit ćemo ploču "najteži sudoku na svijetu", a to je:

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

2.2. Riješena ploča

A da bismo brzo pokvarili rješenje - pravilno riješena zagonetka dat će nam sljedeći rezultat:

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. Algoritam povratka unatrag

3.1. Uvod

Algoritam vraćanja unazad pokušava riješiti zagonetku testiranjem svake stanice na valjano rješenje.

Ako nema kršenja ograničenja, algoritam se premješta u sljedeću ćeliju, ispunjava sva potencijalna rješenja i ponavlja sve provjere.

Ako postoji kršenje, to povećava vrijednost ćelije. Jednom, vrijednost ćelije dosegne 9, i dalje postoji kršenje, tada se algoritam vraća na prethodnu ćeliju i povećava vrijednost te ćelije.

Pokušava sva moguća rješenja.

3.2. Riješenje

Prije svega, definirajmo našu ploču kao dvodimenzionalni niz cijelih brojeva. Upotrijebit ćemo 0 kao našu praznu ćeliju.

int [] [] ploča = {{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}};

Stvorimo a riješiti() metoda koja uzima odbor kao ulazni parametar i ponavlja se kroz retke, stupce i vrijednosti testirajući svaku ćeliju na valjano rješenje:

privatno logičko rješenje (int [] [] ploča) {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) {for (int k = MIN_VALUE; k <= MAX_VALUE; k ++) {ploča [redak] [stupac] = k; if (isValid (ploča, redak, stupac) && riješi (ploča)) {return true; } ploča [redak] [stupac] = NO_VALUE; } return false; }}} return true; }

Još jedna metoda koja nam je trebala je isValid () metoda koja će provjeriti Sudoku ograničenja, tj. provjeriti jesu li redak, stupac i mreža 3 x 3 valjani:

private boolean isValid (int [] [] ploča, int redak, int stupac) {return (rowConstraint (ploča, red) && columnConstraint (ploča, stupac) && subsectionConstraint (ploča, redak, stupac)); }

Te su tri provjere relativno slične. Prvo, krenimo s provjerama redaka:

privatni logički rowConstraint (int [] [] ploča, int redak) {boolean [] ograničenje = novo logičko [BOARD_SIZE]; vratiti IntStream.range (BOARD_START_INDEX, BOARD_SIZE) .allMatch (stupac -> checkConstraint (ploča, redak, ograničenje, stupac)); }

Dalje koristimo gotovo identičan kod za provjeru stupca:

privatni logički stupConstraint (int [] [] ploča, int stupac) {boolean [] ograničenje = novo logičko [BOARD_SIZE]; vratiti IntStream.range (BOARD_START_INDEX, BOARD_SIZE) .allMatch (redak -> checkConstraint (ploča, redak, ograničenje, stupac)); }

Nadalje, moramo potvrditi pododjeljak 3 x 3:

privatno boolean subsectionConstraint (int [] [] ploča, int redak, int stupac) {boolean [] ograničenje = novo boolean [BOARD_SIZE]; int subsectionRowStart = (red / SUBSECTION_SIZE) * SUBSECTION_SIZE; int subsectionRowEnd = subsectionRowStart + SUBSECTION_SIZE; int subsectionColumnStart = (stupac / 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; }} return true; }

Napokon, trebamo a checkConstraint () metoda:

logička checkConstraint (int [] [] ploča, int redak, boolean [] ograničenje, int stupac) {if (ploča [redak] [stupac]! = NO_VALUE) {if (! ograničenje [ploča [red] [stupac] - 1 ]) {ograničenje [ploča [redak] [stupac] - 1] = true; } else {return false; }} return true; }

Jednom je sve to gotovo isValid () metoda može jednostavno vratiti pravi.

Sad smo gotovo spremni testirati rješenje. Algoritam je gotov. Međutim, vraća se pravi ili lažno samo.

Stoga, za vizualnu provjeru ploče trebamo samo ispisati rezultat. Izgleda da ovo nije dio algoritma.

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

Uspješno smo implementirali algoritam za vraćanje unatrag koji rješava zagonetku Sudokua!

Očito je da ima mjesta za poboljšanja jer algoritam uvijek nanovo naivno provjerava svaku moguću kombinaciju (iako znamo da je određeno rješenje nevaljano).

4. Plesne veze

4.1. Točan pokrov

Pogledajmo još jedno rješenje. Sudoku se može opisati kao problem s točnim pokrivačem, koji se može prikazati matricom incidencije koja prikazuje odnos između dva objekta.

Na primjer, ako uzmemo brojeve od 1 do 7 i zbirku skupova S = {A, B, C, D, E, F}, gdje:

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

Cilj nam je odabrati takve podskupine da se svaki broj nalazi samo jednom i nijedan se ne ponovi, pa otuda i naziv.

Problem možemo prikazati pomoću matrice, gdje su stupci brojevi, a retci skupovi:

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

Podzbirka S * = {B, D, F} točno je pokriće:

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

Svaki stupac ima točno jedan 1 u svim odabranim redovima.

4.2. Algoritam X

Algoritam X je a “Pristup pokušajima i pogreškama” kako bismo pronašli sva rješenja za točan problem s naslovnicom, tj. počevši od naše zbirke primjera S = {A, B, C, D, E, F}, pronađite podzbirku S * = {B, D, F}.

Algoritam X djeluje na sljedeći način:

  1. Ako matrica A nema stupaca, trenutno djelomično rješenje je valjano rješenje;

    uspješno prekinuti, u suprotnom odaberite stupac c (deterministički)

  2. Odaberite red r takav da Ar, c = 1 (nedeterministički, tj. Isprobajte sve mogućnosti)
  3. Uključi redak r u djelomičnom rješenju
  4. Za svaki stupac j takav da Ar, j = 1, za svaki redak ja takav da Aja, j = 1,

    izbriši redak ja iz matrice A iizbriši stupac j iz matrice A

  5. Ponovite ovaj algoritam rekurzivno na smanjenoj matrici A

Učinkovita primjena algoritma X je algoritam Dancing Links (skraćeno DLX) koji je predložio dr. Donald Knuth.

Sljedeće je rješenje nadahnuto ovom Java implementacijom.

4.3. Točan problem s naslovnicom

Prvo, moramo stvoriti matricu koja će predstavljati Sudoku zagonetku kao problem s točnim pokrivačem. Matrica će imati 9 ^ 3 retka, tj. Jedan redak za svaki pojedini mogući položaj (9 redaka x 9 stupaca) svakog mogućeg broja (9 brojeva).

Stupci će predstavljati ploču (opet 9 x 9) pomnoženu s brojem ograničenja.

Već smo definirali tri ograničenja:

  • svaki će red imati samo jedan broj svake vrste
  • svaki stupac imat će samo jedan broj svake vrste
  • svaki će pododjeljak imati samo jedan broj svake vrste

Uz to, postoji implicitno četvrto ograničenje:

  • u ćeliji može biti samo jedan broj

To daje ukupno četiri ograničenja, a time i 9 x 9 x 4 stupca u matrici Točan pokrov:

privatni statički int BOARD_SIZE = 9; privatni statički int SUBSECTION_SIZE = 3; privatni statički int NO_VALUE = 0; private static int OGRANIČENJA = 4; privatni statički int MIN_VALUE = 1; privatni statički int MAX_VALUE = 9; privatni statički int COVER_START_INDEX = 1;
private int getIndex (int redak, int stupac, int broj) {return (redak - 1) * BOARD_SIZE * BOARD_SIZE + (stupac - 1) * BOARD_SIZE + (num - 1); }
private boolean [] [] createExactCoverBoard () {boolean [] [] coverBoard = novo boolean [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); povratak coverBoard; } private int checkSubsectionConstraint (boolean [] [] coverBoard, int hBase) {for (int row = COVER_START_INDEX; row <= BOARD_SIZE; row + = SUBSECTION_SIZE) {for (int column = COVER_START_INDEX; column <= BOARD_SIZE; ) {for (int n = COVER_START_INDEX; n <= BOY_SIZE; n ++, hBase ++) {for (int rowDelta = 0; rowDelta <SUBSECTION_SIZE; rowDelta ++) {for (int columnDelta = 0; columnDelta <SUBSECTION_SIZE; {indexDelta = index getIndex (redak + redaDelta, stupac + stupacDelta, n); coverBoard [indeks] [hBase] = true; }}}}} return 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 ++) {for ( int redak = COVER_START_INDEX; redak <= BOARD_SIZE; redak ++) {int indeks = getIndex (redak, stupac, n); coverBoard [indeks] [hBase] = točno; }}} return 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 ++) {for ( int stupac = COVER_START_INDEX; stupac <= BOARD_SIZE; stupac ++) {int index = getIndex (redak, stupac, n); coverBoard [indeks] [hBase] = točno; }}} return 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 <= VELIČINA_PLAČE; n ++) {int indeks = getIndex (redak, stupac, n); coverBoard [indeks] [hBase] = true; }}} return hBase; }

Dalje, moramo ažurirati novostvorenu ploču s našim početnim izgledom slagalice:

privatni logički [] [] initializeExactCoverBoard (int [] [] ploča) {boolean [] [] coverBoard = createExactCoverBoard (); za (int redak = COVER_START_INDEX; red <= BOARD_SIZE; red ++) {za (int stupac = COVER_START_INDEX; stupac <= BOARD_SIZE; stupac ++) {int n = ploča [red - 1] [stupac - 1]; if (n! = NO_VALUE) {for (int num = MIN_VALUE; num <= MAX_VALUE; num ++) {if (num! = n) {Arrays.fill (coverBoard [getIndex (redak, stupac, broj)], false); }}}}} povratak coverBoard; }

Sada smo spremni za prelazak na sljedeću fazu. Stvorimo dvije klase koje će povezati naše stanice zajedno.

4.4. Plesni čvor

Algoritam Dancing Links djeluje na osnovnom opažanju koje slijedi na dvostruko povezanim popisima čvorova:

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

uklanja čvor, dok:

node.prev = node node.next = node

obnavlja čvor.

Svaki čvor u DLX-u povezan je s čvorom lijevo, desno, gore i dolje.

DancingNode klasa će imati sve operacije potrebne za dodavanje ili uklanjanje čvorova:

klasa DancingNode {DancingNode L, R, U, D; Čvor stupca C; DancingNode hookDown (čvor DancingNode) {assert (this.C == node.C); node.D = this.D; node.D.U = node; node.U = ovo; ovo.D = čvor; povratni čvor; } DancingNode hookRight (čvor DancingNode) {node.R = this.R; čvor.R.L = čvor; node.L = ovo; ovo.R = čvor; povratni čvor; } 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 = ovo; } DancingNode (ColumnNode c) {this (); C = c; }}

4.5. Čvor stupca

ColumnNode klasa će povezati stupce:

klasa ColumnNode proširuje DancingNode {int veličina; Naziv niza; ColumnNode (Niz n) {super (); veličina = 0; ime = n; C = ovo; } void cover () {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.size--; }}} void uncover () {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. Rješavač

Dalje, moramo stvoriti mrežu koja se sastoji od naših DancingNode i ColumnNode objekti:

private ColumnNode makeDLXBoard (boolean [] [] grid) {int COLS = grid [0] .length; ColumnNode headerNode = novi ColumnNode ("header"); Popis stupacaNovi = novi 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 (boolean [] aGrid: grid) {DancingNode prev = null; for (int j = 0; j <COLS; j ++) {if (aGrid [j]) {ColumnNode col = columnNodes.get (j); DancingNode newNode = novi DancingNode (col); if (prev == null) prev = newNode; col.U.hookDown (newNode); prev = prev.hookRight (newNode); col.size ++; }}} headerNode.size = COLS; vratiti headerNode; }

Koristit ćemo heurističko pretraživanje kako bismo pronašli stupce i vratili podskup matrice:

private ColumnNode selectColumnNodeHeuristic () {int min = Integer.MAX_VALUE; ColumnNode ret = null; za (ColumnNode c = (ColumnNode) header.R; c! = header; c = (ColumnNode) c.R) {if (c.size <min) {min = c.size; ret = c; }} povratak ret; }

Napokon, možemo rekurzivno potražiti odgovor:

privatno void pretraživanje (int k) {if (header.R == header) {handleSolution (odgovor); } else {StupacNod c = selectColumnNodeHeuristic (); c.cover (); za (DancingNode r = c.D; r! = c; r = r.D) {answer.add (r); za (DancingNode j = r.R; j! = r; j = j.R) {j.C.cover (); } pretraga (k + 1); r = answer.remove (answer.size () - 1); c = r.C; za (DancingNode j = r.L; j! = r; j = j.L) {j.C.uncover (); }} c.uncover (); }}

Ako više nema stupaca, tada možemo isprintati riješenu Sudoku ploču.

5. Mjerila

Ta dva različita algoritma možemo usporediti pokretanjem na istom računalu (na taj način možemo izbjeći razlike u komponentama, brzini CPU-a ili RAM-a itd.). Stvarna vremena razlikuju se od računala do računala.

Međutim, trebali bismo moći vidjeti relativne rezultate, a to će nam reći koji algoritam radi brže.

Algoritmu povratka treba oko 250 ms da riješi ploču.

Ako ovo usporedimo s Plesnim vezama, koje traju oko 50 ms, možemo vidjeti jasnog pobjednika. Dancing Links je oko pet puta brži kada se rješava ovaj konkretni primjer.

6. Zaključak

U ovom uputstvu raspravljali smo o dva rješenja za sudoku slagalicu s jezgrom Java. Algoritam povratka unatrag, koji je algoritam grube sile, može lako riješiti standardnu ​​9 × 9 zagonetku.

Razgovarano je i o malo složenijem algoritmu Dancing Links. Oboje rješavaju najteže zagonetke u roku od nekoliko sekundi.

Napokon, kao i uvijek, kod korišten tijekom rasprave možete pronaći na GitHubu.