Vytvorte Sudoku Solver v Jave
1. Prehľad
V tomto článku sa pozrieme na hlavolamy a algoritmy použité pri jeho riešení.
Ďalej implementujeme riešenia v prostredí Java. Prvým riešením bude jednoduchý útok hrubou silou. Druhá bude využívať techniku Dancing Links.
Pamätajme na to, že zameranie sa zameriame na algoritmy a nie na návrh OOP.
2. Puzzle Sudoku
Zjednodušene povedané, Sudoku je kombinatorická skladačka na umiestňovanie čísel s mriežkou buniek 9 x 9, ktorá je čiastočne vyplnená číslami od 1 do 9. Cieľom je vyplniť zvyšné prázdne polia zvyškom čísel tak, aby každý riadok a stĺpec mal iba jedno počet každého druhu.
A čo viac, v každej podsekcii mriežky 3 x 3 nemôže byť tiež duplikované žiadne číslo. Úroveň obtiažnosti prirodzene stúpa s počtom prázdnych polí na každej doske.
2.1. Skúšobná komisia
Aby bolo naše riešenie zaujímavejšie a overil sa algoritmus, použijeme dosku „najťažšie sudoku na svete“, ktorá je:
8 . . . . . . . . . . 3 6 . . . . . . 7 . . 9 . 2 . . . 5 . . . 7 . . . . . . . 4 5 7 . . . . . 1 . . . 3 . . . 1 . . . . 6 8 . . 8 5 . . . 1 . . 9 . . . . 4 . .2.2. Vyriešená rada
A aby sme riešenie rýchlo pokazili - správne vyriešené puzzle nám prinesie nasledujúci výsledok:
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. Algoritmus spätného sledovania
3.1. Úvod
Algoritmus Backtracking sa snaží vyriešiť hádanku testovaním každej bunky na platné riešenie.
Ak nedôjde k porušeniu obmedzení, algoritmus sa presunie do ďalšej bunky, vyplní všetky potenciálne riešenia a zopakuje všetky kontroly.
Ak dôjde k porušeniu, zvýši sa hodnota bunky. Akonáhle hodnota bunky dosiahne 9, stále existuje porušenie, potom sa algoritmus presunie späť do predchádzajúcej bunky a zvýši hodnotu tejto bunky.
Skúša všetky možné riešenia.
3.2. Riešenie
Najskôr si definujme našu dosku ako dvojrozmerné pole celých čísel. Ako svoju prázdnu bunku použijeme 0.
int [] [] board = {{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}};Vytvorme a vyriešiť () metóda, ktorá vyžaduje doska ako vstupný parameter a iteruje cez riadky, stĺpce a hodnoty testujúce každú bunku na platné riešenie:
súkromné boolovské riešenie (int [] [] doska) {pre (int riadok = BOARD_START_INDEX; riadok <BOARD_SIZE; riadok ++) {pre (int stĺpec = BOARD_START_INDEX; stĺpec <BOARD_SIZE; stĺpec ++) {if (board [riadok] [stĺpec] = = NO_VALUE) {for (int k = MIN_VALUE; k <= MAX_VALUE; k ++) {board [riadok] [stĺpec] = k; if (isValid (doska, riadok, stĺpec) &&olve (doska)) {return true; } doska [riadok] [stĺpec] = NO_VALUE; } return false; }}} návrat true; }Ďalšia metóda, ktorú sme potrebovali, je je platné() metóda, ktorá bude kontrolovať obmedzenia sudoku, t. j. skontrolovať, či sú riadok, stĺpec a mriežka 3 x 3 platné:
private boolean isValid (int [] [] doska, int riadok, int stĺpec) {return (rowConstraint (doska, riadok) && columnConstraint (doska, stĺpec) && subsectionConstraint (doska, riadok, stĺpec)); }Tieto tri kontroly sú si relatívne podobné. Najprv začnime s kontrolami riadkov:
private boolean rowConstraint (int [] [] board, int row) {boolean [] constraint = new boolean [BOARD_SIZE]; návrat IntStream.range (BOARD_START_INDEX, BOARD_SIZE) .allMatch (stĺpec -> checkConstraint (doska, riadok, obmedzenie, stĺpec)); }Ďalej používame na overenie stĺpca takmer identický kód:
private boolean columnConstraint (int [] [] board, int column) {boolean [] constraint = new boolean [BOARD_SIZE]; návrat IntStream.range (BOARD_START_INDEX, BOARD_SIZE) .allMatch (riadok -> checkConstraint (doska, riadok, obmedzenie, stĺpec)); }Ďalej musíme potvrdiť pododdiel 3 x 3:
private boolean subsectionConstraint (int [] [] doska, int riadok, int stĺpec) {boolean [] obmedzenie = nový boolean [BOARD_SIZE]; int subsectionRowStart = (riadok / SUBSECTION_SIZE) * SUBSECTION_SIZE; int subsectionRowEnd = subsectionRowStart + SUBSECTION_SIZE; int subsectionColumnStart = (stĺpec / 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; }} návrat true; }Nakoniec potrebujeme a checkConstraint () metóda:
boolean checkConstraint (int [] [] doska, int riadok, boolean [] obmedzenie, int stĺpec) {if (board [riadok] [stĺpec]! = NO_VALUE) {if (! obmedzenie [doska [riadok] [stĺpec] - 1 ]) {obmedzenie [doska [riadok] [stĺpec] - 1] = pravda; } else {return false; }} návrat true; }Raz je všetko hotové je platné() metóda sa môže jednoducho vrátiť pravda.
Teraz sme takmer pripravení testovať riešenie. Algoritmus je hotový. Vracia sa však pravda alebo nepravdivé iba.
Preto na vizuálnu kontrolu dosky stačí vytlačiť výsledok. Zdá sa, že to nie je súčasťou algoritmu.
private void printBoard () {for (int riadok = BOARD_START_INDEX; riadok <BOARD_SIZE; riadok ++) {pre (int stĺpec = BOARD_START_INDEX; stĺpec <BOARD_SIZE; stĺpec ++) {System.out.print (doska [riadok] [stĺpec] + "" ); } System.out.println (); }}Úspešne sme implementovali algoritmus spätného sledovania, ktorý rieši hádanku Sudoku!
Je zrejmé, že existuje priestor na vylepšenie, pretože algoritmus naivne kontroluje každú možnú kombináciu znova a znova (aj keď vieme, že konkrétne riešenie je neplatné).
4. Tanečné odkazy
4.1. Presný obal
Pozrime sa na iné riešenie. Sudoku možno označiť za problém presného krytia, ktorý je možné znázorniť pomocou matice incidencie ukazujúcej vzťah medzi dvoma objektmi.
Napríklad, ak vezmeme čísla od 1 do 7 a zbierku množín S = {A, B, C, D, E, F}, kde:
- A = {1, 4, 7}
- B = {1, 4}
- C. = {4, 5, 7}
- D = {3, 5, 6}
- E = {2, 3, 6, 7}
- F = {2, 7}
Naším cieľom je vybrať také podmnožiny, aby každé číslo bolo iba raz a žiadne sa neopakovalo, odtiaľ pochádza aj názov.
Problém môžeme reprezentovať pomocou matice, kde stĺpce sú čísla a riadky súpravy:
| 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 |Podkolekcia S * = {B, D, F} je presná obálka:
| 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 |Každý stĺpec má vo všetkých vybratých riadkoch presne jednu 1.
4.2. Algoritmus X
Algoritmus X je a „Prístup pokusov a omylov“ nájsť všetky riešenia presného problému s obalom, t. j. počnúc našou ukážkovou zbierkou S = {A, B, C, D, E, F}, nájsť podkolekciu S * = {B, D, F}.
Algoritmus X funguje nasledovne:
- Ak matica A nemá žiadne stĺpce, súčasné čiastočné riešenie je platným riešením;
ukončiť úspešne, inak zvoľte stĺpec c (deterministicky)
- Vyberte riadok r také, že Ar, c = 1 (nedeterministicky, tj. Vyskúšať všetky možnosti)
- Zahrnúť riadok r v čiastočnom riešení
- Pre každý stĺpec j také, že Ar, j = 1, pre každý riadok i také, že Ai, j = 1,
vymazať riadok i z matice A aodstrániť stĺpec j z matice A
- Tento algoritmus opakujte rekurzívne na redukovanej matici A
Účinnou implementáciou algoritmu X je algoritmus Dancing Links (skrátene DLX), ktorý navrhol Dr. Donald Knuth.
Nasledujúce riešenie bolo výrazne inšpirované touto implementáciou Java.
4.3. Presný problém s krytom
Najskôr musíme vytvoriť maticu, ktorá bude predstavovať sudoku ako problém s presným obalom. Matica bude mať 9 ^ 3 riadky, t. J. Jeden riadok pre každú možnú pozíciu (9 riadkov x 9 stĺpcov) každého možného čísla (9 čísel).
Stĺpce budú predstavovať nástenku (opäť 9 x 9) vynásobenú počtom obmedzení.
Už sme definovali tri obmedzenia:
- každý riadok bude mať iba jedno číslo od každého druhu
- každý stĺpec bude mať iba jedno číslo od každého druhu
- každá podsekcia bude mať iba jedno číslo od každého druhu
Ďalej existuje implicitné štvrté obmedzenie:
- v bunke môže byť iba jedno číslo
Toto dáva celkovo štyri obmedzenia, a teda stĺpce 9 x 9 x 4 v matici Exact Cover:
private static int BOARD_SIZE = 9; private static int SUBSECTION_SIZE = 3; private static int NO_VALUE = 0; private static int OBMEDZENIA = 4; private static int MIN_VALUE = 1; private static int MAX_VALUE = 9; private static int COVER_START_INDEX = 1;private int getIndex (int riadok, int stĺpec, int num) {návrat (riadok - 1) * BOARD_SIZE * BOARD_SIZE + (stĺpec - 1) * BOARD_SIZE + (num - 1); }private boolean [] [] createExactCoverBoard () {boolean [] [] coverBoard = new 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); spätný kryt Doska; } private int checkSubsectionConstraint (boolean [] [] coverBoard, int hBase) {for (int riadok = COVER_START_INDEX; riadok <= BOARD_SIZE; riadok + = SUBSECTION_SIZE) {pre (int stĺpec = COVER_START_INDEX; stĺpec <= BOARD_SIZE; stĺpec + = SK ) {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 getIndex (riadok + riadokDelta, stĺpec + stĺpecDelta, n); coverBoard [index] [hBase] = true; }}}}} vrátiť 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 riadok = COVER_START_INDEX; riadok <= BOARD_SIZE; riadok ++) {int index = getIndex (riadok, stĺpec, n); coverBoard [index] [hBase] = true; }}} vratit 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 stĺpec = COVER_START_INDEX; stĺpec <= BOARD_SIZE; stĺpec ++) {int index = getIndex (riadok, stĺpec, n); coverBoard [index] [hBase] = true; }}} vratit 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 (riadok, stĺpec, n); coverBoard [index] [hBase] = true; }}} vratit hBase; }Ďalej musíme aktualizovať novovytvorenú dosku s našim pôvodným rozložením puzzle:
private boolean [] [] initializeExactCoverBoard (int [] [] board) {boolean [] [] coverBoard = createExactCoverBoard (); pre (int riadok = COVER_START_INDEX; riadok <= BOARD_SIZE; riadok ++) {pre (int stĺpec = COVER_START_INDEX; stĺpec <= BOARD_SIZE; stĺpec ++) {int n = doska [riadok - 1] [stĺpec - 1]; if (n! = NO_VALUE) {for (int num = MIN_VALUE; num <= MAX_VALUE; num ++) {if (num! = n) {Arrays.fill (coverBoard [getIndex (row, column, num)], false); }}}}} vrátiť coverBoard; }Teraz sme pripravení prejsť do ďalšej fázy. Vytvorme dve triedy, ktoré spoja naše bunky.
4.4. Tancujúci uzol
Algoritmus Dancing Links pracuje na základnom pozorovaní, že nasledujúca operácia na dvojnásobne prepojených zoznamoch uzlov:
node.prev.next = node.next node.next.prev = node.prevodstráni uzol, zatiaľ čo:
node.prev = uzol node.next = uzolobnoví uzol.
Každý uzol v DLX je prepojený s uzlom vľavo, vpravo, hore a dole.
DancingNode trieda bude mať všetky operácie potrebné na pridanie alebo odstránenie uzlov:
trieda DancingNode {DancingNode L, R, U, D; ColumnNode C; DancingNode hookDown (uzol DancingNode) {assert (this.C == node.C); uzol.D = toto.D; uzol D.U = uzol; node.U = toto; this.D = node; spätný uzol; } DancingNode hookRight (uzol DancingNode) {node.R = this.R; uzol.R.L = uzol; node.L = this; this.R = uzol; spätný uzol; } 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 = toto; } DancingNode (ColumnNode c) {this (); C = c; }}4.5. Uzol stĺpca
ColumnNode trieda prepojí stĺpce:
trieda ColumnNode rozširuje DancingNode {int veľkosť; Názov reťazca; ColumnNode (Reťazec n) {super (); veľkosť = 0; meno = n; C = toto; } void cover () {unlinkLR (); pre (DancingNode i = this.D; i! = this; i = i.D) {for (DancingNode j = i.R; j! = i; j = j.R) {j.unlinkUD (); j.C. veľkosť -; }}} 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. Riešiteľ
Ďalej musíme vytvoriť mriežku pozostávajúcu z našej DancingNode a ColumnNode objekty:
private ColumnNode makeDLXBoard (boolean [] [] grid) {int COLS = grid [0] .length; ColumnNode headerNode = nový ColumnNode ("hlavička"); Zoznam stĺpcových uzlov = nový ArrayList (); pre (int i = 0; i <COLS; i ++) {ColumnNode n = nový ColumnNode (Integer.toString (i)); columnNodes.add (n); headerNode = (ColumnNode) headerNode.hookRight (n); } headerNode = headerNode.R.C; pre (boolean [] aGrid: grid) {DancingNode prev = null; for (int j = 0; j <COLS; j ++) {if (aGrid [j]) {ColumnNode col = columnNodes.get (j); DancingNode newNode = nový DancingNode (col); if (prev == null) prev = newNode; col.U.hookDown (newNode); prev = prev.hookRight (newNode); col.size ++; }}} headerNode.size = COLS; návrat headerNode; }Použijeme heuristické vyhľadávanie na nájdenie stĺpcov a vrátenie podmnožiny matice:
private ColumnNode selectColumnNodeHeuristic () {int min = Integer.MAX_VALUE; ColumnNode ret = null; pre (ColumnNode c = (ColumnNode) header.R; c! = header; c = (ColumnNode) c.R) {if (c.size <min) {min = c.size; ret = c; }} návrat ret; }Na záver môžeme rekurzívne hľadať odpoveď:
private void search (int k) {if (header.R == header) {handleSolution (answer); } else {ColumnNode c = selectColumnNodeHeuristic (); c.cover (); pre (DancingNode r = c.D; r! = c; r = r.D) {answer.add (r); pre (DancingNode j = r.R; j! = r; j = j.R) {j.C.cover (); } vyhladat (k + 1); r = answer.remove (answer.size () - 1); c = r.C; pre (DancingNode j = r.L; j! = r; j = j.L) {j.C.uncover (); }} c.uncover (); }}Ak už nie sú žiadne stĺpce, môžeme vytlačiť vyriešenú dosku Sudoku.
5. Referenčné hodnoty
Tieto dva rôzne algoritmy môžeme porovnať tak, že ich spustíme na rovnakom počítači (vyhneme sa tak rozdielom v komponentoch, rýchlosti CPU alebo RAM atď.). Skutočné časy sa budú líšiť od počítača k počítaču.
Mali by sme však byť schopní vidieť relatívne výsledky, a to nám prezradí, ktorý algoritmus beží rýchlejšie.
Algoritmus spätného sledovania trvá vyriešenie hernej plochy približne 250 ms.
Ak to porovnáme s Tanečnými odkazmi, ktoré trvajú asi 50 ms, môžeme vidieť jasného víťaza. Dancing Links je pri riešení tohto konkrétneho príkladu asi päťkrát rýchlejší.
6. Záver
V tomto tutoriáli sme diskutovali o dvoch riešeniach logickej hry sudoku s jadrom Java. Algoritmus spätného sledovania, ktorý je algoritmom hrubej sily, dokáže ľahko vyriešiť štandardnú hádanku 9 × 9.
Diskutovalo sa tiež o trochu komplikovanejšom algoritme Dancing Links. Obe vyriešia najťažšie hádanky v priebehu niekoľkých sekúnd.
Nakoniec, ako vždy, kód použitý počas diskusie nájdete na GitHub.
