שתי גישות לפתרון חידות בפייתון- ריבוע קסם

יש המון ריבועי קסם ויש דרכים רבות לגשת לפתרון חידות בכלל, ולפתרון ריבוע קסם בפרט. שתי הגישות אליהן אתייחס להלן, הן שתי דרכים שונות בתכלית לפתור חידה (או בעיה). המטרה היא לימודית, להבין את הגישות, מעבר לארבע הקירות של החידה. החידה היא חידה ותיקה ומוכרת. יש לנו ריבוע של 3X3 משבצות לתוכו אנו צריכים לשבץ את הספרות 1-9 כך שסכום הספרות בכל שורה יהיה 15, סכום הספרות בכל טור יהיה 15 וסכום האלכסונים יהיה אף הוא 15. אי אפשר להשתמש בספרה אחת פעמיים.

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

הגישה השנייה, שהיא המעניינת יותר, נקראת backTracking, והיא אומרת את הדבר הבא - בואו נציב במשבצת הראשונה את האפשרות הראשונה שיש לנו מבין האפשרויות (האופציות שלנו), נבצע בדיקה האם יש לנו פתרון לחידה, ונעבור למשבצת הבאה. האפשרויות שלנו עבור המשבצת הבאה כבר יותר מצומצמות כי הורדנו מהאפשרויות את השיבוץ של המשבצת הראשונה. וכך הלאה. באופן הזה אנו בודקים פחות אפשרויות מאשר בגישה הראשונה, משום שאנו הולכים ומצמצמים את מרחב האפשרויות. את הגישה השנייה אנו יכולים לבצע באמצעות רקורסיה, שבכל פעם בודקת עולם מסוים או ענף מסוים (למי שאוהב אנלוגיה של עץ) עם אפשרויות הולכות ומצטמצמות.

נתחיל בקוד של הגישה הראשונה - כמובן אפשר להעתיק ולנסות בבית (מומלץ) -

#magic 15 with permutations import itertools nineList=[i for i in range(1,10)] for b in itertools.permutations(nineList): if b[0]+b[1]+b[2]==15: if b[3]+b[4]+b[5]==15: if b[6]+b[7]+b[8]==15: if b[0]+b[3]+b[6]==15: if b[1]+b[4]+b[7]==15: if b[2]+b[5]+b[8]==15: if b[2]+b[4]+b[6]==15: if b[0]+b[4]+b[8]==15: print(b[0:3]) print(b[3:6]) print(b[6:9]) print("*********")

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

for a in itertools.combinations([1,2,3],2): print(a)

>>>

(1, 2)

(1, 3)

(2, 3)

קיבלנו את כל האפשרויות לשני מספרים שונים מתוך שלושת המספרים 1-3. אם היינו מבקשים לקבל קומבינציה לשלושה מספרים שונים מתוך הרשימה 1-3 היינו מקבלים אפשרות אחת - 1,2,3 האפשרות 3,1,2 אינה מעניינת במתודה הזאת וגם האפשרות 3,3,1 אינה מעניינת כדי לקבל גם מספר אחד יותר מפעם אחת אנו צריכים את המתודה itertools.combinations_with_replacement. במתודה combinatios ניתן לקבל, אם הפרמטר השני יהיה 3 ולא 2, רק שלושה מספרים שונים בלי אפשרויות שונות לסדר אותם בסידורים שונים כמו למשל 3,1,2 . היות שהפתרון שלנו הוא סידור כלשהו של המספרים 1-9 לאו דווקא מהקטן לגודל, אנו מחפשים מונח אחר והוא permutations, זה אמנם נותן לנו מספרים בלי לחזור פעמיים על אותו אחד, אבל הוא נותן גם את האפשרויות לסידורים שונים של שלושת המספרים השונים.

בחידה שלנו זה מה שאנו צריכים, את כל הסידורים השונים של המספרים 1-9. כל סידור כזה נבדק אם הוא עומד בשורת התנאים (שהכל שווה ל- 15) ורק במידה והוא צולח את כל התנאים הוא מדפיס את הפתרון - אחרי הרצת התוכנית מקבלים את שמונת הפתרונות- כפי שניתן לראות למטה. לא כל הפתרונות הם ייחודיים, חלקם זה אותו פתרון רק הפוך או מסובב וחלקם זו תמונת ראי של אותו פתרון. בקיצור יש רק פתרון אחד, רצף אחד שמסתובב סביב הספרה 5 באופן מעגלי.

(2, 7, 6)

(9, 5, 1)

(4, 3, 8)

*********

(2, 9, 4)

(7, 5, 3)

(6, 1, 8)

*********

(4, 3, 8)

(9, 5, 1)

(2, 7, 6)

*********

(4, 9, 2)

(3, 5, 7)

(8, 1, 6)

*********

(6, 1, 8)

(7, 5, 3)

(2, 9, 4)

*********

(6, 7, 2)

(1, 5, 9)

(8, 3, 4)

*********

(8, 1, 6)

(3, 5, 7)

(4, 9, 2)

*********

(8, 3, 4)

(1, 5, 9)

(6, 7, 2)

*********

נחזור לגישה השנייה - ונראה את הקוד היותר מורכב שלה. חלק מהסברים בגוף הקוד אחרי הסולמית -

#magic 15 #pythonisrael.com def check (b): # True פונקציה לבדיקה האם כל התנאים מתקיימים ואם כן מחזירה if b[0]+b[1]+b[2]==15: if b[3]+b[4]+b[5]==15: if b[6]+b[7]+b[8]==15: if b[0]+b[3]+b[6]==15: if b[1]+b[4]+b[7]==15: if b[2]+b[5]+b[8]==15: if b[2]+b[4]+b[6]==15: if b[0]+b[4]+b[8]==15: return True b=[0 for i in range(9)] #המסע שלנו מתחילה עם רשימה של תשעה אפסים המדמים לוח ריק pos = [i for i in range(1,10)] #הרשימה הזאת מייצגת את האפשרויות שלנו המספרים 1-9 def solveMagic15(board,options): #אנו בונים פונקציה שמקבלת שני פרמטרים לוח ריק ולוח אפשרויות if check(board): # אם יש לנו פתרון מדפיסים אותו אחרת ממשיכים print(b[0:3]) print(b[3:6]) print(b[6:9]) print("*********") else: #מכאן מתקדמים כשאין פתרון for i,v in enumerate(b): # הפקודה נותנת לנו מיקום אמיתי וערך של כל איבר ברשימה if v==0: #אם הערך ברשימה שווה לאפס אנו רוצים להציב בו מספר 1-9 break #אנו רוצים להתחיל לעבוד רק על תאים ריקים עד אז התוכנה תחפש אותם for n in options: #אנו רצים על רשימת האופציות שלנו המספרים 1-9 בהתחלה b[i]=n #במקום אפס אנו מציבים את אחד המספרים indxO = options.index(n) # זוכרים מהיכן אנו עתידים לשלוף את המספר שבאופציות options.remove(n) #מצמצמים את רשימת האופציות לענף הבא solveMagic15(board,options) # הרקורסיה- הפעולה תחזור על עצמה בענף אחר b[i]=0 # אם הרקוסיות לא פתרו את החידה מחזרים את הכל לקדמותו options.insert(indxO,n) #מחזירים גם את האופציה שהוסרה solveMagic15(b,pos) #זו הפקודה להפעיל את הפונקציה על הלוח הריק ולוח האופציות

הפתרונות מהרצת התוכנית, אותם פתרונות כמו למעלה.

כדי להבין טוב יותר את העניין של הרקורסיה מומלץ לעבור על החלק במדריך העוסק ברקורסיה, שזה פחות או יותר הדבר הכי מורכב שיש לנו בתכנות, ואני אומר את זה לחיוב, כי זה לא הולך להיות מסובך יותר מזה. זה החלק הקשה.

אבל רגע, לא סיימתי. למה להיכנס לתוכנית כל כך מסובכת כשיש פתרון קצר ופשוט (אני בטוח שיש גם פתרון של שורה), מה גם שלקח לתוכנית בגישה השנייה הרבה יותר זמן מאשר לאופציה הראשונה. אני אומר לכם למה. כי כאשר הפרמוטציות הן של תשעה מספרים, המחשב עושה את זה יחסית מהר, אבל כאשר נגיע לחידות או בעיות מורכבות יותר, למשל 61 אפשרויות בחידתו hidato רק אז מרגשים את ההבדל בין נצח (שזה ממש בלתי אפשרי) לבין דקות ספרות - לטובת הגישה השנייה. הגישה השנייה הרבה פעמים תעשה את ההבדל בין פתרון מהיר ומגניב לבין התשה ובדיקה כל שעה אם המחשב סיים לעבוד.

מי מצליח לקצר את זמן העבודה של התכנית ?

מי מצליח לקצר את הקוד ?

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