בחידה הזאת צריך להגיע מהמצב ההתחלתי כמתואר למעלה למצב הסופי שגם הוא מתואר למעלה. הכללים של החידה -כל יצור אמפיבי יכול לנוע למשבצת ריקה הסמוכה אליו או לדלג מעל יצור אמפיבי אחר. צפרדעים יכולות לנוע ימינה בלבד וקרפדות יכולות לנוע שמאלה בלבד. התנועה יכולה להתבצע בשני אופנים : צפרדע יכולה לגלוש למשבצת ריקה סמוכה שנמצאת מימין בלבד ואילו קרפדות יכולות לגלוש למשבצת ריקה סמוכה לשמאל בלבד. צפרדעים וקרפדות יכולות גם לדלג, (זה כל הקטע בבחירת דו חי מהסוג הזה) כמובן כל ייצור לכיוון שמותר לו, צפרדעים רק ימינה וקרפדות רק שמאלה. הדילוג יכול להתבצע אך ורק כאשר יש בסמוך לכיוון הדילוג ייצור מסוג אחר ויש גם אחריו משבצת ריקה. כלומר, צפרדע לא יכולה לדלג מעל צפרדע וקרפדה לא יכולה לדלג מעל קרפדה (בין אם יש אחרי משבצת ריקה ובין אם לא). אי אפשר לדלג על יותר מייצור אחד (צפרדע לא יכולה לדלג מעל שתי קרפדות) ואי אפשר לדלג מעל ייצור שאין אחריו משבצת ריקה (וכל אחת כזכור רק לכיוון שהיא יודעת לדלג).
צריך לבנות תוכנית, בפייתון (כאילו בזה אנו עוסקים כאן), שתציג מודל של החידה. ותציג את שלבי הפתרון מהמצב ההתחלתי למצב הסופי שבו הצפרדעים והקרפדות מחליפות מקומות.
הראשון שיפתור עם תוכנית מרשימה יזכה בתהילת עולם (בקנה המידה המצומצם יותר של קומץ האנשים הנדירים החברים באתר הזה בפורום).
טוב אם ניסיתם במשך כמה ימים ולא הצלחתם , הנה פתרון באמצעות מחלקה -class - וגם רקורסיה - וגם backtracking . לא פתרון של שתי שורות (למי שיש לו רעיון שידביק כאן בשמחה אני לא משלם לפי מספר העמודים באתר), אלא פתרון כזה שאפשר, אולי, ללמוד ממנו משהו - האסטרטגיה של- backtracking מחפשת את הפתרון הנכון מבין האופציות שיש בכל סיטואציה (במדריך יש אנלוגיה של עץ וענפים שזה סבבה), כאשר לא מוצאת בענף מסוים, משיבה את המצב לקדמותו וממשיכה לחפש (למשל אם הסתבר שלהזיז צפרדע לא נותן פתרון, אזי בסיבוב הבא, באותה סיטואציה, התוכנית תקפיץ קרפדה (לא לבעלי קיבה חלשה).
תחילה מקימים מחלקה בשם Creature המתאימה לכל הייצורים האמפיביים, הן צפרדעים והן קרפדות. המחלקה כוללת את הפונקציות הבאות __init__ המספרת לנו מה יש במחלקה - type הוא attribute המטפל בסוג האמפיבי שלנו, צפרדע "f" או קרפדה "t" (באנגלית toad). בהמשך location מטפלת במיקום של הייצור בביצה שלנו שהיא רשימה בשם line (האיבר הראשון משמאל הוא [line[0 כך שהמיקום של מי שנמצא שם הוא 0).
על מנת שנוכל להזיז את הייצורים יש לנו מתודות (שהן פונקציות בתוך מחלקה) כמו move , jump undo_move המותאמות לכל ייצור בנפרד. יש לנו מתודה option המתארת את אפשרות התזוזה של כל ייצור, ויש גם מתודה __repr__ כדי לייצג באופן הולם את הדרך שבה אנו רוצים לראות את הייצור כאשר נבקש להדפיס אותו למשל.
class Creature: def __init__(self,type,location,line): self.type=type self.location=location self.line=line def move(self): self.last_location=self.location if self.type=="f" and self.location<6 and self.line[self.location+1]==0: self.line[self.location+1]=self self.line[self.location]=0 self.location += 1 if self.type == "t" and self.location>0 and self.line[self.location-1]==0: self.line[self.location - 1] = self self.line[self.location] = 0 self.location -= 1 def jump(self): self.last_location = self.location if self.type == "f" and self.location<5 and self.line[self.location+1].type=="t" and self.line[self.location + 2] == 0: self.line[self.location + 2] = self self.line[self.location] = 0 self.location += 2 if self.type == "t" and self.location>1 and self.line[self.location-1].type=="f" and self.line[self.location - 2] == 0: self.line[self.location - 2] = self self.line[self.location] = 0 self.location -= 2 def option(self): option=[] if self.type == "f" and self.location<6 and self.line[self.location + 1] == 0: option.append("m") elif self.type == "t" and self.location>0 and self.line[self.location - 1] == 0: option.append("m") elif self.type == "f" and self.location<5 and self.line[self.location + 1].type == "t" and self.line[self.location + 2] == 0: option.append("j") elif self.type == "t" and self.location>1 and self.line[self.location - 1].type == "f" and self.line[self.location - 2] == 0: option.append("j") else: option.append("n") return option[-1] def undo_move(self): if self.line[self.last_location]==0: self.line[self.location]=0 self.line[self.last_location]=self self.location,self.last_location=self.last_location,self.location def __repr__(self): return f"{self.type}{self.location}" #: מכאן אנו מתחילים לייצר את המופעים של המחלקה שלנו Line=[] Line.append(Creature("f",0,Line)) Line.append(Creature("f",1,Line)) Line.append(Creature("f",2,Line)) Line.append(0) Line.append(Creature("t",4,Line)) Line.append(Creature("t",5,Line)) Line.append(Creature("t",6,Line)) #-זו פונקציה שאומרת מתי סיימנו עם החידה הזו def check_solve(line): if line[3]==0: if line[0].type=="t" and line[1].type=="t"and line[2].type=="t" and line[4].type=="f" and line[5].type=="f" and line[6].type=="f": return True # -כאן אנו מתחילים עם הפונקציה הרקורסיבית שפותרת את החידה def solve (line): l=line[::] #מתוך הרשימה אנו יוצרים אובייקט חדש ולא רק מצביע נוסף לאותה רשימה print(line) if check_solve(line): print(line,"the end") exit() else: for p,v in enumerate(l): #כאן מתחילים את האיטרציה על האובייקט החדש שהופק מהרשימה moj = 0 #זה מיועד להראות שאכן ביצענו קפיצה או תזוזה של משהו if v==0 or v.option()=="n": #כאשר אנו נתקלים ב-0 או כשאין אפשרות תזוזה ממשיכים continue z = l.index(0) #המיקום של 0 ברשימה ילמד אותנו לאן עתיד היצור לזוז if v.option()=="j": line[p].jump() moj+=1 elif v.option() == "m": line[p].move() moj += 1 solve(line) #זאת הרקורסיה בהתגלמותה if moj>0: line[z].undo_move() #כך משיבים הכל למקום כשלא הושלם הפתרון solve(Line) #כך משתמשים במחלקה שבנינו
>>>
הפתרון כתוצאה מהרצת התוכנית נראה כך -
[f0, f1, f2, 0, t4, t5, t6]
[f0, f1, 0, f3, t4, t5, t6]
[f0, 0, f2, f3, t4, t5, t6]
[0, f1, f2, f3, t4, t5, t6]
[f0, f1, t2, f3, 0, t5, t6]
[f0, f1, t2, 0, f4, t5, t6]
[f0, 0, t2, f3, f4, t5, t6]
[0, f1, t2, f3, f4, t5, t6]
[t0, f1, 0, f3, f4, t5, t6]
[t0, 0, f2, f3, f4, t5, t6]
[t0, f1, 0, f3, f4, t5, t6]
[t0, 0, f2, f3, f4, t5, t6]
[t0, f1, f2, t3, f4, 0, t6]
[t0, f1, f2, t3, 0, f5, t6]
[t0, f1, 0, t3, f4, f5, t6]
[t0, 0, f2, t3, f4, f5, t6]
[t0, t1, f2, 0, f4, f5, t6]
[t0, t1, 0, f3, f4, f5, t6]
[t0, t1, f2, 0, f4, f5, t6]
[t0, t1, 0, f3, f4, f5, t6]
[t0, t1, f2, f3, t4, f5, 0]
[t0, t1, f2, f3, t4, 0, f6]
[t0, t1, f2, 0, t4, f5, f6]
[t0, t1, 0, f3, t4, f5, f6]
[t0, t1, t2, f3, 0, f5, f6]
[t0, t1, t2, 0, f4, f5, f6]
[t0, t1, t2, 0, f4, f5, f6] the end
זו לא הדרך הקצרה ביותר, אבל זו דרך לדעת שיש פתרון לחידה שלנו.