ראשית עשיתי חישוב מתמטי פשוט כדי לדעת מה צריך להיות הסכום של כל שורה וכל אלכסון. היות שיש לנו חמש שורות בלוח, כל שורה צריכה להכיל את אותו המספר. סכום כל המספרים מ-1 עד 19 הוא 190. לחלק ב- חמש שורות (או חמישה אלכסונים) יוצא 38 לכל שורה או אלכסון. בהתחלה לקחתי את הלוח והפכנו אותו לרשימה של 19 איברים, שבכל אחד מהם מוצב המספר 0 בהתחלה. המספר הראשון ברשימה מצד שמאל הוא התא השמאלי העליון בלוח. והמספר האחרון ברשימה הוא התא הימני התחתון בלוח כמו שמתואר בצילום הבא - את הפתרון מצאתי בעזרת שיטת הbacktracking המפורסמת שבעצם בודקת את כל האפשרויות המתאימות לתנאי השאלה. לכל איבר ברשימה התוכנה בודקת את האפשרויות לפי תנאי השאלה וכל פעם היא חוזרת שלבים במקרה שאין אפשרויות המתאימות לתנאים. התוכנית לא אלגנטית במיוחד ורצה במחשב שלי ב- 110 שניות(שזה יחסית הרבה). אבל היא עובדת ומוציאה 12 פתרונות שהם בעצם אותו הפתרון רק מסובב ומראה. הקוד: board = [0 for i in range(19)] possibilities = [i for i in range(1,20)] for item0 in possibilities[::]: board[0] = item0 p1 = possibilities[::] for i in range(1): p1.remove(board[i]) rp1 = [] for item in p1: if board[0]+item < 38 and board[0]+item > 18: rp1.append(item) for item1 in rp1: board[1] = item1 p2 = possibilities[::] for i in range(2): p2.remove(board[i]) rp2 = [] for item in p2: if board[0]+board[1]+item == 38: rp2.append(item) for item2 in rp2: board[2] = item2 p3 = possibilities[::] for i in range(3): p3.remove(board[i]) rp3 = [] for item in p3: if board[0]+item < 38 and board[0]+item > 18: rp3.append(item) for item3 in rp3: board[3] = item3 p4 = possibilities[::] for i in range(4): p4.remove(board[i]) rp4 = [] for item in p4: if board[0]+item < 38 and board[1]+item < 38 and board[0]+item < 38: rp4.append(item) for item4 in rp4: board[4] = item4 p5 = possibilities[::] for i in range(5): p5.remove(board[i]) rp5 = [] for item in p5: if board[1]+item < 38 and board[2]+item < 38 and board[3]+board[4]+item < 38 and board[3]+board[4]+item > 18: rp5.append(item) for item5 in rp5: board[5] = item5 p6 = possibilities[::] for i in range(6): p6.remove(board[i]) rp6 = [] for item in p6: if board[3]+board[4]+board[5]+item == 38 and board[2]+item < 38 and board[2]+item > 18: rp6.append(item) for item6 in rp6: board[6] = item6 p7 = possibilities[::] for i in range(7): p7.remove(board[i]) rp7 = [] for item in p7: if board[0]+board[3]+item == 38: rp7.append(item) for item7 in rp7: board[7] = item7 p8 = possibilities[::] for i in range(8): p8.remove(board[i]) rp8 = [] for item in p8: if board[3]+item < 38 and board[7]+item < 38 and board[1]+board[4]+item < 38 and board[1]+board[4]+item > 18: rp8.append(item) for item8 in rp8: board[8] = item8 p9 = possibilities[::] for i in range(9): p9.remove(board[i]) rp9 = [] for item in p9: if board[0]+board[4]+item < 38 and board[2]+board[5]+item < 38 and board[7]+board[8]+item < 38: rp9.append(item) for item9 in rp9: board[9] = item9 p10 = possibilities[::] for i in range(10): p10.remove(board[i]) rp10 = [] for item in p10: if board[7]+board[8]+board[9]+item < 38 and board[7]+board[8]+board[9]+item > 18 and board[1]+board[5]+item < 38 and board[1]+board[5]+item > 18 and board[6]+item < 38: rp10.append(item) for item10 in rp10: board[10] = item10 p11 = possibilities[::] for i in range(11): p11.remove(board[i]) rp11 = [] for item in p11: if board[2]+board[6]+item == 38 and board[7]+board[8]+board[9]+board[10]+item == 38: rp11.append(item) for item11 in rp11: board[11] = item11 p12 = possibilities[::] for i in range(12): p12.remove(board[i]) rp12 = [] for item in p12: if board[7]+item < 38 and board[7]+item > 18 and board[1]+board[4]+board[8]+item == 38: rp12.append(item) for item12 in rp12: board[12] = item12 p13 = possibilities[::] for i in range(13): p13.remove(board[i]) rp13 = [] for item in p13: if board[12]+item < 38 and board[2]+board[5]+board[9]+item < 38 and board[2]+board[5]+board[9]+item > 18 and board[3]+board[8]+item < 38 and board[3]+board[8]+item > 18: rp13.append(item) for item13 in rp13: board[13] = item13 p14 = possibilities[::] for i in range(14): p14.remove(board[i]) rp14 = [] for item in p14: if board[0]+board[4]+board[9]+item < 38 and board[0]+board[4]+board[9]+item > 18 and board[6]+board[10]+item < 38 and board[6]+board[10]+item > 18 and board[12]+board[13]+item < 38 and board[12]+board[13]+item > 18: rp14.append(item) for item14 in rp14: board[14] = item14 p15 = possibilities[::] for i in range(15): p15.remove(board[i]) rp15 = [] for item in p15: if board[1]+board[5]+board[10]+item == 38 and board[12]+board[13]+board[14]+item == 38 and board[11]+item < 38 and board[11]+item > 18: rp15.append(item) for item15 in rp15: board[15] = item15 p16 = possibilities[::] for i in range(16): p16.remove(board[i]) rp16 = [] for item in p16: if board[7]+board[12]+item == 38 and board[2]+board[5]+board[9]+board[13]+item == 38: rp16.append(item) for item16 in rp16: board[16] = item16 p17 = possibilities[::] for i in range(17): p17.remove(board[i]) rp17 = [] for item in p17: if board[3]+board[8]+board[13]+item == 38 and board[6]+board[10]+board[14]+item == 38 and board[16]+item < 38 and board[16]+item > 18: rp17.append(item) for item17 in p17: board[17] = item17 p18 = possibilities[::] for i in range(18): p18.remove(board[i]) rp18 = [] for item in p18: if board[16]+board[17]+item == 38 and board[11]+board[15]+item == 38 and board[0]+board[4]+board[9]+board[14]+item == 38: rp18.append(item) for item18 in rp18: board[18] = item18 print(board) >>> [3, 17, 18, 19, 7, 1, 11, 16, 2, 5, 6, 9, 12, 4, 8, 14, 10, 13, 15] [3, 19, 16, 17, 7, 2, 12, 18, 1, 5, 4, 10, 11, 6, 8, 13, 9, 14, 15] [9, 11, 18, 14, 6, 1, 17, 15, 8, 5, 7, 3, 13, 4, 2, 19, 10, 12, 16] [9, 14, 15, 11, 6, 8, 13, 18, 1, 5, 4, 10, 17, 7, 2, 12, 3, 19, 16] [10, 12, 16, 13, 4, 2, 19, 15, 8, 5, 7, 3, 14, 6, 1, 17, 9, 11, 18] [10, 13, 15, 12, 4, 8, 14, 16, 2, 5, 6, 9, 19, 7, 1, 11, 3, 17, 18] [15, 13, 10, 14, 8, 4, 12, 9, 6, 5, 2, 16, 11, 1, 7, 19, 18, 17, 3] [15, 14, 9, 13, 8, 6, 11, 10, 4, 5, 1, 18, 12, 2, 7, 17, 16, 19, 3] [16, 12, 10, 19, 2, 4, 13, 3, 7, 5, 8, 15, 17, 1, 6, 14, 18, 11, 9] [16, 19, 3, 12, 2, 7, 17, 10, 4, 5, 1, 18, 13, 8, 6, 11, 15, 14, 9] [18, 11, 9, 17, 1, 6, 14, 3, 7, 5, 8, 15, 19, 2, 4, 13, 16, 12, 10] [18, 17, 3, 11, 1, 7, 19, 9, 6, 5, 2, 16, 14, 8, 4, 12, 15, 13, 10]

הפתרון שלי עובד עבור כל n צפרדעים ולוח של 2n+1 - במקרה הזה עבור 5 צפרדעים וחמש קרפדות המחליפות מקום. בפתרון שלי קרפדות מסומנות ב- 0, צפרדעים מסומנות ב- 1 והמקום הריק ב- 2- #Toads = 0 #Frogs = 1 #Empty Place = 2 class Frogs_and_Toads: def __init__(self, n): self.n = n self.board = [0 for i in range(n)] + [2]+ [1 for i in range(n)] self.solution = [1 for i in range(n)] + [2]+ [0 for i in range(n)] self.steps = [self.board[::]] self.solve() def pm(self, board): # bc stands for board copy - a copy of the board possible_moves = [] for place, item in enumerate(board): try: if item == 0: if board[place+1] == 2: bc = board[::] bc[place] = 2 bc[place+1] = 0 possible_moves.append(bc) if item == 1: if place != 0: if board[place-1] == 2: bc = board[::] bc[place] = 2 bc[place-1] = 1 possible_moves.append(bc) except: pass if place < len(board)-2: if item == 0 and board[place+1] == 1 and board[place+2] == 2: bc = board[::] bc[place] = 2 bc[place+2] = 0 possible_moves.append(bc) if place > 1: if item == 1 and board[place-1] == 0 and board[place-2] == 2: bc = board[::] bc[place] = 2 bc[place-2] = 1 possible_moves.append(bc) return possible_moves def solve(self): if self.solution in self.steps: for item in self.steps: print(item) exit() else: for item in self.pm(self.steps[-1]): self.steps.append(item) self.solve() self.steps.pop() Frogs_and_Toads(5) >>> [0, 0, 0, 0, 0, 2, 1, 1, 1, 1, 1] [0, 0, 0, 0, 2, 0, 1, 1, 1, 1, 1] [0, 0, 0, 0, 1, 0, 2, 1, 1, 1, 1] [0, 0, 0, 0, 1, 0, 1, 2, 1, 1, 1] [0, 0, 0, 0, 1, 2, 1, 0, 1, 1, 1] [0, 0, 0, 2, 1, 0, 1, 0, 1, 1, 1] [0, 0, 2, 0, 1, 0, 1, 0, 1, 1, 1] [0, 0, 1, 0, 2, 0, 1, 0, 1, 1, 1] [0, 0, 1, 0, 1, 0, 2, 0, 1, 1, 1] [0, 0, 1, 0, 1, 0, 1, 0, 2, 1, 1] [0, 0, 1, 0, 1, 0, 1, 0, 1, 2, 1] [0, 0, 1, 0, 1, 0, 1, 2, 1, 0, 1] [0, 0, 1, 0, 1, 2, 1, 0, 1, 0, 1] [0, 0, 1, 2, 1, 0, 1, 0, 1, 0, 1] [0, 2, 1, 0, 1, 0, 1, 0, 1, 0, 1] [2, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1] [1, 0, 2, 0, 1, 0, 1, 0, 1, 0, 1] [1, 0, 1, 0, 2, 0, 1, 0, 1, 0, 1] [1, 0, 1, 0, 1, 0, 2, 0, 1, 0, 1] [1, 0, 1, 0, 1, 0, 1, 0, 2, 0, 1] [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 2] [1, 0, 1, 0, 1, 0, 1, 0, 1, 2, 0] [1, 0, 1, 0, 1, 0, 1, 2, 1, 0, 0] [1, 0, 1, 0, 1, 2, 1, 0, 1, 0, 0] [1, 0, 1, 2, 1, 0, 1, 0, 1, 0, 0] [1, 2, 1, 0, 1, 0, 1, 0, 1, 0, 0] [1, 1, 2, 0, 1, 0, 1, 0, 1, 0, 0] [1, 1, 1, 0, 2, 0, 1, 0, 1, 0, 0] [1, 1, 1, 0, 1, 0, 2, 0, 1, 0, 0] [1, 1, 1, 0, 1, 0, 1, 0, 2, 0, 0] [1, 1, 1, 0, 1, 0, 1, 2, 0, 0, 0] [1, 1, 1, 0, 1, 2, 1, 0, 0, 0, 0] [1, 1, 1, 2, 1, 0, 1, 0, 0, 0, 0] [1, 1, 1, 1, 2, 0, 1, 0, 0, 0, 0] [1, 1, 1, 1, 1, 0, 2, 0, 0, 0, 0] [1, 1, 1, 1, 1, 2, 0, 0, 0, 0, 0] הפתרון מראה את כל התהליך של החלפת המקומות בין הצפרדעים לקרפדות. טבע ארבילי