פייתון/פייתון גרסה 3/גישוש נסוג
< פייתון | פייתון גרסה 3
גישוש נסוג (Backtracking) הוא אלגוריתם למציאת פתרון לבעיה. בכל פעם שנגיע לפתרון לא נכון נחזור להתחלה וננסה דרך אחרת. כל זאת באמצעות רקורסיה.
ניתן דוגמה לפתרון חידת שמונה המלכות באמצעות גישוש נסוג.
על חידת שמונה המלכות והפתרון הכללי לחידה
עריכה
על לוח שח מט אנו רוצים להניח שמונה מלכות מבלי שתוכלנה לאכול זו את זו.
מלכה, בשחמט, יכולה לנוע באלכסון או במאוזן ומאונך.
אם נביט על המלכה בשורה הראשונה נוכל לראות כי לא משמאל, לא מימין ולא משני האלכסונים יכולה המלכה לאכול מלכה אחרת על לוח.
פתרון לחידה
עריכה- נלך אל המיקום ה- בלוח.
- אם ניתן להציב בו מלכה - נציב ונעדכן את מספר העמודה ל- והשורה ל-
- אם לא ניתן להציב בו מלכה נעלה את השורה ב-1.
- במידה ולא ניתן יותר לעלות את העמודה נבצע backtracking:
- נמחק את המלכה מהמיקום האחרון שהצבנו אותה ונעדכן את הטור והשורה בהתאם לאותו מיקום.
- נמחק את המלכה מהמיקום האחרון שהצבנו אותה ונעדכן את מיקומינו בהתאם לטור ולשורה בהתאם בה נמצאת המלכה.
- מאחר שלא ניתן להציב שם מלכה נעדכן את מיקום השורה בפלוס 1.
- במידה ולא ניתן יותר לעלות את העמודה נבצע backtracking:
- בסוף תחזיר התכנה רשימה עם מספרים אשר מיקומם מייצג את התור של הלוח לפי הסדר. כל ערך מיצג את מספר השורה שבה נמצאת המלכה.
![{\displaystyle board[i][j]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b6c2cf80ee3fa7d203911869a1507604ac6b4f86)
- דוגמה:
[1, 3, 0, 2]
מייצג פתרון ללוח מגודל כאשר במיקום:
- ה- יש מלכה.
- ה- יש מלכה.
- ה- יש מלכה.
- ה- יש מלכה.
![{\displaystyle board[0][2]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2ef642d1e5be75f61369856adee133cdd9c111e6)
![{\displaystyle board[1][0]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/463c937c7927f6819eec094046576330dc866c2b)
![{\displaystyle board[2][3]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3f63be83b9971950342351e755a5150a3ab70905)
![{\displaystyle board[3][1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b35de98e3c24301219b810b0a3b5bc710ac6ec10)
דוגמה
עריכה- נלך אל המיקום ה- בלוח.
- ניתן להציב בו מלכה ולכן נבדוק את העמודה ה-
- לא ניתן להציב שם מלכה ולכן נעלה את השורה ב-
- לא ניתן להציב את המלכה ב- ולכן נעלה את השורה ב-
- כן ניתן להציב מלכה ב- , נעדכן את מספר העמודה והשורה
- לא ניתן להציב שם מלכה ולכן נעלה את השורה ל-
- לא ניתן להציב שם מלכה ולכן נעלה את השורה ל-
- לא ניתן להציב שם מלכה ולכן נעלה את השורה ל-
- לא ניתן להציב שם מלכה והגענו לשורה האחרונה ועל כן נבצע backtrack ונמחק את המלכה ב- וכן הלאה.
![{\displaystyle board[0][0]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/68358877d1075edacb2a5dcafe5589be14a50656)
![{\displaystyle board[0][1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/52b70536b76ac45198979030268df1815aa8c9cb)
![{\displaystyle board[1][1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/74a5a747c6fb4532ea5cd42a30f0aa560d703956)
![{\displaystyle board[2][1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7356c3256cc24a35f78051d231fcad119b836a06)
![{\displaystyle board[1][2]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/738dad22b32fddd290a1114899102dfbf722eb84)
![{\displaystyle board[2][2]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/11107256a5b26f413eaea79ed6415df492b28d38)
![{\displaystyle board[3][2]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9ac3637b67506b6211ce05c7ded69f72afd99213)
לכלל המהלכים ניתן לצפות בקישור אל יוטוב בתחתית הדף.
אלגוריתם פתרון
עריכה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)