חידת 8 המלכות

חידת 8 המלכות היתה פופולרית מאוד בראיונות עבודה, ובדרך כלל משמשת להדגים את יעילות שיטת backtraking, כאן נדגים משהוא אחר. החידה הולכת כך: על לוח שחמט צריך לסדר 8 מלכות (מלכה יכולה לנוע לאורך טורים שורות ואלכסונים ללא הגבלה). סידור המלכות על פני הלוח צריך להיות כזה שאף מלכה אינה עומדת על המשבצות עליהן חולשת מלכה אחרת (בשליטת מלכה אחרת). זאת אומרת שבכל טור בלוח ובכל שורה בלוח צריכה לעמוד רק מלכה אחת. ועל כל אלכסון בלוח לא תהיה יותר ממלכה אחת.

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

היות שבחידה שלנו אין יותר ממלכה אחת על כל טור וכל שורה, אנו יכולים להשתמש בפרמוטציות של שמונה מספרים 0-7 מה שיתן לנו את כל הסידורים השונים של 8 מלכות על הלוח כאשר אין יותר ממלכה אחת על כל טור או כל שורה.

נראה את התוכנית ונמשיך להסביר -

from itertools import permutations cols = range(8) for p in permutations(cols): if (len(set(p[c]+c for c in cols)) == len(set(p[c]-c for c in cols))==8): print (p)

אנו מייבאים מתוך הספריה itertools את המתודה permutations שמייצרת לנו סידורים של המספרים 0-7 במיקומים שונים בלי לחזור על אותו מספר פעמיים - משהו כזה -

(6, 2, 7, 1, 4, 0, 5, 3)

(6, 3, 1, 4, 7, 0, 2, 5)

(6, 3, 1, 7, 5, 0, 2, 4)

(6, 4, 2, 0, 5, 7, 1, 3)

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

לשם כך, צריך לחקור את הלוח וניתן לגלות עליו את הדבר הבא -

בלוח השחמט יש שני סוגי אלכסונים - כאלה שחלקם הגבוה הוא בצד שמאל וחלקם הנמוך בצד ימין (כמו האלכסון בריבוע הימני המסומן במספר 7) - נקרא להם אלכסונים יורדים. והסוג השני הוא אלכסונים שמתחילים בצד שמאל למטה ומסיימים בצד ימין למעלה, (כמו אלה המסומנים בריבוע השמאלי בספרה 0) נקרא להם אלכסונים עולים. מלכה הנמצאת במקום טוב באמצע הלוח, חולשת הן על אלכסונים עולים והן על אלכסונים יורדים. אנו צריכים לוודא שעל שני הסוגים לא עומדת מלכה אחרת. התבוננות בלוחות מגלה כי ניתן לייצג את האלכסונים היורדים בנוסחה הבאה: מספר השורה+מספר הטור, כך שכל מלכה שתעמוד על אותו אלכסון יורד תהיה על אותו מספר. ואותו הדבר לגבי האלכסונים העולים אותם מקבלים לפי הנוסחה: מספר טור - מספר שורה (מספר השורה פחות מספר הטור), אחרי שמיישמים את הנוסחה לכל הלוח אנו יכולים לראות למשל שכל המשבצות שתוצאת הנוסחה בתוכן היא 3- הן על אותו אלכסון עולה (בלוח השמאלי).

אם כך, מה שאנחנו מחפשים הוא פרמוטציה, permutation, של המספרים 0-7 (המייצגים 8 שורות בלוח השחמט) במיקומים כאלה על הלוח (למשל לוח האלכסונים היורדים) שכל מלכה תעמוד על משבצת בעלת מספר אחר (כלומר כל אחת על אלכסון שונה) וכך גם בלוח של האלכסונים העולים.

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

מכאן השורה בקוד -

if (len(set(p[c]+c for c in cols))== len(set(p[c]-c for c in cols))==8):

אנו רוצים שהאורך len של סט set המופעל על נוסחת האלכסונים העולים של כל מלכה יהיה שווה ל-8. כנ"ל לגבי האלכסונים היורדים. אם הסט (שאינו מכיל פעמיים את אותו המספר - המייצג אלכסון) שווה ל- 8 זה אומר שכל מלכה על אלכסון שונה. p[c]-c למשל מייצגת את נוסחת האלכסונים העולים [p[c הוא מספר השורה (מסומן בירוק בלוחות שלנו) ו- c הוא מספר הטור (מסומן בצהוב בלוחות שלנו).

סה"כ מתקבלים 92 פתרונות של החידה (מתוך 4 מיליארד אפשרויות בערך) - מוזמנים להעתיק ולנסות במחשב שלכם.

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

1. 0, 5, 7, 2, 6, 3, 1, 4

2. 0, 6, 3, 5, 7, 1, 4, 2

3. 0, 6, 4, 7, 1, 3, 5, 2

משמעות הפתרון הראשון, מלכה ראשונה בטור השמאלי ביותר בשורה 0 (שהיא השורה הראשונה), המלכה השנייה (שנייה ברשימה) בטור השני משמאל בשורה 6 (אם מתחילים מ-0 המספר 5 הוא השורה הששית) המלכה השלישית, בטור השלישי משמאל בשורה העליונה ביותר (השורה השמינית המיוצגת על ידי הספרה 7) וכו'.