פתרון חידת 8 המלכות בתכנות מונחה עצמים והגדרת הלוח (Board)
כיצד אנחנו מחליפים פונקציה פרוצדורלית מרכזית בסימולציה מבוזרת שבה כל מלכה היא עצם עצמאי בעמודה בלעדית, וכיצד המחלקה Board מאתחלת את שרשרת המלכות ומזניקה את החיפוש אחרי כל 92 הפתרונות.
מודל מנטלי ועיקרון מנחה: ביזור האחריות – קהילה של 8 מלכות שמנהלות משא ומתן בהודעות!
במקום "במאי רודן" (פונקציה פרוצדורלית) שמזיז בובות דוממות על מערך דו-ממדי, אצלנו כל מלכה היא שחקנית חיה ואוטונומית שמקבלת עמודה כנחלתה הבלעדית ומנהלת משא ומתן עם שכנתה משמאל רק על השורה שתתפוס!
הלוח (Board) אינו יודע לחשב איומים ואינו מכיר את כל 8 המלכות! יש לו משתנה מופע יחיד בלבד (lastQueen) המצביע על המלכה הימנית ביותר (עמודה 8), וכל התקשורת עוברת דרכה בשרשרת.
האתחול (initialize) בונה רשימה מקושרת שבקצה השמאלי שלה ניצבת "מלכה מנוונת" (QueenTerminator), והמתודה solve שולפת בלולאה את כל 92 הפתרונות באמצעות firstSolution ו-nextSolution.
1. מהפכת הסימולציה: איך חושבים על חידת 8 המלכות בתכנות מונחה עצמים?
מעבר מניהול מרכזי של מערך ולולאות נסיגה (Backtracking) לעצמים אוטונומיים המדברים בהודעות
בוא נפתח יחד את הפרק המרתק הזה בשאלה פשוטה: איך פותרים בדרך כלל את חידת 8 המלכות בתכנות פרוצדורלי מסורתי? בגישה הפרוצדורלית יש לנו פונקציה מרכזית אחת ש"יודעת הכל" — היא מחזיקה מערך מרכזי, מנהלת בעצמה לולאות מקוננות ומבצעת נסיגה לאחור (Backtracking) בכל פעם שמתגלה התנגשות.
אבל בתכנות מונחה עצמים אנחנו חושבים אחרת לגמרי! הפתרון מונחה העצמים שלנו ממדל את הבעיה כסימולציה שבה כל אחת מ-8 המלכות מיוצגת באמצעות עצם (Object) עצמאי ואוטונומי. כל מלכה מקבלת עמודה משלה בלוח השחמט כנחלתה הבלעדית (מבלי לפגוע בכלליות הפתרון, שכן ממילא אסור לשתי מלכות לעמוד באותה עמודה!). המשא ומתן לפתרון החידה מתנהל אך ורק באמצעות שליחת הודעות בין העצמים, כשהמלכות דנות ביניהן רק לגבי השורה שכל אחת מהן תתפוס בעמודה שלה כדי שלא יאיימו זו על זו.
2. המעטפת החיצונית: המחלקה Board והרצת החידה
איך מפעילים את הפתרון ב-Workspace, מה תפקידו של המשתנה lastQueen, ואיך נראה הפלט ב-Transcript?
לצד המלכות, אנו מגדירים עצם המייצג את לוח השחמט עצמו — המחלקה Board. היא משמשת כמעטפת החיצונית שמאתחלת את שרשרת המלכות ומזניקה את תהליך החיפוש.
כדי לקבל את כל פתרונות החידה, כל מה שאנחנו צריכים להריץ בחלון ה-Workspace הוא שתי שורות קוד קצרות ונקיות:
board := Board new initialize. board solve
אנחנו יוצרים מופע חדש של Board, מאתחלים אותו באמצעות ההודעה initialize, ושולחים אליו את ההודעה solve.
Object subclass: #Board
instanceVariableNames: 'lastQueen'
classVariableNames: ''
poolDictionaries: ''
category: 'OOD-8Queens'
שים לב: למחלקה Board (היורשת מ-Object) יש משתנה מופע יחיד בלבד בשם lastQueen המצביע על המלכה האחרונה (הימנית ביותר, בעמודה 8)!
3. צלילה לעומק הקוד של הלוח: המתודות initialize ו-solve
איך בונים רשימה מקושרת של 8 מלכות עם QueenTerminator, ואיך שולפים את כל 92 הפתרונות?
בוא נבחן כעת מקרוב את שתי המתודות של המחלקה Board ונבין כל שורת קוד בהן:
איך הלוח בונה את שרשרת המלכות?
האתחול יוצר רשימה מקושרת של 8 מלכות:
1. תחילה נוצר עצם מסוג QueenTerminator (מלכה "מנוונת" המשמשת כתנאי עצירה בקצה השמאלי) ומושם לתוך lastQueen.
2. לאחר מכן, בלולאה הרצה מ-1 עד 8, נוצרת בכל איטרציה מלכה חדשה (Queen new) בעמודה i, ששכנתה משמאל (neighbor) היא המלכה שנוצרה לפניה (באמצעות ההודעה setColumn: i neighbor: lastQueen), ו-lastQueen מתעדכן להצביע על המלכה החדשה.
3. בסיום הלולאה, lastQueen מצביע על המלכה בעמודה 8, שמצביעה למלכה 7, וכן הלאה עד למלכה 1 שמצביעה ל-QueenTerminator!
איך הלוח מבקש פתרונות מ-lastQueen?
1. המתודה מנקה את חלון ה-Transcript (Transcript clear).
2. הלוח פונה ישירות אל lastQueen בלבד ושולח אליה את ההודעה firstSolution.
3. אם נמצא פתרון ראשון (ifTrue:): הוא מדפיס את הפתרון ע"י המרת התוצאה למחרוזת (lastQueen result printString), ונכנס ללולאת whileTrue: המבקשת שוב ושוב פתרון נוסף (lastQueen nextSolution) ומדפיסה אותו עד למיצוי כל 92 הפתרונות, ובסיום מדפיסה 'End of Solutions.'.
4. אם לא נמצא פתרון ראשון (ifFalse:): מודפסת ההודעה 'No Solution.'.
OrderedCollection ( 1 5 8 6 3 7 2 4 ) OrderedCollection ( 1 6 8 3 7 4 2 5 ) OrderedCollection ( 1 7 4 6 8 2 5 3 ) ... End of Solutions.
כל שורת פלט מייצגת פתרון חוקי שלם: למשל בפתרון הראשון OrderedCollection ( 1 5 8 6 3 7 2 4 ), מלכה 1 בשורה 1, מלכה 2 בשורה 5, מלכה 3 בשורה 8, מלכה 4 בשורה 6, מלכה 5 בשורה 3, מלכה 6 בשורה 7, מלכה 7 בשורה 2 ומלכה 8 בשורה 4.
initializeהלוח מצביע רק ל-lastQueen (עמודה 8), וכל מלכה מצביעה לשכנתה משמאל עד ל-QueenTerminator
מיני-סימולציה 15.1: מנתח שורות הקוד של המחלקה Board
סימולטור אתחול שרשרת המלכות (initialize) והרצת פתרונות ב-solve
לחץ על "צעד הבא באתחול" כדי לראות צעד-אחר-צעד כיצד המתודה initialize יוצרת תחילה את ה-QueenTerminator ואז מוסיפה את מלכות 1 עד 8 בשרשרת מקושרת. לאחר השלמת השרשרת, לחץ על "הרץ board solve" כדי להציג את הפתרונות על לוח השחמט וב-Transcript!
lastQueen):
שלב אתחול: QueenTerminator
הגשר הנרטיבי: הבנו איך הלוח בונה את שרשרת המלכות ומזניק את החיפוש – אבל ממה בנוי העצם Queen עצמו?
ראינו שהלוח (Board) בסך הכל יוצר 8 מופעים של המחלקה Queen ושולח ל-lastQueen את ההודעות firstSolution, nextSolution ו-result.
אבל איזה מידע פנימי מחזיקה כל מלכה בתוכה? ואיך מחולק פרוטוקול ההודעות שלה בין הודעות ציבוריות (ממשק חיצוני) לבין הודעות תקשורת פנימיות בין המלכות? בוא נעבור ליחידה 15.2 ונגלה!
הגדרת המחלקה Queen ופרוטוקול ההודעות שלה
שלושת משתני המופע של כל מלכה (row, column, neighbor) והחלוקה הארכיטקטונית של הפרוטוקול להודעות חיצוניות (ממשק ציבורי) ולהודעות תקשורת פנימיות בין המלכות.
מודל מנטלי ועיקרון מנחה: ידע מקומי מינימלי ופרוטוקול תקשורת מוגדר היטב
כל מלכה יודעת רק שלושה דברים בעולם: באיזו עמודה קבועה היא חיה (column), באיזו שורה היא מנסה לעמוד כרגע (row), ומי היא השכנה הישירה שלה משמאל (neighbor)!
מלכה לעולם אינה מחזיקה מערך של כל הלוח: השכנה הישירה שלה משמאל (neighbor) מייצגת עבורה את כל קבוצת המלכות השמאליות גם יחד!
פרוטוקול המלכה מחולק ל-4 הודעות חיצוניות (ציבוריות) לניהול החיפוש והפתרון, ול-3 הודעות תקשורת פנימיות לתיאום מיקומים ובדיקת איומים בין המלכות.
1. המבנה הפנימי של מלכה: הגדרת המחלקה Queen ושלושת משתני המופע
איזה מידע שומרת כל מלכה לעצמה לאורך ריצת הסימולציה?
עכשיו בוא נסתכל לתוך הלב של כל מלכה על הלוח. המחלקה Queen יורשת מ-Object ומייצגת מלכה אמיתית הפועלת על גבי לוח השחמט.
כמה משתני מופע (Instance Variables) לדעתך מלכה צריכה כדי להשתתף בחיפוש הפתרון? מתברר שדי לה בשלושה משתני מופע בלבד:
Object subclass: #Queen
instanceVariableNames: 'row column neighbor'
classVariableNames: ''
poolDictionaries: ''
category: 'OOD-8Queens'
מספר העמודה הקבוע שהוקצה למלכה זו (מ-1 עד 8). נקבע באתחול ואינו משתנה לעולם.
מספר השורה הנוכחי (1 עד 8) שבו המלכה מנסה למקם את עצמה מבלי להיות מאוימת ע"י חברותיה.
מצביע למלכה השכנה משמאל ברשימה המקושרת (או ל-QueenTerminator עבור המלכה הראשונה בעמודה 1).
2. פרוטוקול ההודעות של המלכה: ממשק ציבורי מול תקשורת פנימית
7 ההודעות שמרכיבות את כל יכולות הפעולה והמשא ומתן של המחלקה Queen
כמו בכל עיצוב מונחה עצמים משובח, אנו מגדירים את הפרוטוקול (אוסף ההודעות) שהמלכה יודעת להגיב אליו, ומחלקים אותו לשתי קבוצות לוגיות ברורות:
🌐 א. הודעות חיצוניות (ציבוריות – ממשק לניהול הפתרון)
setColumn:neighbor:— אתחול מספר העמודה וקישור למלכה השכנה הסמוכה משמאל.firstSolution— בקשה למציאת פתרון חוקי ראשון לחידה.nextSolution— בקשה למציאת פתרון חוקי נוסף (הבא בתור).result— איסוף והחזרת רשימת השורות של הפתרון הנוכחי לצורך הדפסה.
🔄 ב. הודעות תקשורת פנימית בין המלכות
advance— מבקשת מהמלכה להתקדם למשבצת הבאה באותה עמודה באופן ציקלי (ומפעילה נסיגה אם הגיעה לקצה).moveToNextNonAttackedRow— מבקשת מהמלכה להתקדם בעמודה שלה עד למשבצת בטוחה שאינה מאוימת ע"י מלכות אחרות.canAttack:x:— מבקשת מהמלכה לבדוק האם משבצת מסוימת (שורה ועמודה) מאוימת על ידה או על ידי אחת משכנותיה משמאל.
Queenמשתני המופע הפנימיים (State) ופרוטוקול 7 ההודעות (Behavior)
מיני-סימולציה 15.2: סייר הפרוטוקול ומשתני המופע של Queen
חוקר העצמים החי (Object Inspector): בחר מלכה בשרשרת ובחן את המצב והפרוטוקול שלה
בחר כל אחת מ-8 המלכות על הלוח (בפתרון הראשון 1 5 8 6 3 7 2 4) כדי לפתוח עבורה Smalltalk Inspector המציג את שלושת משתני המופע שלה ואת ההודעות שניתן לשלוח אליה:
הגשר הנרטיבי: הכרנו את משתני המופע והפרוטוקול של המלכה – איך ממומשות בפועל 4 המתודות החיצוניות שלה?
כעת, כשאנחנו יודעים שלכל מלכה יש row, column ו-neighbor, הגיע הזמן לפתוח את דפדפן הקוד ולראות איך כתובות ב-Smalltalk ארבע המתודות הציבוריות של המלכה: setColumn:neighbor:, firstSolution, nextSolution ו-result.
מדוע firstSolution מחזירה ערך בוליאני (true/false) ולא את הפתרון עצמו? למה משתמשים ב-and: בתוך nextSolution? ולמה חייבים את ההודעה yourself בסוף המתודה result? בוא נעבור ליחידה 15.3!
מימוש התנהגות המלכה: הפרוטוקול החיצוני
ניתוח מעמיק של ארבע המתודות הציבוריות של המלכה: setColumn:neighbor:, firstSolution, nextSolution (עם האופרטור העצל and:) ו-result (עם שרשור addLast: row; yourself).
מודל מנטלי ועיקרון מנחה: הפרדה בין מציאת הפתרון (בוליאני) לבין איסוף הפתרון (רשימה)
לפני שמלכה בעמודה i מנסה בכלל למצוא לעצמה שורה ב-firstSolution, היא פונה לשכנתה משמאל ואומרת לה: "תסתדרו קודם אתן!". רק אחרי שכל השכנות משמאל מצאו סידור חוקי, היא נעמדת בשורה 1 ומתחילה לחפש מקום בטוח.
המתודות firstSolution ו-nextSolution מחזירות ערך בוליאני בלבד (true או false) ולא את הפתרון עצמו! איסוף מיקומי השורות מתבצע רק לאחר שנמצא פתרון, באמצעות המתודה הנפרדת result.
במתודה nextSolution נעשה שימוש בהודעה העצלה and: [...] כדי לעצור מיד את החיפוש אם אין יותר פתרונות, ובמתודה result משתמשים ב-yourself כדי להחזיר את האוסף כולו ולא את האיבר הבודד שנוסף!
1. אתחול וחיפוש פתרון ראשון: setColumn:neighbor: ו-firstSolution
איך המלכה מתאתחלת ואיך היא מתאמת את הפתרון הראשון מול שכנותיה משמאל?
בוא נצלול כעת אל המימוש של ארבע המתודות החיצוניות של המחלקה Queen. נתחיל בשתיים הראשונות — המתודה שמאתחלת את המלכה והמתודה שמוצאת את הפתרון החוקי הראשון:
המתודה setColumn:neighbor:
המימוש הוא מיידי וישיר: המתודה מקבלת את מספר העמודה (aColumn) ואת המצביע למלכה השכנה משמאל (aQueen), ושומרת אותם במשתני המופע column ו-neighbor.
💡 דגש חשוב: מרגע האתחול, ערכים אלה משמשים כקבועים לאורך כל ריצת התוכנית ואין עוד לשנות את ערכם!
המתודה firstSolution
ההיגיון האלגוריתמי:
1. המלכה מבקשת קודם כל משכנתה משמאל למצוא פתרון חוקי ראשון עבור כל המלכות שמשמאלה (neighbor firstSolution).
2. לאחר שהשכנות משמאל הסתדרו, המלכה מציבה את עצמה בשורה הראשונה של העמודה שלה (row := 1).
3. היא שולחת לעצמה את ההודעה self moveToNextNonAttackedRow כדי להתקדם לשורה שבה אינה מאוימת ע"י אף אחת משכנותיה (אם שורה 1 כבר בטוחה, היא תישאר בה).
💡 שני דגשים קריטיים להבנת firstSolution:
- הערך המוחזר הוא בוליאני בלבד: המתודה מחזירה עצם בוליאני (
trueאם נמצאה שורה ללא איום, אוfalseאם לא נמצא פתרון) — היא אינה מחזירה את הפתרון עצמו! - השכנה כנציגת הקבוצה כולה: כל מלכה מדברת אך ורק עם שכנה אחת בלבד (
neighbor), ולא עם כל 8 המלכות! השכנה הזו מייצגת עבורה את קבוצת כל המלכות השכנות שמשמאלה גם יחד (גם אם מדובר במלכה 8 שיש לה 7 שכנות משמאל).
2. חיפוש הפתרון הבא ואיסוף התוצאה: nextSolution ו-result
השימוש בתחביר העצל and: לעצירת החיפוש, ושרשור ההודעות addLast: row; yourself באיסוף הרשימה
המתודה nextSolution והאופרטור העצל and:
כדי לעבור מהפתרון הנוכחי לפתרון חוקי חדש, המלכה חייבת תחילה לזוז מהמשבצת שבה היא עומדת כרגע! לכן:
1. היא מתקדמת צעד אחד לשורה הבאה באמצעות self advance.
2. אם נותרו עדיין אפשרויות (advance החזיר true), היא מנסה שוב לחפש שורה שאינה מאוימת (self moveToNextNonAttackedRow).
דגש תחבירי (and:): השימוש בהודעה העצלה (Short-circuit) and: [self moveToNextNonAttackedRow] מיועד לעצור מיד את החיפוש אם אין יותר פתרונות (אם advance החזיר false, הבלוק בסוגריים המרובעים כלל לא יופעל ויוחזר false!).
המתודה result ומדוע חייבים ; yourself?
מופעלת כאשר נמצא פתרון שלם:
1. המלכה פונה לשכנתה משמאל (neighbor result) כדי לקבל את האוסף (OrderedCollection) המכיל את מספרי השורות של כל המלכות הקודמות.
2. היא מוסיפה לסוף הרשימה את מספר השורה שלה באמצעות addLast: row.
למה חייבים ; yourself? ב-Smalltalk, המתודה addLast: row מחזירה את האיבר שנוסף (המספר row) ולא את האוסף! לכן משרשרים בנקודה-פסיק (Cascade) את ההודעה yourself אל האוסף, כך שהמתודה result תחזיר את האוסף המלא כולו!
השוואת מנגנון firstSolution, nextSolution ושרשור האוסף ב-result
מיני-סימולציה 15.3: מעבדת "מה היה קורה אילו?" על הקוד של סעיף 15.3
סימולטור בניית התוצאה הרקורסיבית: ^ neighbor result addLast: row; yourself
כאשר הלוח מבקש lastQueen result, ההודעה צוללת שמאלה מ-Queen 8 עד ל-QueenTerminator (שמחזיר OrderedCollection new ריק), ואז בחזרה ימינה כל מלכה מוסיפה לסוף הרשימה את ה-row שלה ומחזירה yourself! צעד קדימה וראה את הרשימה נבנית מול עיניך:
הגשר הנרטיבי: הבנו את הממשק החיצוני – אבל איך פועלות מתודות התקשורת הפנימיות advance, moveToNextNonAttackedRow ו-canAttack:x:?
ראינו שגם firstSolution וגם nextSolution נעזרות במתודות הפנימיות advance ו-moveToNextNonAttackedRow.
איך בדיוק מתבצעת הנסיגה לאחור (Backtracking) כשמלכה מגיעה לשורה 8 ועדיין מאוימת? ואיך פועלת הנוסחה המתמטית של canAttack: testRow x: testColumn שבודקת שורות ואלכסונים? בוא נעבור ליחידה 15.4 ונראה את הקסם בפעולה!
מתודות התקשורת הפרטיות בין המלכות ובדיקת איומים
איך ממומש מנגנון הנסיגה הציקלי במתודה advance, לולאת החיפוש במתודה moveToNextNonAttackedRow, והגיאומטריה המדויקת של בדיקת האיומים ב-canAttack: testRow x: testColumn.
מודל מנטלי ועיקרון מנחה: נסיגה מבוזרת (Backtracking) כבקשת עזרה מהשכנה משמאל!
תחשוב על advance כמו על מד אוץ (קילומטראז') של מכונית: כשגלגל השיניים הימני מגיע מ-8 חזרה ל-1, הוא מסובב שן אחת בגלגל שמשמאלו (neighbor nextSolution) ומתאפס בעצמו לשורה 1!
ב-canAttack: testRow x: testColumn בודקים רק 3 איומים: אותה שורה (row = testRow), אלכסון עולה (row + columnDifference = testRow) ואלכסון יורד (row - columnDifference = testRow). אין צורך לבדוק עמודה כי לכל מלכה עמודה ייחודית מראש!
אם המלכה הנוכחית אינה מאיימת על המשבצת הנבדקת, היא מעבירה את השאלה הלאה במורד השרשרת אל שכנתה משמאל: ^ neighbor canAttack: testRow x: testColumn.
1. מנגנון הנסיגה והחיפוש בעמודה: advance ו-moveToNextNonAttackedRow
איך המלכה מתקדמת באופן ציקלי בעמודה שלה ואיך היא מבקשת משכנותיה למצוא סידור אחר כשהגיעה לשורה 8?
בוא נבין עכשיו איך הקסם של הנסיגה לאחור (Backtracking) מתרחש בלי שום פונקציית רקורסיה מרכזית, אלא מתוך דיאלוג בין שתי מתודות קצרות להפליא: advance ו-moveToNextNonAttackedRow:
המתודה advance (מנגנון ה-Backtracking)
תפקידה של advance לקדם את המלכה למשבצת הבאה בעמודה שלה באופן ציקלי:
• בדיקת קצה הלוח (row = 8): אם המלכה כבר הגיעה לשורה השמינית ולא מצאה מנוחה, מוצו כל אפשרויותיה בעמודה זו בסידור הנוכחי! לכן היא פונה לשכנתה משמאל ומבקשת ממנה לעבור לפתרון הבא שלה (neighbor nextSolution).
• אם השכנות נכשלו (ifFalse: [^ false]): המלכה "מתייאשת" ומחזירה מיד false.
• אם השכנות הצליחו: המלכה מאפסת את השורה ל-row := 0, כדי שבשורה הבאה בקוד (row := row + 1) היא תתמקם מחדש בשורה 1 ותחזיר true!
המתודה moveToNextNonAttackedRow
המתודה הזו פועלת בלולאת whileTrue: פשוטה ובהירה:
• כל עוד השכנה משמאל (או אחת המלכות שלפניה) מאיימת על מיקומה הנוכחי של המלכה (כלומר neighbor canAttack: row x: column מחזיר true), המלכה מתקדמת צעד אחד באמצעות self advance.
• אם תוך כדי ההתקדמות מוצו כל האפשרויות בלוח ו-self advance החזיר false, המתודה כולה נכשלת ומחזירה מיד ^ false.
• ברגע שנמצאה משבצת שבה canAttack:x: מחזיר false (משבצת בטוחה ללא איום), הלולאה מסתיימת והמתודה מחזירה ^ true!
2. סעיף 15.4.3: בדיקת האיומים – המתודה canAttack: testRow x: testColumn
הגיאומטריה של הפרש העמודות (columnDifference), שלוש משוואות האיום, והעברת השאלה בשרשרת
ועכשיו נגיע לשאלה המתמטית היפה ביותר בפרק: איך מלכה שעומדת במשבצת (row, column) יודעת אם היא מאיימת על משבצת אחרת בקואורדינטות (testRow, testColumn)?
בוא נקרא יחד את הקוד של canAttack: testRow x: testColumn ונבין את המשוואות שלו:
canAttack: testRow x: testColumn | columnDifference | columnDifference := testColumn - column. ((row = testRow or: [row + columnDifference = testRow]) or: [row - columnDifference = testRow]) ifTrue: [^ true]. ^ neighbor canAttack: testRow x: testColumn
📐 ניתוח מתמטי של שלושת תנאי האיום:
תחילה מחשבים במשתנה המקומי columnDifference את מרחק העמודות: testColumn - column. כעת נבדקים 3 תנאי איום ישירים של המלכה הנוכחית על המשבצת (testRow, testColumn):
- איום באותה שורה:
row = testRow - איום באלכסון ראשון (עולה):
row + columnDifference = testRow - איום באלכסון שני (יורד):
row - columnDifference = testRow
💡 מדוע לא בודקים איום באותה עמודה (column = testColumn)? משום שלכל מלכה מוקצית מראש עמודה ייחודית משלה!
🔄 אם אף אחד מ-3 התנאים אינו מתקיים, המלכה מעבירה את השאלה בשרשרת לשכנתה משמאל: ^ neighbor canAttack: testRow x: testColumn.
canAttack:x: ומנגנון הנסיגה ב-advanceחישוב columnDifference בשלושת צירי האיום, ובקשת neighbor nextSolution בשורה 8
מיני-סימולציה 15.4: מחשבון משוואות האיום של canAttack: testRow x: testColumn
מעבדת רדאר האיומים (canAttack:x:) ודיבגר הנסיגה (advance & nextSolution)
לפניך לוח שבו מוצבות 3 המלכות הראשונות בעמודות 1, 2 ו-3 (בשורות 1, 5, 8), ומלכה 4 בעמודה 4 מחפשת שורה בטוחה!
לחץ על כל שורה בעמודה 4 כדי להפעיל את רדאר האיומים לאורך השרשרת, או לחץ על "הדגם נסיגה (Backtracking) בשורה 8" כדי לראות מה קורה כשמלכה מגיעה לשורה 8 ומבקשת neighbor nextSolution!
הגשר הנרטיבי: כל מלכה פונה לשכנתה משמאל – אבל מי היא השכנה של המלכה הראשונה בעמודה 1?
שים לב לדבר מדהים: בכל המתודות שראינו (firstSolution, advance, moveToNextNonAttackedRow, canAttack:x: ו-result), המלכה שולחת הודעות ל-neighbor בלי לבדוק אף פעם neighbor isNil!
איך זה ייתכן שהמלכה הראשונה (בעמודה 1, שאין לה מלכה אמיתית משמאלה) לא מתרסקת בשגיאה? התשובה טמונה בעצם הגאוני QueenTerminator — ובוא נעבור ליחידה 15.5 כדי להכיר אותו!
חסימת התנאים ומניעת סרבול קוד: המחלקה QueenTerminator
כיצד תבנית ה-Null Object (מלכה "מנוונת" בקצה השרשרת) חוסכת מאיתנו בדיקות תנאי מסורבלות (neighbor isNil) בכל מתודה, וכיצד 4 המתודות של QueenTerminator בולמות את הרקורסיה באלגנטיות.
מודל מנטלי ועיקרון מנחה: פולימורפיזם ותבנית Null Object במקום משפטי תנאי!
במקום שהמלכה הראשונה תעמוד ליד תהום ותצטרך לבדוק בכל צעד "האם יש מישהו משמאלי או שאני בקצה?", הצבנו משמאלה "קיר חכם" (QueenTerminator) שעונה לה באדיבות תשובות קבועות של תנאי עצירה!
במקום לסרבל את קוד המלכה הרגילה במשפטי תנאי מרובים (כגון neighbor isNil), אנו מגדירים מחלקת "מלכה מנוונת" (תבנית התכנון Null Object) המממשת את אותו הפרוטוקול בדיוק עם תשובות טריוויאליות קבועות.
ב-QueenTerminator: firstSolution מחזיר תמיד true, nextSolution מחזיר תמיד false, canAttack:x: מחזיר תמיד false, ו-result מחזיר OrderedCollection new.
1. הבעיה התכנונית ופתרון ה-QueenTerminator (תבנית Null Object)
למה אנחנו לא רוצים לבדוק neighbor isNil בכל מתודה של המחלקה Queen?
עצור רגע וחשוב על המלכה הראשונה (זו שניצבת בעמודה 1): במציאות הפיזית של לוח השחמט, אין שום מלכה אמיתית משמאלה!
אילו היינו מתכנתים בגישה נאיבית ומציבים במשתנה neighbor של מלכה 1 את הערך הריק nil, היינו נאלצים להוסיף משפטי תנאי מסורבלים (neighbor isNil ifTrue: [...] ifFalse: [...]) בכל אחת ואחת מהמתודות של Queen — גם ב-firstSolution, גם ב-advance, גם ב-moveToNextNonAttackedRow, גם ב-canAttack:x: וגם ב-result!
בתכנות מונחה עצמים אנחנו פותרים זאת באלגנטיות יוצאת דופן באמצעות תבנית התכנון Null Object:
אנו מגדירים מחלקה מיוחדת של "מלכה מנוונת" (QueenTerminator) שתשמש כשכנה (neighbor) של המלכה הראשונה (בעמודה 1).
למלכה המנוונת יש את אותו מבנה פרוטוקול בדיוק כמו למלכה רגילה, אך ללא משתני מופע כלל, והיא מחזירה תשובות קבועות וטריוויאליות שמסיימות את הרקורסיה!
Object subclass: #QueenTerminator
instanceVariableNames: ''
classVariableNames: ''
poolDictionaries: ''
category: 'OOD-8Queens'
המחלקה יורשת מ-Object ואינה זקוקה לשום משתנה מופע (instanceVariableNames: ''), משום שאין לה מיקום פיזי על הלוח או שכנה משלה.
canAttack: testRow x: testColumn ^ false firstSolution ^ true nextSolution ^ false result ^ OrderedCollection new
2. ניתוח פעולת ה-QueenTerminator וטבלת השוואה מול Queen
למה כל אחת מ-4 המתודות מחזירה בדיוק את הערך הזה, ומדוע 3 המתודות האחרות כלל אינן בשימוש?
המלכה המנוונת אינה קיימת פיזית על הלוח ולכן היא לעולם אינה מאיימת על אף משבצת! החזרת false עוצרת את שרשרת בדיקת האיומים ומאשרת שאין איום משמאל לעמודה 1.
כשמלכה 1 מבקשת משכנתה neighbor firstSolution, המלכה המנוונת עונה תמיד true — כי מבחינתה "הלוח הריק משמאל" תמיד פתור ומסודר!
כשמלכה 1 מגיעה לשורה 8 ומנסה לבקש משכנתה סידור נוסף (neighbor nextSolution), המלכה המנוונת עונה תמיד false — אין לה פתרונות נוספים! זה מאותת למלכה 1 (ולכל השרשרת) שאין עוד לאן לסגת ומוצו כל 92 הפתרונות!
מחזירה אוסף סדור ריק חדש (OrderedCollection new), שאליו תוסיף מלכה 1 את השורה שלה, אחריה מלכה 2, וכן הלאה עד מלכה 8!
| הודעה בפרוטוקול | מימוש במחלקה רגילה (Queen) |
מימוש במלכה מנוונת (QueenTerminator) |
|---|---|---|
| setColumn:neighbor: | שומרת את column ו-neighbor במשתני המופע |
אינה בשימוש במלכה המנוונת (אין לה עמודה או שכנה) |
| firstSolution | מבקשת neighbor firstSolution, מציבה row := 1 ומחפשת שורה בטוחה |
^ true |
| nextSolution | ^ self advance and: [self moveToNextNonAttackedRow] | ^ false |
| result | ^ neighbor result addLast: row; yourself | ^ OrderedCollection new |
| advance | מקדמת שורה ציקלית (ובשורה 8 מבקשת neighbor nextSolution) |
אינה בשימוש במלכה המנוונת (נשלחת רק ע"י מלכה לעצמה self) |
| moveToNextNonAttackedRow | מתקדמת בלולאה כל עוד neighbor canAttack: row x: column |
אינה בשימוש במלכה המנוונת (נשלחת רק ע"י מלכה לעצמה self) |
| canAttack:testRow x:testColumn | בודקת שורה ו-2 אלכסונים; אם לא מאיימת מעבירה ל-neighbor |
^ false |
QueenTerminator)כיצד המלכה המנוונת עוצרת את 4 סוגי ההודעות ומבטלת את הצורך בבדיקות isNil
מיני-סימולציה 15.5: בוחן ההודעות של QueenTerminator
מעבדת השוואת קוד: פולימורפיזם עם QueenTerminator מול סרבול בדיקות isNil
בחר מתודה של המחלקה Queen וראה כיצד שימוש ב-QueenTerminator שומר על קוד נקי לחלוטין מתנאים, לעומת הסרבול שהיה נוצר אילו היינו צריכים לבדוק neighbor isNil בכל מתודה:
הגשר הנרטיבי: השלמנו את כל קוד ה-Smalltalk של חידת 8 המלכות (15.1 עד 15.5) – בוא נסכם ונתרגל!
כעת כל חלקי הפאזל יושבים במקומם: הלוח (Board), המלכה (Queen) עם שלושת משתני המופע שלה ו-7 מתודות הפרוטוקול שלה, והמלכה המנוונת (QueenTerminator) בקצה השרשרת.
ביחידה המסכמת הבאה נבחן את כל הסימולציה מקצה לקצה ונתרגל את כל מושגי הפרק בכרטיסיות זיכרון תלת-ממדיות (3D Flashcards)!
מילון מושגים אינטראקטיבי וסיכום פרק 15 (פתרון 8 המלכות ב-OOP)
סיכום הארכיטקטורה המלאה של שלוש המחלקות (Board, Queen, QueenTerminator), זרימת ההודעות בשרשרת, וכרטיסיות זיכרון תלת-ממדיות (3D Flashcards) לכל מושגי הפרק.
מודל מנטלי ועיקרון מנחה: שלוש מחלקות, אפס לולאות מקוננות מרכזיות, ו-100% תקשורת בהודעות!
מחזיקה רק את lastQueen (מלכה 8). בונה ב-initialize את הרשימה המקושרת עם QueenTerminator בקצה, ושולפת ב-solve את כל 92 הפתרונות.
מחזיקה row, column ו-neighbor. מנהלת משא ומתן בהודעות חיצוניות (firstSolution, nextSolution, result) ופנימיות (advance, moveToNextNonAttackedRow, canAttack:x:).
תבנית Null Object בקצה השרשרת ללא משתני מופע. מונעת בדיקות isNil ועוצרת את הרקורסיה עם תשובות קבועות (true, false, OrderedCollection new).
שיתוף הפעולה בין Board, Queen ו-QueenTerminator במציאת 92 הפתרונות
מיני-סימולציה 15.6: בוחן אבחנה מהיר – מי אחראי על מה בסימולציית 8 המלכות?
כרטיסיות זיכרון תלת-ממדיות (3D Flashcards) לכל 12 מושגי פרק 15
לחץ על כל כרטיסייה כדי להפוך אותה ולבחון את עצמך על כל אחד מ-12 מושגי היסוד והמתודות של פרק 15:
נחשפו: 0 / 12סיימנו במלואו את פרק 15! מה מחכה לנו בפרק 16?
שלטנו בכל פרט של הפתרון מונחה העצמים לחידת 8 המלכות בשפת Smalltalk — מהמחלקה Board, דרך שבע המתודות של Queen, ועד לתבנית ה-Null Object ב-QueenTerminator.
classVariableNames: 'N' לעומת משתנה מופע), וכיצד ממדלים את חידת המלכות המרחבית בתלת-ממד ($N \times N \times N$)!