מה עושים עם יותר מידי אפשרויות בפייתון

בפורום הצגנו את החידה הבאה - בתוך ריבוע קסם הכולל תשעה תאים (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]

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