Hozzon létre egy Sudoku Solver-t Java-ban

1. Áttekintés

Ebben a cikkben a Sudoku puzzle-t és a megoldáshoz használt algoritmusokat fogjuk megvizsgálni.

Ezután megoldásokat fogunk bevezetni a Java-ban. Az első megoldás egy egyszerű durva erő támadása lesz. A második a Dancing Links technikát fogja használni.

Ne felejtsük el, hogy nem az OOP tervezésére, hanem az algoritmusokra összpontosítunk.

2. A Sudoku puzzle

Egyszerűen fogalmazva, a Sudoku egy kombinatorikus számelhelyezési puzzle, amelynek 9 x 9 cellarácsát részben kitöltve 1 és 9 közötti számokkal. A cél a fennmaradó, üres mezők kitöltése a többi számmal úgy, hogy minden sornak és oszlopnak csak egy legyen az egyes fajták száma.

Ráadásul a rács minden 3 x 3 alszakaszában nem lehet duplikálni egyetlen számot sem. A nehézségi szint természetesen nő az egyes táblák üres mezők számával.

2.1. Teszttábla

A megoldásunk érdekesebbé tétele és az algoritmus validálása érdekében a „világ legnehezebb sudoku” tábláját fogjuk használni:

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

2.2. Megoldott tábla

És hogy gyorsan elrontsuk a megoldást - a helyesen megoldott rejtvény a következő eredményt adja:

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. Visszalépés algoritmus

3.1. Bevezetés

A visszakövetési algoritmus úgy próbálja megoldani a rejtvényt, hogy minden cellát érvényes megoldással tesztel.

Ha nincs megsértése a korlátozásoknak, az algoritmus a következő cellába lép, kitölti az összes lehetséges megoldást és megismétli az összes ellenőrzést.

Ha van szabálysértés, akkor növeli a cella értékét. Amint a cella értéke eléri a 9-et, és még mindig van megsértés, akkor az algoritmus visszalép az előző cellába, és növeli a cella értékét.

Minden lehetséges megoldást kipróbál.

3.2. Megoldás

Először is definiáljuk táblánkat egész számok kétdimenziós tömbjeként. A 0-at fogjuk használni üres cellánkként.

int [] [] tábla = {{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}};

Hozzunk létre egy megoldani () módszer, amely a tábla bemeneti paraméterként, és sorokon, oszlopokon és értékeken keresztül iterál, és minden cellán érvényes megoldást tesztel:

privát logikai megoldás (int [] [] tábla) {for (int sor = BOARD_START_INDEX; sor <BOARD_SIZE; sor ++) {for (int oszlop = BOARD_START_INDEX; oszlop <BOARD_SIZE; oszlop ++) {if (tábla [sor] [oszlop] = = NO_VALUE) {for (int k = MIN_VALUE; k <= MAX_VALUE; k ++) {tábla [sor] [oszlop] = k; if (isValid (tábla, sor, oszlop) && megoldani (tábla)) {return true; } tábla [sor] [oszlop] = NEM ÉRTÉK; } return false; }}} return true; }

Egy másik módszer, amire szükségünk volt, az érvényes() metódus, amely ellenőrzi a Sudoku-kényszereket, vagyis ellenőrizze, hogy a sor, oszlop és 3 x 3 rács érvényes-e:

privát logikai isValid (int [] [] tábla, int sor, int oszlop) {return (rowConstraint (tábla, sor) && columnConstraint (tábla, oszlop) && subsectionConstraint (tábla, sor, oszlop)); }

Ez a három ellenőrzés viszonylag hasonló. Először kezdjük a sorellenőrzésekkel:

privát logikai sorConstraint (int [] [] tábla, int sor) {logikai [] kényszer = új logikai [BOARD_SIZE]; return IntStream.range (BOARD_START_INDEX, BOARD_SIZE) .allMatch (oszlop -> checkConstraint (tábla, sor, kényszer, oszlop)); }

Ezután majdnem azonos kódot használunk az oszlop érvényesítéséhez:

privát logikai oszlopKényszer (int [] [] tábla, int oszlop) {logikai [] kényszer = új logikai [BOARD_SIZE]; return IntStream.range (BOARD_START_INDEX, BOARD_SIZE) .allMatch (sor -> checkConstraint (tábla, sor, kényszer, oszlop)); }

Továbbá 3 x 3 alszakaszt kell érvényesítenünk:

privát logikai alszakaszKényszer (int [] [] tábla, int sor, int oszlop) {logikai [] kényszer = új logikai [BOARD_SIZE]; int subsectionRowStart = (sor / SUBSECTION_SIZE) * SUBSECTION_SIZE; int subsectionRowEnd = subsectionRowStart + SUBSECTION_SIZE; int subsectionColumnStart = (oszlop / 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 (tábla, r, kényszer, c)) hamis értéket ad vissza; }} return true; }

Végül szükségünk van a checkConstraint () módszer:

boolean checkConstraint (int [] [] tábla, int sor, logikai [] kényszer, int oszlop) {if (tábla [sor] [oszlop]! = NO_VALUE) {if (! kényszer [tábla [sor] [oszlop] - 1 ]) {kényszer [tábla [sor] [oszlop] - 1] = igaz; } else {return false; }} return true; }

Egyszer mindez megtörtént érvényes() módszer egyszerűen visszatérhet igaz.

Már majdnem készen állunk a megoldás tesztelésére. Az algoritmus elkészült. Viszont visszatér igaz vagy hamis csak.

Ezért a tábla vizuális ellenőrzéséhez csak ki kell nyomtatnunk az eredményt. Úgy tűnik, hogy ez nem része az algoritmusnak.

private void printBoard () {for (int sor = BOARD_START_INDEX; sor <BOARD_SIZE; sor ++)) {for (int oszlop = BOARD_START_INDEX; oszlop <BOARD_SIZE; oszlop ++) {System.out.print (tábla [sor] [oszlop] + "" ); } System.out.println (); }}

Sikeresen megvalósítottuk a visszalépés algoritmust, amely megoldja a Sudoku rejtvényt!

Nyilvánvaló, hogy van még mit fejleszteni, mivel az algoritmus naiv módon ellenőrzi az egyes lehetséges kombinációkat újra és újra (annak ellenére, hogy tudjuk, hogy az adott megoldás érvénytelen).

4. Tánc linkek

4.1. Pontos fedél

Nézzünk meg egy másik megoldást. A Sudoku pontosan lefedhető problémaként írható le, amelyet két objektum kapcsolatát mutató incidencia mátrix képviselhet.

Például, ha 1-től 7-ig számokat veszünk, és halmazokat gyűjtünk S = {A, B, C, D, E, F}, hol:

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

Célunk olyan részhalmazok kiválasztása, hogy minden szám csak egyszer legyen, és egyik sem ismétlődik meg, ezért a név.

A problémát egy mátrix segítségével ábrázolhatjuk, ahol az oszlopok számok, a sorok pedig halmazok:

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

Az S * = {B, D, F} részgyűjtemény pontos fedezet:

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

Minden oszlopban pontosan egy van az összes kijelölt sorban.

4.2. X algoritmus

Az X algoritmus a „Próba-hiba megközelítés” hogy megtalálja az összes megoldást a pontos borítóproblémára, azaz a példagyűjteményünkkel kezdve S = {A, B, C, D, E, F}, keresse meg az algyűjteményt S * = {B, D, F}.

Az X algoritmus a következőképpen működik:

  1. Ha a mátrix A nincs oszlopa, az aktuális részmegoldás érvényes megoldás;

    sikeres befejezés, különben válasszon egy oszlopot c (determinisztikusan)

  2. Válasszon egy sort r oly módon, hogy Ar, c = 1 (nemdeterminisztikusan, azaz próbáljon ki minden lehetőséget)
  3. Tartalmazza a sort r a részoldatban
  4. Minden oszlopra j oly módon, hogy Ar, j = 1, minden sorhoz én oly módon, hogy Aén, j = 1,

    sor törlése én mátrixból A ésoszlop törlése j mátrixból A

  5. Ismételje meg ezt az algoritmust rekurzívan a redukált mátrixon A

Az X algoritmus hatékony megvalósítása a Dancing Links algoritmus (röviden DLX), amelyet Dr. Donald Knuth javasolt.

A következő megoldást erősen inspirálta ez a Java-implementáció.

4.3. Pontos fedélprobléma

Először létre kell hoznunk egy mátrixot, amely a Sudoku puzzle-t pontos fedél problémaként jeleníti meg. A mátrixnak 9 ^ 3 sora lesz, azaz egy sor minden lehetséges szám (9 szám) minden lehetséges pozíciójához (9 sor x 9 oszlop).

Az oszlopok a táblát (ismét 9 x 9) fogják megszorozni a megszorítások számával.

Már három korlátozást definiáltunk:

  • minden sorban csak egy szám lesz minden fajta
  • minden oszlopnak csak egy száma lesz minden fajtából
  • minden alszakasznak csak egy száma lesz minden fajtából

Ezenkívül implicit negyedik korlátozás is létezik:

  • csak egy szám lehet egy cellában

Ez összesen négy megszorítást ad, tehát 9 x 9 x 4 oszlopot az Exact Cover mátrixban:

privát statikus int BOARD_SIZE = 9; privát statikus int SUBSECTION_SIZE = 3; privát statikus int NO_VALUE = 0; privát statikus int KORLÁTOZÁSOK = 4; privát statikus int MIN_VALUE = 1; privát statikus int MAX_VALUE = 9; privát statikus int COVER_START_INDEX = 1;
private int getIndex (int sor, int oszlop, int szám) {return (1. sor) * BOARD_SIZE * BOARD_SIZE + (oszlop - 1) * BOARD_SIZE + (szám - 1); }
privát logikai [] [] createExactCoverBoard () {logikai [] [] coverBoard = új logikai érték [BOARD_SIZE * BOARD_SIZE * MAX_VALUE] [BOARD_SIZE * BOARD_SIZE * CONSTRAINTS]; int hBase = 0; hBase = checkCellConstraint (fedőlap, hBase); hBase = checkRowConstraint (fedőlap, hBase); hBase = checkColumnConstraint (fedőlap, hBase); checkSubsectionConstraint (fedőlap, hBase); visszatérő fedéllap; } private int checkSubsectionConstraint (logikai [] [] coverBoard, int hBase) {for (int sor = COVER_START_INDEX; sor <= BOARD_SIZE; sor + = SUBSECTION_SIZE) {for (int oszlop = COVER_START_INDEX; oszlop <= BOARD_SIZE; oszlop + = SUB ) {for (int n = COVER_START_INDEX; n <= BOARD_SIZE; n ++, hBase ++) {for (int rowDelta = 0; rowDelta <SUBSECTION_SIZE; rowDelta ++) {for (int oszlopDelta = 0; oszlopDelta <SUBSECTION_SIZE; oszlopDelta ++) {int getIndex (sor + sorDelta, oszlop + oszlopDelta, n); fedőlap [index] [hBase] = igaz; }}}}} return hBase; } private int checkColumnConstraint (logikai [] [] fedőlap, int hBase) {for (int oszlop = COVER_START_INDEX; oszlop <= BOARD_SIZE; c ++) {for (int n = COVER_START_INDEX; n <= BOARD_SIZE; n ++, hBase ++) { int sor = COVER_START_INDEX; sor <= BOARD_SIZE; sor ++) {int index = getIndex (sor, oszlop, n); fedőlap [index] [hBase] = igaz; }}} return hBase; } private int checkRowConstraint (logikai [] [] coverBoard, int hBase) {for (int sor = COVER_START_INDEX; sor <= BOARD_SIZE; r ++) {for (int n = COVER_START_INDEX; n <= BOARD_SIZE; n ++, hBase ++) {for ( int oszlop = COVER_START_INDEX; oszlop <= BOARD_SIZE; oszlop ++) {int index = getIndex (sor, oszlop, n); fedőlap [index] [hBase] = igaz; }}} return hBase; } private int checkCellConstraint (logikai [] [] coverBoard, int hBase) {for (int sor = COVER_START_INDEX; sor <= BOARD_SIZE; sor ++) {for (int oszlop = COVER_START_INDEX; oszlop <= BOARD_SIZE; oszlop ++, hBase ++) {for ( int n = COVER_START_INDEX; n <= BOARD_SIZE; n ++) {int index = getIndex (sor, oszlop, n); fedőlap [index] [hBase] = igaz; }}} return hBase; }

Ezután frissítenünk kell az újonnan létrehozott táblát a kezdeti puzzle elrendezéssel:

privát logikai [] [] initizeExactCoverBoard (int [] [] board) {boolean [] [] coverBoard = createExactCoverBoard (); for (int sor = COVER_START_INDEX; sor <= BOARD_SIZE; sor ++) {for (int oszlop = COVER_START_INDEX; oszlop <= BOARD_SIZE; oszlop ++) {int n = tábla [1. sor] [oszlop - 1]; if (n! = NO_VALUE) {for (int szám = MIN_VALUE; num <= MAX_VALUE; num ++) {if (num! = n) {Tömbök.töltés (coverBoard [getIndex (sor, oszlop, szám)], hamis); }}}}} return fedőlap; }

Most már készen állunk a következő lépésre. Hozzunk létre két osztályt, amelyek összekapcsolják a sejtjeinket.

4.4. Táncoló csomópont

A Dancing Links algoritmus egy olyan alapvető megfigyelésen működik, amely a kettősen összekapcsolt csomópontlistákon végzett műveletet követi:

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

eltávolítja a csomópontot, míg:

node.prev = csomópont node.next = csomópont

visszaállítja a csomópontot.

A DLX minden csomópontja összekapcsolódik a bal, jobb, fel és le csomópontokkal.

DancingNode osztály elvégzi az összes műveletet, amely a csomópontok hozzáadásához vagy eltávolításához szükséges:

osztályú DancingNode {DancingNode L, R, U, D; OszlopNode C; DancingNode hookDown (DancingNode csomópont) {állítás (this.C == csomópont.C); csomópont.D = ez.D; csomópont.D.U = csomópont; csomópont.U = ez; ez.D = csomópont; visszatér csomópont; } DancingNode hookRight (DancingNode csomópont) {node.R = this.R; csomópont.R.L = csomópont; csomópont.L = ez; ez.R = csomópont; visszatér csomópont; } void unlinkLR () {this.L.R = this.R; ez.R.L = ez.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 = ez; } DancingNode (c oszlopcsomópont) {this (); C = c; }}

4.5. Oszlopcsomópont

ColumnNode osztály összekapcsolja az oszlopokat:

class ColumnNode kiterjeszti a DancingNode {int size; Karakterlánc neve; ColumnNode (String n) {super (); méret = 0; név = n; C = ez; } void cover () {unlinkLR (); mert (DancingNode i = ez.D; i! = ez; i = i.D) {for (DancingNode j = i.R; j! = i; j = j.R) {j.unlinkUD (); j.C. méret--; }}} 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. Megoldó

Ezután létre kell hoznunk egy rácsot, amely a mi-ből áll DancingNode és ColumnNode tárgyak:

privát ColumnNode makeDLXBoard (logikai [] [] rács) {int COLS = rács [0] .hossz; ColumnNode headerNode = új ColumnNode ("fejléc"); List columnNodes = new ArrayList (); for (int i = 0; i <COLS; i ++) {ColumnNode n = új ColumnNode (Integer.toString (i)); oszlopNodes.add (n); headerNode = (ColumnNode) headerNode.hookRight (n); } headerNode = headerNode.R.C; for (logikai [] aGrid: rács) {DancingNode prev = null; for (int j = 0; j <COLS; j ++) {if (aGrid [j]) {OszlopNode oszlop = columnNodes.get (j); DancingNode newNode = új DancingNode (oszlop); if (prev == null) prev = newNode; col.U.hookDown (newNode); prev = prev.hookRight (newNode); col.size ++; }}} headerNode.size = COLS; return headerNode; }

Heurisztikus kereséssel oszlopokat keresünk, és a mátrix egy részhalmazát adjuk vissza:

privát ColumnNode selectColumnNodeHeuristic () {int min = Egész szám.MAX_VALUE; ColumnNode ret = null; a (ColumnNode c = (ColumnNode) fejléchez.R; c! = header; c = (ColumnNode) c.R) {if (c.size <min) {min = c.size; ret = c; }} return ret; }

Végül rekurzív módon kereshetjük a választ:

private void keresés (int k) {if (header.R == header) {handleSolution (válasz); } else {OszlopNode c = selectColumnNodeHeuristic (); c. fedél (); mert (DancingNode r = c.D; r! = c; r = r.D) {answer.add (r); mert (DancingNode j = r.R; j! = r; j = j.R) {j.C.fedél (); } keresés (k + 1); r = answer.remove (answer.size () - 1); c = rC; mert (DancingNode j = r.L; j! = r; j = j.L) {j.C. felfedés (); }} c. felfedés (); }}

Ha nincs több oszlop, akkor kinyomtathatjuk a megoldott Sudoku táblát.

5. Referenciaértékek

Összehasonlíthatjuk ezt a két különböző algoritmust úgy, hogy ugyanazon a számítógépen futtatjuk őket (így elkerülhetjük az alkatrészek, a CPU vagy a RAM sebességének stb. Különbségeit). A tényleges időpontok számítógépenként változnak.

Viszont látnunk kell a relatív eredményeket, és ez megmondja, melyik algoritmus fut gyorsabban.

A Backtracking algoritmus körülbelül 250 ms-ot vesz igénybe a tábla megoldásához.

Ha összehasonlítjuk ezt a Dancing Links-kel, amely körülbelül 50 ms-ot vesz igénybe, akkor egyértelmű nyertest láthatunk. A Dancing Links körülbelül ötször gyorsabb, ha megoldjuk ezt a példát.

6. Következtetés

Ebben az oktatóanyagban két megoldást vitattunk meg egy mag Java-val rendelkező sudoku rejtvényről. A visszalépés algoritmus, amely egy durva erő algoritmus, könnyen megoldhatja a szokásos 9 × 9 puzzle-t.

A kissé bonyolultabb Dancing Links algoritmusról is szó esett. Mindkettő másodpercek alatt megoldja a legnehezebb rejtvényeket.

Végül, mint mindig, a vita során használt kód megtalálható a GitHubon.


Népszerű Bejegyzések

Legutóbbi hozzászólások

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