כמו הרבה דברים, גם הטריגר לכתוב תכנה שפותרת סודוקו, בא מהחיים עצמם, כלומר מהילדים. אז כשבא מישהו, לא משנה מי, ואומר לי שהוא צריך עזרה לפתור סודוקו, אחרי עשר דקות אני מבין שעבודה קשה זה לא בשבילי, לעומת זאת – לכתוב משהו שיפתור את זה יקח פחות זמן (לא באמת נכון) ויותר מעניין (החלק הזה באמת נכון).
אם לא מעניין אותך ההסברים, דלג\י ישר לחלק האחרון בו נמצא הקוד.
איך לא עושים את זה
הרעיון הראשון שעלה לי בראש הוא סוג אלימינציה, שזה בגדול אותה דרך שאמא שלי מתחילה ממנה: ניקח את כל התאים הריקים, נשים בהם את כל הערכים האפשריים (בדרך כלל 1-9) ואז נעבור ונוריד מכל תא כל מה שבוודאות לא נכון. זאת אומרת, ערכים שכבר קיימים באותה שורה, באותו טור או באותו ריבוע.
לדוגמא: אם ניקח את התא השמאלי העליון בציור, נתחיל מכך שנבדוק את השורה, באותה שורה כבר מופיעות הספרות '4' ו'5', לכן נוכל למחוק אותן. עכשיו נביט בטור ונראה שהוא מכיל גם את '9', '3' ו- '6', כך שנוכל למחוק גם אותם. לסיום נראה שבאותו הריבוע מופיעים גם '3', '4' ו-'9', אלא שאת אלה כבר מחקנו בשלבים הקודמים ולכן אין צורך לחזור על כך.
באותו אופן, נמשיך לבצע זאת על כל אחד מהתאים הריקים עד סוף המטריצה. בשלב זה אם מצאנו תא שבו יש רק אפשרות אחת, נוכל להניח בוודאות שזהו הערך הנכון.
כעת, יש לנו נתון חדש נוסף וניתן לחזור על כל התהליך מהתחלה ולמחוק עוד ערכים אפשריים.
הבעיה בשיטה הזו היא שבפאזלי סודוקו קלים (כאלה שמראש באים עם הרבה ערכים ידועים) היא עשויה לעבוד. אבל בפעמים שניסיתי אותה הגעתי לשלב בו מיציתי את כל המחיקות האפשריות ועדיין לא פתרתי את כל הסודוקו. מבחינת האלגוריתם, ניתן לזהות את המצב הזה כאשר אנחנו מבצעים מעבר שלם על כל המטריצה ולא הצלחנו לצמצם אף תא נוסף לאפשרות אחת בלבד. במקרה הזה המעבר הבא על המטריצה ישיג בדיוק את אותה התוצאה ולכן גם אם נבצע מעברים נוספים, הם לא יוסיפו שום מידע חדש. באסה
אז איך כן עושים את זה באמצעות בק-טראקינג (backtracking)
בק-טראקינג (backtracking) הוא, למעשה היא, משפחה של פתרונות אלגוריתמיים לבעיות מהסוג בו נדרש למצוא פתרון לבעיה העומד במספר אילוצים (constraints), מה שקרוי בעולם מדעי המחשב constraint satisfaction problem. בדרך כלל הבעיה תהיה מהסוג של איך אפשר לסדר מספר אלמנטים בצורה שתעמוד באילוצים מסויימים, או שתעמוד באילוצים בצורה הטובה ביותר (=אופטימלית). דוגמאות לבעיות מהסוג הזה הן:
- "חידת 8 המלכות" – איך נסדר 8 מלכות על לוח שחמט בצורה כזו שאף מלכה לא "מאיימת" על אחרת. או בגרסה המורחבת – איך נסדר n מלכות על לוח שחמט בגודל nXn בצורה כזו שאף מלכה לא … הבנתם את הרעיון
- מציאת מסלול בתוך לבירנט (מבוך) – או לצורך העניין מציאת המסלול הקצר ביותר ליציאה מהמבוך
- כמובן – סודוקו
איך זה עובד
אם נחשוב על הבעיה בתור שיבוץ n אלמנטים בn מקומות, האלגוריתם עובד ככה:
- ננסה לשבץ אלמנט במקום הראשון.
- בכל פעם שנצליח לשבץ (זאת אומרת שאנחנו עומדים בכל האילוצים עדיין), נעבור למקום הבא ונעשה אותו דבר. אם אנחנו כבר במקום האחרון – זהו, מצאנו.
- אם לא נצליח, ננסה את האלמנט האפשרי הבא.
- אם אין יותר אלמנטים אפשריים, נחזור למקום הקודם וננסה לשבץ שם אלמנט אחר באותו אופן.
ככה שכל פעם שאנחנו נתקלים בבעיה אנחנו מנסים את כל האפשרויות באותה נקודה, ואם אף אחת מהן לא עובדת, אנחנו חוזרים אחורה ככל שנצטרך.
דוגמא
בואו נניח שאנחנו מנסים למצוא רצף המורכב משלושת הסימנים A,B וC בלבד, כאשר האילוצים הם שהרצף צריך להיות (א) באורך 3 סימנים לפחות ו(ב)ההפרש בין כל זוג אותיות צמודות הוא גדול מאפס. קל לראות שהרצף היחיד העונה על כך הוא ABC. אבל לצורך הבנת האלגוריתם, ננסה לפתור זאת באמצעות בק-טראקינג, זאת אומרת, ננסה את כל האפשרויות התקינות עד שנמצא אחת שעונה על כל האילוצים.
בשלב ראשון, נתחיל מלמקם את הסימן הראשון האפשרי (A) במקום הראשון. נקבל את הרצף החלקי A. A הוא אינו פתרון מלא כי הוא לא עונה על דרישה (א), הוא קצר מדי. אבל הוא יכול להיות חלק מפתרון, מקרה כזה נקרא interim checkpoint, נסמן זאת בכתום ונתקדם הלאה.
כעת עלינו למקם סימן במקום השני, שוב נתחיל מהאפשרות הראשונה – A ונקבל את הרצף AA, AA אינו רצף תקין כלל, כי ההפרש בין האותיות הוא אפס, הוא גם לא יכול להיות חלק מפתרון ולכן אנחנו חוזרים צעד אחורה, לinterim checkpoint הקודם.
מה- interim checkpoint הראשון ננסה כעת למקם סימן אחר – B ונקבל את הרצף AB. AB גם הוא אינו פתרון מלא, אבל בניגוד לAA הוא יכול להיות חלק מפתרון מלא ולכן נסמן גם אותו כInterim checkpoint.
כעת ננסה למקם סימן במקום השלישי, כאשר ננסה למקם את A או B נקבל רצף לא תקין, כי הוא לא עונה על דרישה (ב) להפרש בין הסימנים. לכן בכל אחד מהנסיונות האלה נחזור לinterim checkpoint האחרון שהוא AB. בנסיון השלישי נמקם את הסימן C ונקבל את הרצף ABC, ABC עונה על שני האילוצים (א) ו(ב) ולכן הוא פתרון מלא. מכיוון שהגענו לפתרון מלא אנחנו יכולים לעצור כאן והתשובה הנכונה היא ABC.
די פשוט, לא ?
ומה לגבי סודוקו ?
עכשיו שהבנו את הרעיון שמאחורי בק-טראקינג. ננסה ליישם אותו על בעיית הסודוקו. אפשר לגשת לכך במספר דרכים, אך הדרך האינטואיבית ביותר תהיה לעבור בצורה עקבית על פני לוח הסודוקו, מקום ריק אחרי מקום ריק ולנסות לשבץ את אחד האלמנטים האפשריים (בסודוקו של 9X9 מדובר בספרות 1 עד 9).
בכל פעם שננסה לשבץ ספרות במקום ריק נפעל באופן הבא:
- אם הספרה עונה על האילוצים של סודוקו, מדובר בinterim checkpoint ולכן נעבור לשבץ במקום הבא.
- אם הספרה מפרה את אחד האילוצים, ננסה את הספרה הבאה.
- אם ניסינו את כל הספרות ונתקלנו בבעיה, נחזור מקום אחד אחורה ונמשיך שם מהספרה הבאה.
ניקח לדוגמא את הסודוקו הבא: נתחיל מהמקום העליון בצד שמאל. הספרה הראשונה שננסה לשבץ היא 1, כמובן שאי אפשר לעשות זאת כי יש כבר את הספרה 1 בעמודה ולכן נעבור ספרה ספרה עד שנצליח.
באותה צורה לא נצליח לשבץ גם את 2,3 ו-4 מפני שהן קיימות באותה שורה, 5 ו-7 מפני שהן קיימות באותו ריבוע ו6 כי הוא קיים באותה עמודה, לכן הספרה הראשונה שנצליח לשבץ היא 8.
אחרי שיבוץ מוצלח של 8, הספרה 8 היא כעת interim checkpoint. באותו אופן נמשיך ימינה, עם שיבוץ של 1 ו5. במקום החמישי הפנוי, ניתן לראות שלא ניתן לשבץ אף ספרה מ1 עד 9, במצב כזה, אנחנו חוזרים לinterim checkpoint האחרון. שהוא השיבוץ של 5 במקום השלישי הפנוי.
נעצור רגע להבין את ההגיון בשיבוץ במקום השלישי הריק: תחת ההנחה ששיבצנו את 8 ו-1 במקומות הקודמים, אנחנו כבר יודעים שהספרות 1-4 לא מתאימות, אנחנו גם יודעים שכאשר שיבצנו את 5, זה יצר בעיה במקום הבא ולכן גם 5 לא מתאים.
נמשיך לאפשרויות שנותרו במקום השלישי הריק, 6 כבר בשימוש באותו ריבוע ולכן נעבור ל7.
לאחר שיבוץ 7 במקום השלישי ניתן לשבץ את 5 במקום הרביעי הפנוי ו6 במקום הבא. עכשיו יש לנו שיבוץ של השורה הראשונה שהוא בחזקת interim checkpoint. באותו אופן נעבור לשבץ את השורה השנייה משמאל לימין. יש לזכור שהשורה הראשונה אינה השיבוץ הסופי, ולכן עדיין יש אפשרות שנצטרך לחזור כל הדרך אחורה כדי לנסות שיבוצים אחרים בשורה הראשונה.
זה האלגוריתם, בגדול. אם זה עדיין לא ברור אני מציע לחזור אחורה ולקרוא בתשומת לב צעד אחרי צעד כדי לבסס את ההבנה של האלגוריתם. כשזה ברור, אפשר להתקדם לשלב הבא – קידוד.
צוללים לקוד
מתחילים מהסוף
כשניגשתי לבעיה, חשבתי שאולי בעתיד זה יהיה מעניין לעשות מימוש באמצעות דף Web סטטי (סטטי – כל הלוגיקה נמצאת בדף עצמו). לכן מראש החלטתי לכתוב את הקוד בשפת javascript "עטופה" בתוך מחלקה (class) אחת, בצורה כזו יהיה קל יחסית לשלב את הקוד באופן הבא:
// This is a solver for sudoku boards. It uses a backtracking algorithm to find a solution.
class SSolver {
constructor(square_size) {
this.square_size = square_size;
this.board_size = square_size*square_size;
}
// board is a 2 dimentional array with numbers for a known value or 0 for an unknown value
solve(board) {
// this is where the magic happens
return result;
}
המחלקה מקבלת רק פרמטר אחד והוא square_size, גודל הריבוע. תחת ההנחה שתמיד נעבוד עם פאזל ריבועי בו מספר האלמנטים בריבוע הוא גם מספר הריבועים. בהמשך נראה שלא באמת התאמצתי לתמוך בגודל של ריבוע אחר מאשר 3. לדוגמא – הספרות השונות שניתן לשבץ בכל ריבוע הן תמיד 1-9, בלי קשר לגודל הריבוע.
למעשה, הסיבה העיקרית שאני נוטה להשאיר משתנים מהסוג הזה בקוד, למרות חוסר התמיכה בהם, הוא שזה גורם לך לתכנן את הפתרון בצורה כללית יותר (ולדעתי מרגיל אותך להיות מפתח טוב יותר). אפשר גם למצוא בקלות טיעונים נגד הגישה הזו, אבל נניח לעת עתה לדיון הפילוסופי ונתקדם.
הפונקציה היחידה שבאמת נדרשת כלפי חוץ היא הפונקציה solve, הפונקציה מקבלת מערך דו מימדי בגודל המתאים כאשר כל ספרה קיימת מיוצגת כמספר ו0 מייצג מקום ריק.
פונקציות שירות
העברה של אובייקטים בין פונקציות בג'אווסקריפט היא נושא עדין, בניגוד למספרים ומחרוזות שהם בהגדרה לא-ניתנים לשינוי (נקראים immutables) מערכים ורוב האובייקטים האחרים ניתנים לשינוי על ידי הפונקציה הנקראת. על קצה המזלג – כאשר מעבירים מערך כפרמטר לפונקציה, כל שינוי במערך המבוצע בתוך הפונקציה ישפיע גם על הקוד מחוץ לפונקציה. למי שהקונספט הזה חדש כדאי להתעמק ולקרוא על Object References. נושא ראוי לפוסט בפני עצמו. לעניינינו – ראיתי לא מעט מימושים של backtracking שעובדים עם מבנה נתונים יחיד, זה אפשרי, זה גם יעיל יותר מבחינת ביצועים וצריכת זכרון, אבל אני במקרה הזה בחרתי ללכת על הגישה הבטוחה של שכפול הלוח לפני שינויים, לצורך הזה כתבתי את הפונקציה getClone המקבלת לוח ומחזירה העתק מלא (deep copy) של הלוח, ככה שכל שינוי בלוח החדש לא משפיע על הלוח המקורי, למזלנו הspread operator (שלוש נקודות) של ג'אווסקריפט מאפשר לעשות את זה בקלות:
getClone(board){
return board.map(row => [...row]);
}
נזכיר: הלוח ממומש בתור רשימה דו-מימדית, או יותר מדוייק, רשימה של רשימות, כאשר כל אלמנט ברשימה החיצונית מייצג שורה בתור רשימה פנימית המייצגת את כל התאים באותה שורה בלוח.. הפונקציה map עוברת על רשימת השורות ומחזירה במקום כל שורה העתק של אותה שורה, זאת בעזרת הspread operator (שלוש נקודות) שפורש לתוך מערך חדש את כל האלמנטים בrow.
פונקצית השירות הבאה שנצטרך היא getNextPosition, שמקבלת זוג קואורדינטות בלוח – col ו- row ומחזירה tuple* של הקואורדינטה הבאה בתור, די טריוויאלי:
*אוקי, אין באמת tuple בשפת ג'אווסקריפט, זה פשוט מערך עם שני אלמנטים.
getNextPosition(col, row){
col++;
if (col === this.board_size){
col = 0;
row++;
}
return [col, row];
}
לב האלגוריתם
לב האלגוריתם בנוי משתי פונקציות פשוטות למדי, הראשונה היא isValidAssignment, הפונקציה מקבלת לוח וקואורדינטות ובודקת האם ההשמה בקואורדינטות האלה חוקית.
נשים לב שבעצם בגלל שאנחנו בודקים כל פעם את החוקיות של השמה אחת בלבד, מספיק לבדוק רק את השורה, טור והריבוע הרלוונטי שכן השמה יכולה ליצור קונפליקט רק באחד משלושתם.
כמו כן – הקונפליקט היחיד שיכול להווצר מהשמה של ספרה מסויימת הוא שהספרה כבר קיימת באותה שורה, טור או ריבוע.
משהו כללי על מבנה של פונקציות מהסוג isValid: יש אסכולה שאומרת שreturn באמצע פונקציה זה רעיון רע. אני לא שייך לאסכולה הזו. אבל כמו שאמר דוד בן – With great power comes great responsibility. אז אני לגמרי בעד לכתוב פונקציות מהסוג הזה עם return באמצע הפונקציה, אבל הנה שתי המלצות כשעושים את זה:
1. קוד קצר, כזה שאפשר "לתפוס" במבט בודד את כל תנאי היציאה מהפונקציה.
2. המבנה בדרך כלל יהיה כזה
- בדיקה ראשונה – אם התוצאה חיובית – החזר כשלון (False)
- בדיקה שנייה – אם התוצאה חיובית – החזר כשלון (False)
- …
- אם הגענו עד לכאן, הכל טוב, החזר הצלחה (True)
ישנו גם מקרה הפוך – סדרת בדיקות שכל אחת מהן היא הצלחה וברירת המחדל היא כשלון. גם הוא מוצלח לטעמי אבל פחות בשימוש. בכל מקרה – עדיף להמנע מלערבב בדיקות הצלחה ובדיקות כשלון באותו מבנה, זה פוגע בקְרִיאוּת (readability) ומוביל לבאגים.
isValidAssignment(board, col, row){
let val = board[row][col];
// check row and col
for (let i = 0; i < this.board_size; i++){
if (i !== col && board[row][i] === val)
return false;
if (i !== row && board[i][col] === val)
return false;
}
// check square
const squareRow = Math.floor(row / this.square_size) * this.square_size ;
const squareCol = Math.floor(col / this.square_size) * this.square_size ;
for (let i = 0; i < this.square_size; i++){
for (let j = 0; j < this.square_size; j++){
if ((squareRow + i !== row || squareCol + j !== col) && board[squareRow + i][squareCol + j] === val)
return false;
}
}
return true;
}
הסבר: בחלק הראשון אנחנו משתמשים בלולאת for "רגילה" כדי לבדוק במקביל גם את העמודה (שורה 5) ואת השורה (שורה 7). בכל עמודה\שורה אנחנו בודקים: א. שזה לא השורה\העמודה הנוכחיים וב. האם הערך הוא אותו ערך (val) שכרגע אנחנו מוסיפים (כפי שמצאנו בשורה 2). במקרה ושני התנאים נכונים – מצאנו שהערך הזה כבר קיים בעמודה\שורה ולכן נחזיר כשלון (False)
בחלק השני אנחנו מחשבים את הקואורדינטות של המקום הימני העליון בריבוע שאותו אנחנו בודקים (שורות 12-13), כעת אנחנו עוברים בלולאת for מקוננת על כל הקואורדינטות של הריבוע ובודקים: א. האם זה לא השורה ועמודה שבהם הצבנו ערך כרגע. ב. האם הערך במקום הזה שווה לערך שהצבנו (חושב בשורה 2) . גם כאן – אם שתי הבדיקות (שורה 17) חיוביות משמע מצאנו מקום אחר באותו ריבוע שכבר מכיל את הערך החדש. ולכן נחזיר כשלון (False)
אם הגענו לשורה 22, כאמור, זה אומר שאין קונפליקט באותה שורה, אותה עמודה או אותו ריבוע ולכן ההצבה תקינה – נחזיר הצלחה (True)
פונקציית הרקורסיה
עכשיו באמת הגענו לעיקר: מימוש backtracking באמצעות רקורסיה.
הפונקציה tryOption מקבלת לוח סודוקו מלא עד נקודה מסויימת (זהו הinterim checkpoint במושגי backtracking) ומנסה למצוא פתרון,
אם היא מוצאת פתרון היא תחזיר אותו, אחרת היא תחזיר Null.
tryOption(board, col, row){
const current_board = board;
// we got to the end of the board and some, so we have a solution
if (row === this.board_size){
return current_board;
}
// if this position is already set, move to the next one
if (board[row][col] !== 0){
const [next_col, next_row] = this.getNextPosition(col, row);
return this.tryOption(current_board, next_col, next_row);
}
for (let attempted = 1; attempted < 10; attempted++){
const attempted_board = this.getClone(current_board);
attempted_board[row][col] = attempted;
if (!this.isValidAssignment(attempted_board, col, row))
continue;
const [next_col, next_row] = this.getNextPosition(col, row);
const res = this.tryOption(attempted_board, next_col, next_row);
// if a solution found, return it
if (res !== null)
return res;
}
return null;
}
בתוך הפונקציה נטפל בשלושה מקרים עיקריים:
מקרה ראשון – הגענו לסוף הלוח
אם הפונקציה תקרא עבור שורה שאינה קיימת (row == this.board_size) סימן שהגענו לסוף הלוח, ואז ניתן להניח שהפתרון שבידינו הוא הפתרון הנכון, ולכן נחזיר אותו.
מקרה שני – הגענו למקום "תפוס"
במקרה זה יש כבר מספר במקום הנוכחי, היות ואין מה לבדוק לגביו, פשוט נעבור למקום הבא.
מקרה שלישי – כל השאר
זהו עיקר הרקורסיה. החלק של הפתרון שמילאנו עד כה הוא תקין, אבל יכול להיות שאי אפשר להגיע ממנו לפתרון מלא.
כדי לבדוק אם ניתן להגיע לפתרון מלא, ננסה את כל הערכים האפשריים (בדרך כלל 1-9). עבור כל אחד מהם נפעל באופן הבא:
אם לא – נעבור לערך הבא
היות ואנחנו מחפשים פתרון יחיד לסודוקו, ברגע שtryOption מחזיר פתרון כלשהו, למעשה הגענו לסוף האלגוריתם ופשוט נחזיר את הפתרון במעלה שרשרת הקריאות.
אם אף אחד מהערכים לא הוביל לפתרון, אנחנו יודעים שאין פתרון עבור הלוח החלקי הנוכחי, נחזיר Null, המסמן לפונקציה הקוראת שלמעשה אין אף פתרון תקין בהמשך הדרך.
למה זה עובד ?
בדיוק כמו ההסבר בתחילת הפוסט, בכל נקודה בזמן יש לאלגוריתם פתרון חלקי תקין (interim checkpoint), שממנו הוא מנסה להתקדם לפתרון מלא, אם לא ניתן להגיע לפתרון מלא ממנו, הוא נפסל ואנחנו חוזרים לinterim checkpoint הקודם. היות ואנחנו מנסים את כל האפשרויות התקינות, בסופו של דבר נגיע לסדרה של interim checkpoints שמייצגת את הפתרון המלא.
סיכום
בקטראקינג (back-tracking) הוא טכניקה לפתרון של בעיות מהסוג של עמידה באילוצים (constraints). זו אינה הטכניקה המהירה או היעילה ביותר לפתור בעיות מסוג זה. אבל היא פשוטה למימוש וקלה להבנה.