מתודה נחמדה בפייתון נקראת divmod עושה פעולה מתמטית שיכולה לעתים לקצר תהליכים ולהיות מאוד שימושית. כידוע אנו יכולים לקבל מנה של שני מספרים בתצורות שונות בפייתון, במקרה הזה אנו מקבלים את המנה (תוצאת החילוק) כ- tuple שחלקו השמאלי מייצג את המספר השלם וחלקו הימני את השארית. נדגים - print(divmod(5,3)) נקבל - (1,2) כלומר, 3 מוכל ב- 5 פעם אחת בלבד עם שארית של 2 התוצאה כאמור בטופל שניתן להתייחס בנפרד לשני חלקיו. אפשר גם להזין ערך כ- float למשל 8.0 - print(divmod(8.0 ,3)) התוצאה המתקבלת - (2.0, 2.0) כלומר 3 מוכל פעמיים ב- 8 ונותרת שארית של 2 (פייתון מחזיר את התוצאה כטופל המכיל מספרים מסוג- float) מה אפשר לעשות עם זה? - למשל, אפשר לכתוב תוכנית שמחזירה את סכום הספרות של מספר כלשהו x - x = 999 #זה המספר שבחרנו sum_dig = 0 #כאן נסכום את היחידות while x!=0: dm = divmod(x, 10) #חלוקה ב-10 מבודדת את היחידות מיתר המספר dig = dm[1] #בסיבוב הראשון שווה 9 x = dm[0] #בסיבוב הראשון שווה 99 sum_dig = sum_dig + dig #צוברים את סכומי האחדות print(sum_dig) התוצאה כמובן 27=9+9+9 אפשר לכתוב תוכנית שהופכת לנו את סדר הספרות במספר כלשהו - x = 456 #המספר שבחרנו rev_num = 0 #כאן יהיה המספר ההפוך while x!=0: dm = divmod(x, 10) dig = dm[1] x = dm[0] rev_num = rev_num * 10 + dig #תהליך של צירוף היחידות ובסיבוב הבא הכפלה ב-10 print(rev_num) התוצאה בדוגמא הזאת - 654 סדר ספרות הפוך למספר המקורי שלנו 456. עכשיו נראה שימוש בפעולה מתמטית אחרת log שנייבא מתוך הספריה math פעולת log מבחינה מתמטית משמשת, בגדול, לאיתור מעריך החזקה כאשר בסיס החזקה נתון ותוצאת פעולת החזקה נתונה. 2**3=8 פעולת log יכולה למצוא את מעריך החזקה 3 כאשר נתונים לנו בסיס החזקה 2 והתוצאה 8 - from math import log print(log(8,2)) התוצאה 3.0 - הערך הוא מסוג float בספריית math אפשר למצוא לוגים עם בסיסים מן המוכן למשל בסיס 10 בסיס 2 כך שלא צריך להזין את הבסיס בנוסחה אלא רק את המספר ממנו נחלץ את מעריך החזקה. אחד השימושים האפשריים הוא מציאת אורך של מספר (כמה ספרות יש במספר) X כלשהו. from math import log x=34523 #המספר שבחרנו len_x=int(log(x,10))+1 #הסבר למטה print(len_x) התוצאה היא 5 כי במספר יש חמש ספרות. הסבר - כאשר אנו עושים פעולה של לוג בבסיס של 10 נקבל מספר שלם המשקף את מספר הספרות אחרי המספר הראשון משמאל ועוד שבר (מספרים אחרי הנקודה העשרונית) שילך ויגדל ככל שאנו מתקרבים להוספת ספרה לאורך המספר. למשל - log בבסיס 10 של 100 = 2, log בבסיס 10 של 500 =2.698 ואילו לוג בבסיס 10 של 1000 שווה ל- 3. היות שאנו מעוניינים רק בחלק התוצאה שהיא המספרים השלמים - אנו מבצעים פעולה של ( )int שמנקה את הספרות מימין לנקודה. כמו כן, פעולת לוג נותנת לנו את הספרות אחרי המספר השמאלי ואנו רוצים את האורך של כל המספר לכן אנו מוסיפים 1. הרי לנו שימוש בפעולה מתמטית לצורך ביצוע משימה בפייתון שאינה קשורה דווקא במתמטיקה.

בעברית קוראים לזה תזכור (tizkur) ובהתחלה זה נראה כמו שגיאת כתיב של המילה memorization אבל זה זה לא. ומדובר במושג בעל חשיבות גדולה מאוד, בעיקר לתוכנה כמו פייתון שעקב האכילס שלה הוא מהירות הריצה של התוכניות. הדבר מוצא את ביטויו לעיתים קרובות כאשר מבקשים לבצע חישובים מורכבים או חישובים רקורסיביים, אשר חוזרים על עצמם פעמים רבות בתוך פונקציה אחת וגורמים לאיטיות בלתי נסבלת עד בלתי אפשרית של התוכנית. הרעיון התיאורטי הוא פשוט, אנו עורכים מילון של כל החישובים הארוכים שכבר ערכנו, ואם יש לנו במילון תוצאה של חישוב שכבר ערכנו, אנו לא מחשבים שוב ובכך חוסכים זמן ריצה ומשאבי זיכרון. אם כך נראה איך זה עובד בפייתון בפועל - לשם כך ניקח פונקציה רקורסיבית (המופיעה גם במדריך שלנו) המחשבת את מספרי פיבונאצ'י (....1,1,2,3,5,8,13,21), הבעיה המתעוררת כאשר מריצים את מספר פיבונאצ'י מספר 35 בסדרה, המחשב נעשה כבד ובקושי זז, ונראה שהוא נתקף בעיות זכרון קשות. נראה את הפונקציה ולאחר מכן מה עושים כדי לשפר את המצב. n מייצג את מיקום מספר הפיבונאצ'י בסדרה, למשל כאשר n=6 אנו מתכוונים למספר השישי ברשימה כלומר 8 - def fib(n): if n<3: return 1 else: return (fib(n-1)+fib(n-2)) למעלה אנו רואים פונקציה רקורסיבית המחזירה את הערך 1 לשני האיברים הראשונים בסדרה ולגבי האחרים מפעילה את אותה פונקציה באופן רקורסיבי פעמיים, (fib(n-1)+fib(n-2 כדי למצוא את המספר שלנו (ניתן לעיין במדריך בערך פונקציה רקורסיבית). בדרך הזאת יוצא לפונקציה שלנו fib לבצע שוב ושוב פעמים רבות את אותו החישוב שהיא כבר ביצעה, למשל היא תחזור המון פעמים על החישוב (fib(5 כאשר אנו מחפשים את (fib(30. כעת נראה איך אנו יכולים להכין מילון עם התוצאות שכבר חישבנו - כדי להתגבר על הבעיה- fibonacci_mem={} def fib(n): if n in fibonacci_mem: return fibonacci_mem[n] if n<3: value=1 else: value=fib(n-1)+fib(n-2) fibonacci_mem[n]=value return value print(fib(950)) אנו רואים שיצרנו מילון בשם fibonacci_mem שהדבר הראשון שהפונקציה עושה היא לחפש האם יש בו את החישוב עבור מספר הפיבונאצ'י המבוקש, אם יש היא מחזירה אותו ואם אין היא מחשבת אותו כרגיל ולבסוף לפני שהיא מחזירה את הערך שחושב, היא מכניסה אותו למילון שלנו. זה הכל, כעת אנו יכולים לחשב מהו מספר הפיבונאצ'י מספר 950 באופן מיידי בלי לשאוב את הזכרון של המחשב שלנו ובלי להמתין לנצח. נזכיר שלפני כן נתקענו כבר במספר פיבונאצ'י מספר 35. הדברים עד כדי כך חשובים שפיתחו ספריה שעושה את הדבר הזה באופן אוטומטי עבור הפונקציות שלנו (בלי שאנו מכינים מילון וכו') ונראה איך הדבר עובד, מדובר במתודה הקיימת בספריה functools והנקראת lru_cache על שום שהיא עוסקת בזכרון המטמון של המחשב. ונראה איך עושים את זה - from functools import lru_cache @lru_cache() def fib(n): if n<3: return 1 else: return (fib(n-1)+fib(n-2)) for i in range(1,1000): print(fib(i)) הדברים פשוטים מאוד, לאחר שיבאנו את המתודה lru_cache של הספריה functools אנו בונים פונקציית קישוט (דקורטור) מעל הפונקציה הרגילה שלנו השורה שמתחילה בסימן שטרודל. אפשר גם לרשום מה גודל הזכרון שאנו רוצים לשמור וזה יראה כך (lru_cache(maxsize=1000@ וכעת אנו יכולים לחשב את אלף מספרי הפיבונאצ'י הראשונים באופן מיידי. המספרים ארוכים מאוד מאוד ולכן לא מציג אותם כאן. טוב אולי רק את מספר פיבונאצ'י 950 המתחיל ב- 444 וממשיך הרבה אחרי זה סה"כ 199 ספרות (כדי לחשב את אורך המספר הופכים אותו למחרוזת ומבקשים את האורך שלה באמצעות len שאינה פועלת על integers . 4447803282326157141063860798140565135175279561812695372311151183404978544074576084779694906092198758336762454048905401589449506607204278264939097537573413980490519471907060934663660744135522705225 תזכור=memoization

בפורום הצגנו את החידה הבאה - בתוך ריבוע קסם הכולל תשעה תאים (3X3) צריך לשבץ תשעה מספרים ראשוניים שונים (בין 0 ל-100 כולל המספר 1 שלא ברור למתמטיקאים אם הוא גם נחשב למספר ראשוני), באופן שכל שורה בריבוע, כל טור וכל אלכסון יהיה סכומם שווה ל- 111. לאחר שבונים פונקציה ליצירת כלל המספרים הראשוניים (אחת האפשרויות) מופיעה במדריך שלנו בפרק העוסק ברקורסיה, אנו מגלים שיש 26 אפשרויות שונות - [1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] אנו זקוקים בסך הכל לתשעה מספרים. החידה מסקרנת ורוצים לפתור אותה מהר, לכן מייבאים את הספרייה itertools ומבקשים לייצר את כל האפשרויות (permutations) לתשעה מספרים מתוך 26 כאשר התשעה יכולים להיות גם אותם תשעה במיקומים שונים. כמה אפשרויות המחשב צריך לייצר לנו ? הנוסחה היא !26 לחלק ב- !(26-9) התוצאה היא 1,100,000,000,000 - גם אם המחשב שלכם מאוד מהיר, זה הרבה מאוד זמן לסיים את כל האפשרויות האלה, על זה תוסיפו את הסיפור שפייתון היא סביבת עבודה שלמה ונעדרת הידור (קומפילציה) ולכן מעט יותר איטית מתוכנות אחרות וקיבלתם נצח. ניסיון לברוח לרקורסיה גם הוא לא יניב תוצאות מהירות וטובות עם כל כך הרבה אפשרויות. ולכן אין מנוס מלשבת ולכתוב קוד שיצמצם לנו בכל פעם את מספר הפתרונות האפשריים באופן משמעותי. אם אנו יודעים למשל שהמספר הגדול ביותר ברשימה הוא 97 זה אומר לנו שסכום שני מספר שכנים לא יכול להיות קטן מ-14 משום שאז גם אם נוסיף את המספר הגדול ביותר שלנו, 97, לא נגיע ל- 111; כמו כן, סכומם של שני מספרים לא יכול לעלות על 110 משום שלא נותר מקום למספר שלישי בשורה בטור או באלכסון . וכאשר יש לנו כבר שני מספרים שכנים השלישי צריך להשלים ל- 111. עם הנתונים הללו או משתמשים באיטרציה באמצעות לולאות for הרצה על האפשרויות שלנו (רשימת המספרים הראשוניים), מחפשת אפשרויות יותר מדויקות עבורנו. ובכל סיבוב שאנו עוברים למספר הבא, מורידים מהרשימה את המספרים שכבר השתמשנו בהם. לכן, למרות שיש כל כך הרבה אפשרויות, כאשר יש לי שני מספרים בשורה ואני מחפש את השלישי - כאן יש לי רק אפשרות אחת - זו המשלימה ל- 111. למטה ישנו פתרון הדומה לפתרון של טבע מהפורום שלנו, תשומת ליבכם לכך, למי שירצה לנתח את הקוד, שבכל פעם שאנו משלימים סיבוב לגבי מספר בלוח שלנו, אנו עושים את הסיבוב הבא על רשימת הראשונים (פחות אלה שכבר השתמשנו בהם). זה החלק הראשון של הקוד - def primes(n): """ prime numbers from 1 to n """ listPrime=[] for num in range(1,n): for other in range(2,num): if num%other==0: break else: listPrime.append(num) return listPrime potentials=primes(100) board=[0 for i in range(9)] #זו רשימת המספרים הראשונים בחלק השני של הקוד כדאי לשים לב לשימוש ב- [::]potentials הפעולה הזאת מסמלת ברשימה לעבור על הפריטים מהתחלה עד הסוף, אבל חשוב מזה, היא מייצרת אובייקט חדש שלא תלוי בשינויים של רשימת הראשוניים שלנו בסיבוב הראשון. אם לא נוסיף את הסימן הזה [::] התוכנית לא תעבוד כמו שצריך, משום שכל פעם שנשנה את הרשימה ברמה אחת, היא תשתנה גם ברמה אחרת, משום שבפייתון נעשה שימוש במצביעים, ולעיתים גם כשנדמה לנו שיצרנו רשימה חדשה, בעצם יצרנו רק מצביע חדש. הסימן הזה מאפשר לנו ליצור אובייקט בלתי תלוי ולהריץ את האיטרציה עליו (ההסבר לאיטרציה במדריך) באמצעות לולאת for. board=[0 for i in range(9)] #זה ריבוע הקסם שלנו הכולל תשע משבצות for first in potentials[::]: #זו הלולאה הראשונה שלנו indx=potentials.index(first) board[0]=first potentials.remove(first) for second in potentials[::]: if (board[0] + second) > 13 and 111>(board[0] + second) : indx = potentials.index(second) board[1] = second potentials.remove(second) for third in potentials[::]: if (board[0] + board[1]+ third) == 111: indx = potentials.index(third) board[2] = third potentials.remove(third) for forth in potentials[::]: if (board[0] + forth) >13 and 111>(board[0]+ forth): indx = potentials.index(forth) board[3] = forth potentials.remove(forth) for fifth in potentials[::]: if 111 > (board[1] + fifth) and (board[1] + fifth)> 13 and (board[3] + fifth) >13 and (board[3] + fifth)<111 : indx = potentials.index(fifth) board[4] = fifth potentials.remove(fifth) for sixth in potentials[::]: if (board[3] + board[4]+sixth) == 111: indx = potentials.index(sixth) board[5] = sixth potentials.remove(sixth) for seventh in potentials[::]: if (board[0] + board[3] + seventh) == 111 and board[2]+board[4]+seventh==111: indx = potentials.index(seventh) board[6] = seventh potentials.remove(seventh) for eighth in potentials[::]: if (board[1] + board[ 4] + eighth) == 111: indx = potentials.index( eighth) board[7] = eighth potentials.remove(eighth) for last in potentials[::]: if (board[ 2] + board[ 5] + last) == 111 and board[0]+board[4]+last==111: indx = potentials.index( last) board[ 8] = last print(board) #מדפיסים פתרון כשיש לוח מלא potentials.insert(indx,eighth) #כאן מתחילים להחזיר מה שהוצאנו potentials.insert(indx,seventh) potentials.insert(indx,sixth) potentials.insert(indx,fifth) potentials.insert(indx,forth) potentials.insert(indx,third) potentials.insert(indx,second) potentials.insert(indx,first) פתרון החידה - [7, 73, 31, 61, 37, 13, 43, 1, 67] [7, 61, 43, 73, 37, 1, 31, 13, 67] [31, 73, 7, 13, 37, 61, 67, 1, 43] [31, 13, 67, 73, 37, 1, 7, 61, 43] [43, 1, 67, 61, 37, 13, 7, 73, 31] [43, 61, 7, 1, 37, 73, 67, 13, 31] [67, 1, 43, 13, 37, 61, 31, 73, 7] [67, 13, 31, 1, 37, 73, 43, 61, 7] התוכנית מניבה את כל שמונת הפתרונות שהם למעשה פתרון אחד עם סיבוב של הריבוע כל פעם לצלע אחרת ועם תמונת ראי

יש המון ריבועי קסם ויש דרכים רבות לגשת לפתרון חידות בכלל, ולפתרון ריבוע קסם בפרט. שתי הגישות אליהן אתייחס להלן, הן שתי דרכים שונות בתכלית לפתור חידה (או בעיה). המטרה היא לימודית, להבין את הגישות, מעבר לארבע הקירות של החידה. החידה היא חידה ותיקה ומוכרת. יש לנו ריבוע של 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 רק אז מרגשים את ההבדל בין נצח (שזה ממש בלתי אפשרי) לבין דקות ספרות - לטובת הגישה השנייה. הגישה השנייה הרבה פעמים תעשה את ההבדל בין פתרון מהיר ומגניב לבין התשה ובדיקה כל שעה אם המחשב סיים לעבוד. מי מצליח לקצר את זמן העבודה של התכנית ? מי מצליח לקצר את הקוד ? אשמח לפגוש את כל השאלות ההצעות והמחשבות (כולל תיקון שגיאות כתיב) בפורום שלנו.

חידת 8 המלכות היתה פופולרית מאוד בראיונות עבודה, ובדרך כלל משמשת להדגים את יעילות שיטת backtraking, כאן נדגים משהוא אחר. החידה הולכת כך: על לוח שחמט צריך לסדר 8 מלכות (מלכה יכולה לנוע לאורך טורים שורות ואלכסונים ללא הגבלה). סידור המלכות על פני הלוח צריך להיות כזה שאף מלכה אינה עומדת על המשבצות עליהן חולשת מלכה אחרת (בשליטת מלכה אחרת). זאת אומרת שבכל טור בלוח ובכל שורה בלוח צריכה לעמוד רק מלכה אחת. ועל כל אלכסון בלוח לא תהיה יותר ממלכה אחת. בפתרון הזה ננצל את העובדה שלוח השחמט הוא מטריצה של אורך ורוחב - את המיקום של כל מלכה (מתוך השמונה) אנו נתאר כמספר בין 0-7 המתאר את השורה בלוח כאשר את הטור בלוח אנו מתארים באמצעות המיקום ברשימה. מספר שיהיה ראשון ברשימה משמאל, יוצב על הטור השמאלי ביותר של הלוח (המספר ייצג את השורה). היות שבחידה שלנו אין יותר ממלכה אחת על כל טור וכל שורה, אנו יכולים להשתמש בפרמוטציות של שמונה מספרים 0-7 מה שיתן לנו את כל הסידורים השונים של 8 מלכות על הלוח כאשר אין יותר ממלכה אחת על כל טור או כל שורה. נראה את התוכנית ונמשיך להסביר - from itertools import permutations cols = range(8) for p in permutations(cols): if (len(set(p[c]+c for c in cols)) == len(set(p[c]-c for c in cols))==8): print (p) אנו מייבאים מתוך הספריה itertools את המתודה permutations שמייצרת לנו סידורים של המספרים 0-7 במיקומים שונים בלי לחזור על אותו מספר פעמיים - משהו כזה - (6, 2, 7, 1, 4, 0, 5, 3) (6, 3, 1, 4, 7, 0, 2, 5) (6, 3, 1, 7, 5, 0, 2, 4) (6, 4, 2, 0, 5, 7, 1, 3) בכל אפשרות כזה כזאת יש לנו כבר, בילת אין, מצב בו אין יותר ממלכה אחת על כל טור או על כל שורה. מה שנותר לנו הוא לבדוק שאין שתי מלכות על אותו אלכסון. לשם כך, צריך לחקור את הלוח וניתן לגלות עליו את הדבר הבא - בלוח השחמט יש שני סוגי אלכסונים - כאלה שחלקם הגבוה הוא בצד שמאל וחלקם הנמוך בצד ימין (כמו האלכסון בריבוע הימני המסומן במספר 7) - נקרא להם אלכסונים יורדים. והסוג השני הוא אלכסונים שמתחילים בצד שמאל למטה ומסיימים בצד ימין למעלה, (כמו אלה המסומנים בריבוע השמאלי בספרה 0) נקרא להם אלכסונים עולים. מלכה הנמצאת במקום טוב באמצע הלוח, חולשת הן על אלכסונים עולים והן על אלכסונים יורדים. אנו צריכים לוודא שעל שני הסוגים לא עומדת מלכה אחרת. התבוננות בלוחות מגלה כי ניתן לייצג את האלכסונים היורדים בנוסחה הבאה: מספר השורה+מספר הטור, כך שכל מלכה שתעמוד על אותו אלכסון יורד תהיה על אותו מספר. ואותו הדבר לגבי האלכסונים העולים אותם מקבלים לפי הנוסחה: מספר טור - מספר שורה (מספר השורה פחות מספר הטור), אחרי שמיישמים את הנוסחה לכל הלוח אנו יכולים לראות למשל שכל המשבצות שתוצאת הנוסחה בתוכן היא 3- הן על אותו אלכסון עולה (בלוח השמאלי). אם כך, מה שאנחנו מחפשים הוא פרמוטציה, permutation, של המספרים 0-7 (המייצגים 8 שורות בלוח השחמט) במיקומים כאלה על הלוח (למשל לוח האלכסונים היורדים) שכל מלכה תעמוד על משבצת בעלת מספר אחר (כלומר כל אחת על אלכסון שונה) וכך גם בלוח של האלכסונים העולים. המשבצות המסומנות בכחול על שני הלוחות הם בעצם אחד הפתרונות של החידה (על שני הלוחות זה אותו פתרון - מלכה ראשונה על המשבצת השמאלית התחתונה וכו') אנו רואים שבכל לוח יש שמונה מספרים שונים (כל אחד מייצג אלכסון). מכאן השורה בקוד - if (len(set(p[c]+c for c in cols))== len(set(p[c]-c for c in cols))==8): אנו רוצים שהאורך len של סט set המופעל על נוסחת האלכסונים העולים של כל מלכה יהיה שווה ל-8. כנ"ל לגבי האלכסונים היורדים. אם הסט (שאינו מכיל פעמיים את אותו המספר - המייצג אלכסון) שווה ל- 8 זה אומר שכל מלכה על אלכסון שונה. p[c]-c למשל מייצגת את נוסחת האלכסונים העולים [p[c הוא מספר השורה (מסומן בירוק בלוחות שלנו) ו- c הוא מספר הטור (מסומן בצהוב בלוחות שלנו). סה"כ מתקבלים 92 פתרונות של החידה (מתוך 4 מיליארד אפשרויות בערך) - מוזמנים להעתיק ולנסות במחשב שלכם. הנה כמה מהפתרונות לחידה 0, 5, 7, 2, 6, 3, 1, 4 0, 6, 3, 5, 7, 1, 4, 2 0, 6, 4, 7, 1, 3, 5, 2 משמעות הפתרון הראשון, מלכה ראשונה בטור השמאלי ביותר בשורה 0 (שהיא השורה הראשונה), המלכה השנייה (שנייה ברשימה) בטור השני משמאל בשורה 6 (אם מתחילים מ-0 המספר 5 הוא השורה הששית) המלכה השלישית, בטור השלישי משמאל בשורה העליונה ביותר (השורה השמינית המיוצגת על ידי הספרה 7) וכו'.

משחק הקטמינו שאני התוועדתי אליו בגן של הבן שלי לראשונה. האתגר בפאזל הוא לסדר חלקים שונים (מזכירים מעט את החלקים של משחק הטטריס) - מספר החלקים גדל ככל שרמת הקושי עולה - וצריך לסדר אותם כך שהם יתאימו ללוח מלבני באופן מושלם. למשל: שלושה חלקים יתאימו למלבן של 3X5 ו- 11 חלקים יתאימו למלבן של 11X5 . אנחנו, כמובן, בנינו תוכנית בפייתון שפותרת את החידה בעצמה, ומציגה את הפתרון באופן גרפי נחמד וברור. צלמתי סרטון קצר להמחשה. הקוד נכתב באמצעות רקורסיה או לולאה מקוננת (nested loop) כאשר לב התוכנית בוצע באמצעות פונקציה שמחזירה את עצמה. הקוד: import copy #מסייע בהמשך בהעתקת רשימות בתוך רשימות import matplotlib.pyplot as plt #רעיון מעניין להצגה גרפית של הפתרון #כל צורה במשחק מקבלת שם ומטריצה # אם נעמיד את תת הרשימות אחת מתחת לשנייה נוכל לראות את הצורה# #shapes: X=[[0,1,0],[1,1,1],[0,1,0]] P=[[2,2,2],[0,2,2],[0,0,0]] Z=[[3,3,0],[0,3,0],[0,3,3]] F=[[0,0,0,0],[0,0,0,0],[0,4,0,0],[4,4,4,4]] L=[[5,5,5,5],[0,0,0,5],[0,0,0,0],[0,0,0,0]] V=[[6,0,0],[6,0,0],[6,6,6]] R=[[0,7,7],[7,7,0],[0,7,0]] T=[[0,8,0],[0,8,0],[8,8,8]] H=[[9,9,0],[0,9,0],[9,9,0]] W=[[0,0,10],[0,10,10],[10,10,0]] N=[[0,11,11,11],[11,11,0,0],[0,0,0,0],[0,0,0,0]] I=[[12,0,0,0],[12,0,0,0],[12,0,0,0],[12,0,0,0]] #כל פאזל מורכב מחלקים שונים וכאן אנו מזינים את החלקים בחידה הספציפית #here you put the parts in the riddle: katamino=[L,V,P,H,W,F] #here we build the board num_parts=len(katamino) #creating the board Board=[] for i in range (num_parts): Board.append([0,0,0,0,0]) #here we rotate the shape including mirror image כאן מסובים את הצורה כולל תמונת ראי def rotateMatrix(matx): N=len(matx[0]) mat = copy.deepcopy(matx) # Consider all squares one by one for x in range(0, 2): # Consider elements in group # of 4 in current square for y in range(x, N - x - 1): # store current cell in temp variable temp = mat[x][y] # move values from right to top mat[x][y] = mat[y][N - 1 - x] # move values from bottom to right mat[y][N - 1 - x] = mat[N - 1 - x][N - 1 - y] # move values from left to bottom mat[N - 1 - x][N - 1 - y] = mat[N - 1 - y][x] # assign temp to left mat[N - 1 - y][x] = temp return mat def allShapeForms(shape): s = [] s.append(shape) cp = copy.deepcopy(shape) for i in range(3): x = rotateMatrix(cp) s.append(x) cp = x cp = [] for item in shape: cp.append(item[::-1]) s.append(cp) for i in range(3): x = rotateMatrix(cp) s.append(x) cp = x return s #here we fit shape to board כאן מתאימים צורה ללוח שלנו #that the shape will not get out of the board שהצורה לא תצא מהלוח def fitForm2Board (form,tempboard): board=copy.deepcopy(tempboard) combinationFormList=[] collision = 0 for y in range(num_parts): for x in range (5): for index, row in enumerate(form): for ind, cell in enumerate(row): if cell != 0: if (index+y<num_parts and ind+x<5) and (board[index+y][ind+x] == 0): board[index+y][ind+x] = cell else: collision += 1 if collision > 0: collision = 0 board = copy.deepcopy(tempboard) else: combinationFormList.append(board) board =copy.deepcopy(tempboard) return combinationFormList #פונקציה קטנה להצגת מטריצה בדו מימד במקום כרשימה אחת ארוכה def print2d(mat): for item in mat: print(item) #כאן בודקים היכן יש מקומות ריקים בלוח בשכנות לצורה שלנו def emptyNeighbors(y,x,board): nbrs = [] if board[y][x] == 0: if (y - 1) >= 0 and board[y - 1][x] == 0: nbrs.append((y - 1, x)) if (y + 1) <= (num_parts - 1) and board[y + 1][x] == 0: nbrs.append((y + 1, x)) if (x - 1) >= 0 and board[y][x - 1] == 0: nbrs.append((y, x - 1)) if (x + 1) <= 4 and board[y][x + 1] == 0: nbrs.append((y, x + 1)) else: return None return nbrs #כדי לצמצם אפשרויות אנו מסירים לוחות אם איים ריקים שאינם מתאימים לשום צורה def chekSmallCloseTeritoriesInBoard (board): for y in range (num_parts): for x in range (5): if emptyNeighbors(y,x,board)!=None and len(emptyNeighbors(y,x,board))==0: return False if emptyNeighbors(y,x,board)!=None and len(emptyNeighbors(y,x,board))==1: z=emptyNeighbors(y,x,board)[0][0] k=emptyNeighbors(y,x,board)[0][1] if len(emptyNeighbors(z,k,board))==1: return False if emptyNeighbors(y,x,board)!=None and len(emptyNeighbors(y,x,board))==2: z=emptyNeighbors(y,x,board)[0][0] k=emptyNeighbors(y,x,board)[0][1] g=emptyNeighbors(y,x,board)[1][0] h=emptyNeighbors(y,x,board)[1][1] if len(emptyNeighbors(z,k,board))==1 and len(emptyNeighbors(g,h,board))==1 : return False return True #כאן אנו מייצרים את האפשרויות השונות של הלוחות לכל צורה וצורה #return all bords: def allShapePossibilities (shape,board): allposs=[] for item in allShapeForms(shape): for b1 in fitForm2Board(item, board): if chekSmallCloseTeritoriesInBoard(b1): allposs.append(b1) return allposs #כאן כתובה הפונקציה הראשית שפותרת את החידה כלולאה מקוננת #nested loop to solve the puzzle and find us the winnig board Num = 0 def findAll (board): global Num for b in allShapePossibilities(katamino[Num],board): if Num==num_parts-1: print2d(b) z = board #for the graphics for ind, row in enumerate(z): for index, num in enumerate(row): if num == 1: z[ind][index] = 1 if num == 2: z[ind][index] = 2 if num == 3: z[ind][index] = 3 if num == 4: z[ind][index] = 4 if num == 5: z[ind][index] = 5 if num == 6: z[ind][index] = 6 if num == 7: z[ind][index] = 7 if num == 8: z[ind][index] = 8 if num == 9: z[ind][index] = 9 if num == 10: z[ind][index] = 10 if num == 11: z[ind][index] = 11 if num == 12: z[ind][index] = 12 fig = plt.figure() ax = fig.add_subplot(111) ax.imshow(z, extent=[1, 5, 1, num_parts], interpolation='none') plt.show() quit() else: Num+=1 findAll(b) #nested loop כאן הלוואה המקוננת המחזירה את עצמה עד שמוצאת פתרון Num-=1 # if we didn't find solution in that path למקרה שלא מצאנו פתרון חוזרים צעד לאחור findAll(Board) #הפעלת הפונקציה הרקורסיבית המקוננת