פייתון/פייתון גרסה 3/גישוש נסוג

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

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

על חידת שמונה המלכות והפתרון הכללי לחידה

עריכה
 

על לוח שח מט אנו רוצים להניח שמונה מלכות מבלי שתוכלנה לאכול זו את זו.

מלכה, בשחמט, יכולה לנוע באלכסון או במאוזן ומאונך.

 

אם נביט על המלכה בשורה הראשונה נוכל לראות כי לא משמאל, לא מימין ולא משני האלכסונים יכולה המלכה לאכול מלכה אחרת על לוח.

פתרון לחידה

עריכה
  1. נלך אל המיקום ה-  בלוח.
  2. אם ניתן להציב בו מלכה - נציב ונעדכן את מספר העמודה ל-  והשורה ל- 
  3. אם לא ניתן להציב בו מלכה נעלה את השורה ב-1.
    • במידה ולא ניתן יותר לעלות את העמודה נבצע backtracking:
      • נמחק את המלכה מהמיקום האחרון שהצבנו אותה ונעדכן את הטור והשורה בהתאם לאותו מיקום.
      • נמחק את המלכה מהמיקום האחרון שהצבנו אותה ונעדכן את מיקומינו בהתאם לטור ולשורה בהתאם בה נמצאת המלכה.
      • מאחר שלא ניתן להציב שם מלכה נעדכן את מיקום השורה בפלוס 1.
  4. בסוף תחזיר התכנה רשימה עם מספרים אשר מיקומם מייצג את התור של הלוח לפי הסדר. כל ערך מיצג את מספר השורה שבה נמצאת המלכה.
דוגמה:
[1, 3, 0, 2]

מייצג פתרון ללוח מגודל   כאשר במיקום:

  1. ה-  יש מלכה.
  2. ה-  יש מלכה.
  3. ה-  יש מלכה.
  4. ה-  יש מלכה.

דוגמה

עריכה
  1. נלך אל המיקום ה-  בלוח.
  2. ניתן להציב בו מלכה ולכן נבדוק את העמודה ה- 
  3. לא ניתן להציב שם מלכה ולכן נעלה את השורה ב- 
  4. לא ניתן להציב את המלכה ב-  ולכן נעלה את השורה ב- 
  5. כן ניתן להציב מלכה ב- , נעדכן את מספר העמודה והשורה  
  6. לא ניתן להציב שם מלכה ולכן נעלה את השורה ל-  
  7. לא ניתן להציב שם מלכה ולכן נעלה את השורה ל-  
  8. לא ניתן להציב שם מלכה ולכן נעלה את השורה ל-  
  9. לא ניתן להציב שם מלכה והגענו לשורה האחרונה ועל כן נבצע backtrack ונמחק את המלכה ב-  וכן הלאה.

לכלל המהלכים ניתן לצפות בקישור אל יוטוב בתחתית הדף.

אלגוריתם פתרון

עריכה
def queensproblem(rows, columns):
    solutions = [[]]
    for row in range(rows):
        solutions = add_one_queen(row, columns, solutions)
    return solutions

def add_one_queen(new_row, columns, prev_solutions):
    return [solution + [new_column]
            for solution in prev_solutions
            for new_column in range(columns)
            if no_conflict(new_row, new_column, solution)]

def no_conflict(new_row, new_column, solution):
    return all(solution[row]       != new_column           and
               solution[row] + row != new_column + new_row and
               solution[row] - row != new_column - new_row
               for row in range(new_row))

for solution in queensproblem(4, 4):
    print(solution)

ראה גם

עריכה
  1. Backtracking | N Queen Problem - step by step guide