צור סודוקו פותר בג'אווה

1. סקירה כללית

במאמר זה נבחן את הפאזל של סודוקו ואלגוריתמים המשמשים לפתרון.

לאחר מכן ניישם פתרונות ב- Java. הפיתרון הראשון יהיה התקפת כוח אכזרי פשוט. השני ישתמש בטכניקת Dancing Links.

בואו נזכור כי המיקוד בו אנו מתמקדים באלגוריתמים ולא בתכנון ה- OOP.

2. פאזל הסודוקו

במילים פשוטות, סודוקו הוא חידת מיקום מספרים קומבינטורית עם רשת תאים 9x9 מלאה חלקית עם מספרים מ -1 עד 9. המטרה היא למלא שדות ריקים שנותרו עם שאר המספרים כך שלכל שורה ועמודה יהיה רק אחד מספר מכל סוג.

יתרה מכך, בכל מקטע של 3 x 3 של הרשת לא יכול להיות שום מספר משוכפל גם כן. באופן טבעי רמת הקושי עולה עם מספר השדות הריקים בכל לוח.

2.1. מועצת המבחנים

כדי להפוך את הפתרון שלנו למעניין יותר וכדי לאמת את האלגוריתם, נשתמש בלוח "הסודוקו הקשה בעולם", שהוא:

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

2.2. מועצה נפתרה

וכדי לקלקל את הפתרון במהירות - הפאזל שנפתר כהלכה ייתן לנו את התוצאה הבאה:

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. אלגוריתם חזרה על המסלול

3.1. מבוא

אלגוריתם Backtracking מנסה לפתור את הפאזל על ידי בדיקת פתרון חוקי בכל תא.

אם אין הפרה של אילוצים, האלגוריתם עובר לתא הבא, ממלא את כל הפתרונות הפוטנציאליים וחוזר על כל הבדיקות.

אם יש הפרה, זה מגדיל את ערך התא. פעם אחת, הערך של התא מגיע ל- 9, ועדיין יש הפרה ואז האלגוריתם חוזר לתא הקודם ומעלה את הערך של אותו תא.

הוא מנסה את כל הפתרונות האפשריים.

3.2. פִּתָרוֹן

ראשית, נגדיר את הלוח שלנו כמערך דו-ממדי של מספרים שלמים. נשתמש ב- 0 כתא הריק שלנו.

int [] [] לוח = {{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}};

בואו ניצור לִפְתוֹר() שיטה שלוקחת את גלשן כפרמטר הקלט ומתחזר דרך שורות, עמודות וערכים שבודקים כל תא לפתרון חוקי:

לפתור בוליאני פרטי (int [] [] לוח) {עבור (int שורה = BOARD_START_INDEX; שורה <BOARD_SIZE; שורה ++) {עבור (עמודה int = BOARD_START_INDEX; עמודה <BOARD_SIZE; עמודה ++) {אם (לוח [שורה] [עמודה] = = NO_VALUE) {עבור (int k = MIN_VALUE; k <= MAX_VALUE; k ++) {לוח [שורה] [עמודה] = k; אם (isValid (לוח, שורה, עמודה) && לפתור (לוח)) {להחזיר נכון; } לוח [שורה] [עמודה] = NO_VALUE; } להחזיר שקר; }}} להחזיר אמת; }

שיטה אחרת שהיינו זקוקים לה היא isValid () שיטה, אשר הולכת לבדוק אילוצי סודוקו, כלומר לבדוק אם השורה, העמודה ורשת 3 x 3 תקפות:

פרטי בוליאני isValid (int [] [] לוח, שורה int, int עמודה) {return (rowConstraint (board, row) && columnConstraint (board, column) && subsectionConstraint (לוח, שורה, עמודה)); }

שלושת המחאות הללו דומות יחסית. ראשית, נתחיל בבדיקות שורה:

שורה בוליאנית פרטית Constraint (int [] [] לוח, int שורה) {בוליאני [] constraint = בוליאני חדש [BOARD_SIZE]; להחזיר IntStream.range (BOARD_START_INDEX, BOARD_SIZE) .allMatch (עמודה -> checkConstraint (לוח, שורה, אילוץ, עמודה)); }

לאחר מכן אנו משתמשים בקוד כמעט זהה לאימות העמודה:

טור בוליאני פרטי Constraint (int [] [] לוח, טור int) {בוליאני [] constraint = בוליאני חדש [BOARD_SIZE]; להחזיר IntStream.range (BOARD_START_INDEX, BOARD_SIZE). allMatch (שורה -> checkConstraint (לוח, שורה, אילוץ, עמודה)); }

יתר על כן, עלינו לאמת סעיף קטן של 3 x 3:

תת סעיף בוליאני פרטי Constraint (int [] [] לוח, שורה int, עמודה int) {בוליאני [] constraint = בוליאני חדש [BOARD_SIZE]; int subsectionRowStart = (שורה / SUBSECTION_SIZE) * SUBSECTION_SIZE; int subsectionRowEnd = subsectionRowStart + SUBSECTION_SIZE; int subsectionColumnStart = (עמודה / SUBSECTION_SIZE) * SUBSECTION_SIZE; int subsectionColumnEnd = subsectionColumnStart + SUBSECTION_SIZE; עבור (int r = subsectionRowStart; r <subsectionRowEnd; r ++) {for (int c = subsectionColumnStart; c <subsectionColumnEnd; c ++) {if (! checkConstraint (board, r, constraint, c)) return false; }} להחזיר אמת; }

לבסוף, אנחנו צריכים checkConstraint () שיטה:

checkConstraint בוליאני (לוח int [] [], שורה שורה, מגבלה בוליאנית [], עמודה int) {if (לוח [שורה] [טור]! = NO_VALUE) {אם (! אילוץ [לוח [שורה] [טור] - 1 ]) {constraint [board [row] [column] - 1] = true; } אחר {להחזיר כוזב; }} להחזיר אמת; }

פעם אחת, כל מה שנעשה isValid () השיטה יכולה פשוט לחזור נָכוֹן.

אנחנו כמעט מוכנים לבדוק את הפתרון עכשיו. האלגוריתם נעשה. עם זאת, הוא חוזר נָכוֹן אוֹ שֶׁקֶר רק.

לכן, כדי לבדוק חזותית את הלוח אנחנו צריכים רק להדפיס את התוצאה. ככל הנראה, זה לא חלק מהאלגוריתם.

חלל פרטי printBoard () {עבור (int שורה = BOARD_START_INDEX; שורה <BOARD_SIZE; שורה ++) {עבור (int עמודה = BOARD_START_INDEX; עמודה <BOARD_SIZE; עמודה ++) {System.out.print (לוח [שורה] [עמודה] + "" ); } System.out.println (); }}

יישמנו בהצלחה אלגוריתם מעקב אחורני הפותר את חידת סודוקו!

ברור שיש מקום לשיפורים שכן האלגוריתם בודק באופן נאיבי כל שילוב אפשרי שוב ושוב (למרות שאנו יודעים שהפתרון המסוים אינו תקף).

4. קישורים רוקדים

4.1. כיסוי מדויק

בואו נסתכל על פיתרון אחר. ניתן לתאר את סודוקו כבעיית כיסוי מדויק, שניתן לייצג על ידי מטריצת שכיחות המציגה את הקשר בין שני אובייקטים.

לדוגמא, אם ניקח מספרים מ -1 עד 7 ואת אוסף הסטים S = {A, B, C, D, E, F}, איפה:

א = {1, 4, 7}
ב = {1, 4}
ג = {4, 5, 7}
ד = {3, 5, 6}
ה = {2, 3, 6, 7}
F = {2, 7}

המטרה שלנו היא לבחור קבוצות משנה כאלה שכל מספר נמצא שם רק פעם אחת ואף אחד לא חוזר ומכאן השם.

אנו יכולים לייצג את הבעיה באמצעות מטריצה, כאשר העמודות הן מספרים ושורות הן קבוצות:

 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | א | 1 | 0 | 0 | 1 | 0 | 0 | 1 | ב | 1 | 0 | 0 | 1 | 0 | 0 | 0 | ג | 0 | 0 | 0 | 1 | 1 | 0 | 1 | ד | 0 | 0 | 1 | 0 | 1 | 1 | 0 | ה | 0 | 1 | 1 | 0 | 0 | 1 | 1 | F | 0 | 1 | 0 | 0 | 0 | 0 | 1 |

אוסף המשנה S * = {B, D, F} הוא הכריכה המדויקת:

 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | ב | 1 | 0 | 0 | 1 | 0 | 0 | 0 | ד | 0 | 0 | 1 | 0 | 1 | 1 | 0 | F | 0 | 1 | 0 | 0 | 0 | 0 | 1 |

לכל עמודה יש בדיוק 1 בכל השורות שנבחרו.

4.2. אלגוריתם X

אלגוריתם X הוא א "גישת ניסוי וטעייה" למצוא את כל הפתרונות לבעיית הכיסוי המדויקת, כלומר החל מאוסף הדוגמאות שלנו S = {A, B, C, D, E, F}, מצא אוסף משנה S * = {B, D, F}.

אלגוריתם X פועל באופן הבא:

אם המטריצה א אין עמודות, הפיתרון החלקי הנוכחי הוא פיתרון תקף;
לסיים בהצלחה, אחרת, בחר עמודה ג (באופן דטרמיניסטי)
בחר שורה ר כך ש א_{ר, ג} = 1 (באופן לא קבוע, כלומר נסה את כל האפשרויות)
כלול שורה ר בפתרון החלקי
לכל טור י כך ש א_{ר, י} = 1, לכל שורה אני כך ש א_{אני, י} = 1,
מחק שורה אני ממטריקס א ומחק טור י ממטריקס א
חזור על אלגוריתם זה רקורסיבית על המטריצה המופחתת א

יישום יעיל של האלגוריתם X הוא אלגוריתם Dancing Links (בקיצור DLX) שהציע ד"ר דונלד קנוט.

הפתרון הבא קיבל השראה רבה מיישום Java זה.

4.3. בעיית כיסוי מדויקת

ראשית, עלינו ליצור מטריצה שתייצג את פאזל סודוקו כבעיית כיסוי מדויק. למטריצה יהיו 9 ^ 3 שורות, כלומר שורה אחת לכל מיקום אפשרי (9 שורות x 9 עמודות) מכל מספר אפשרי (9 מספרים).

עמודות ייצגו את הלוח (שוב 9 x 9) כפול מספר האילוצים.

הגדרנו כבר שלוש אילוצים:

בכל שורה יהיה מספר אחד בלבד מכל סוג
בכל עמודה יהיה מספר אחד בלבד מכל סוג
בכל סעיף משנה יהיה מספר אחד בלבד מכל סוג

בנוסף, קיימת אילוץ רביעי מרומז:

רק מספר אחד יכול להיות בתא

זה נותן ארבע אילוצים בסך הכל ולכן 9 x 9 x 4 עמודות במטריצת הכיסוי המדויק:

פרטי סטטי פרטי BOARD_SIZE = 9; פרטית סטטית int SUBSECTION_SIZE = 3; פרטי סטטי פרטי NO_VALUE = 0; פרטי סטטי פרטי CONSTRAINTS = 4; פרטית סטטית int MIN_VALUE = 1; פרטי סטטי פרטי MAX_VALUE = 9; פרטית סטטית int COVER_START_INDEX = 1;

פרטי int getIndex (int שורה, int עמודה, int num) {return (שורה - 1) * BOARD_SIZE * BOARD_SIZE + (עמודה - 1) * BOARD_SIZE + (num - 1); }

בוליאני פרטי [] [] createExactCoverBoard () {בוליאני [] [] coverBoard = בוליאני חדש [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); החזרת כיסוי Board; } אינטראקציה פרטית int checkSubsectionConstraint (בוליאני [] [] coverBoard, int hBase) {עבור (int שורה = COVER_START_INDEX; שורה <= BOARD_SIZE; שורה + = SUBSECTION_SIZE) {עבור (עמודה int = COVER_START_INDEX; עמודה <= BOARD_SIZE; עמודה + = SUBSECT ) {עבור (int n = COVER_START_INDEX; n <= BOARD_SIZE; n ++, hBase ++) {עבור (int rowDelta = 0; rowDelta <SUBSECTION_SIZE; rowDelta ++) {עבור (int columnDelta = 0; columnDelta <SUBSECTION_SIZE; columnDelta ++) {int index = getIndex (שורה + שורהDelta, עמודה + עמודהDelta, n); coverBoard [index] [hBase] = true; }}}}} החזר hBase; } check int intaColumnConstraint (בוליאני [] [] 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 = COVER_START_INDEX; שורה <= BOARD_SIZE; שורה ++) {int index = getIndex (שורה, עמודה, n); coverBoard [index] [hBase] = true; }}} להחזיר hBase; } check intow פרטיRowConstraint (בוליאני [] [] coverBoard, int hBase) {עבור (int שורה = COVER_START_INDEX; שורה <= BOARD_SIZE; r ++) {עבור (int n = COVER_START_INDEX; n <= BOARD_SIZE; n ++, hBase ++) {עבור ( עמודה int = COVER_START_INDEX; עמודה <= BOARD_SIZE; עמודה ++) {int index = getIndex (שורה, עמודה, n); coverBoard [index] [hBase] = true; }}} להחזיר hBase; } int intecCellConstraint פרטי (בוליאני [] [] coverBoard, int hBase) {עבור (int שורה = COVER_START_INDEX; שורה <= BOARD_SIZE; שורה ++) {עבור (int עמודה = COVER_START_INDEX; עמודה <= BOARD_SIZE; עמודה ++, hBase ++) {עבור ( int n = COVER_START_INDEX; n <= BOARD_SIZE; n ++) {int index = getIndex (שורה, עמודה, n); coverBoard [index] [hBase] = true; }}} להחזיר hBase; }

לאחר מכן, עלינו לעדכן את הלוח החדש שנוצר עם פריסת הפאזלים הראשונית שלנו:

פרטי בוליאני [] [] initializeExactCoverBoard (int [] [] board) {בוליאני [] [] coverBoard = createExactCoverBoard (); עבור (int שורה = COVER_START_INDEX; שורה <= BOARD_SIZE; שורה ++) {עבור (int עמודה = COVER_START_INDEX; עמודה <= BOARD_SIZE; עמודה ++) {int n = לוח [שורה - 1] [עמודה - 1]; אם (n! = NO_VALUE) {עבור (int num = MIN_VALUE; num <= MAX_VALUE; num ++) {if (num! = n) {Arrays.fill (coverBoard [getIndex (שורה, עמודה, מספר)], שקר); }}}}} החזר coverBoard; }

אנחנו מוכנים לעבור לשלב הבא עכשיו. בואו ניצור שני שיעורים שיקשרו את התאים שלנו יחד.

4.4. צומת רוקדים

אלגוריתם קישורים רוקדים פועל על פי תצפית בסיסית כי בעקבות פעולה ברשימות צמתים מקושרות כפליים:

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

מסיר את הצומת, בעוד:

node.prev = node node.next = node

משחזר את הצומת.

כל צומת ב- DLX מקושר לצומת בצד שמאל, ימין, למעלה ולמטה.

DancingNode בכיתה יהיו כל הפעולות הדרושות כדי להוסיף או להסיר צמתים:

class DancingNode {DancingNode L, R, U, D; ColumnNode C; DancingNode hookDown (DancingNode node) {assert (this.C == node.C); node.D = this.D; node.D.U = צומת; node.U = זה; this.D = צומת; צומת החזרה; } DancingNode hookRight (צומת DancingNode) {node.R = this.R; node.R.L = צומת; node.L = זה; this.R = צומת; צומת החזרה; } בטל unlinkLR () {this.L.R = this.R; this.R.L = this.L; } בטל relinkLR () {this.L.R = this.R.L = זה; } בטל unlinkUD () {this.U.D = this.D; this.D.U = this.U; } בטל relinkUD () {this.U.D = this.D.U = this; } DancingNode () {L = R = U = D = this; } DancingNode (ColumnNode c) {this (); C = c; }}

4.5. צומת העמודה

ColumnNode הכיתה תקשר בין עמודות:

class ColumnNode מרחיב את DancingNode {int גודל; שם מחרוזת; ColumnNode (String n) {super (); גודל = 0; שם = n; C = זה; } כיסוי בטל () {unlinkLR (); עבור (DancingNode i = this.D; i! = this; i = i.D) {עבור (DancingNode j = i.R; j! = i; j = j.R) {j.unlinkUD (); גודל j.C.--; }}} בטל חשיפה () {עבור (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. פּוֹתֵר

לאחר מכן, עלינו ליצור רשת המורכבת משלנו DancingNode ו ColumnNode חפצים:

ColumnNode פרטי makeDLXBoard (בוליאני [] [] רשת) {int COLS = רשת [0] .length; ColumnNode headerNode = ColumnNode חדש ("כותרת"); רשימת columnNodes = ArrayList חדש (); עבור (int i = 0; i <COLS; i ++) {ColumnNode n = ColumnNode new (Integer.toString (i)); columnNodes.add (n); headerNode = (ColumnNode) headerNode.hookRight (n); } headerNode = headerNode.R.C; עבור (בוליאני [] aGrid: grid) {DancingNode prev = null; עבור (int j = 0; j <COLS; j ++) {if (aGrid [j]) {ColumnNode col = columnNodes.get (j); DancingNode newNode = DancingNode חדש (col); אם (prev == null) prev = newNode; col.U.hookDown (newNode); prev = prev.hookRight (newNode); col.size ++; }}} headerNode.size = COLS; כותרת החזרהNode; }

נשתמש בחיפוש היוריסטי כדי למצוא עמודות ולהחזיר תת קבוצה של המטריצה:

פרטי ColumnNode selectColumnNodeHeuristic () {int min = Integer.MAX_VALUE; ColumnNode ret = null; עבור (ColumnNode c = (ColumnNode) כותרת.R; c! = כותרת; c = (ColumnNode) c.R) {אם (c.size <min) {min = c.size; ret = c; }} להחזיר ret; }

לבסוף, אנו יכולים לחפש רקורסיבית את התשובה:

חיפוש ריק ריק (int k) {if (header.R == header) {handleSolution (תשובה); } אחר {ColumnNode c = selectColumnNodeHeuristic (); c.cover (); עבור (DancingNode r = c.D; r! = c; r = r.D) {answer.add (r); עבור (DancingNode j = r.R; j! = r; j = j.R) {j.C.cover (); } חפש (k + 1); r = answer.remove (answer.size () - 1); c = r.C; עבור (DancingNode j = r.L; j! = r; j = j.L) {j.C.uncover (); }} c.uncover (); }}

אם אין עוד עמודות, נוכל להדפיס את לוח הסודוקו שנפתר.

5. אמות מידה

אנו יכולים להשוות את שני האלגוריתמים השונים על ידי הפעלת אותם על אותו מחשב (בדרך זו אנו יכולים להימנע מהבדלים ברכיבים, מהירות המעבד או ה- RAM וכו '). הזמנים בפועל יהיו שונים ממחשב למחשב.

עם זאת, אנו אמורים להיות מסוגלים לראות תוצאות יחסית, וזה יגיד לנו איזה אלגוריתם פועל מהר יותר.

אלגוריתם Backtracking לוקח בערך 250ms כדי לפתור את הלוח.

אם נשווה זאת עם קישורי הרוקדים, שאורכים כ -50 ms, נוכל לראות מנצח ברור. קישורים לריקודים מהירים פי חמישה יותר כאשר פותרים דוגמה מסוימת זו.

6. מסקנה

במדריך זה דנו בשני פתרונות לפאזל סודוקו עם Java הליבה. האלגוריתם למעקב אחורני, שהוא אלגוריתם כוח-כוח, יכול לפתור את הפאזל הסטנדרטי 9 × 9 בקלות.

נדון גם באלגוריתם Dancing Links המסובך מעט יותר. שניהם פותרים את החידות הקשות ביותר תוך שניות.

לבסוף, כמו תמיד, ניתן למצוא את הקוד ששימש במהלך הדיון ב- GitHub.

streamalism.org