אלגוריתמים ושפות תכנות: פתרון לחידת שמונה המלכות – אלגוריתם לא רקורסיבי באדיבות בנימין גולובטי

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

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

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

הפתרון המצורף מטה, בשפת C, מובא באדיבותו של מר בנימין גולובטי.

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

לחידה זו ישנם 12 פתרונות ייחודיים, ו-92 פתרונות בסה"כ הנוצרים
משיקופים אפקיים, שיקופים אנכיים או סיבוב של לוח השחמט
ב- 1800,900 או 2700.

כל שיקוף יוצר 3 פתרונות נוספים, כאשר מסובבים אותו בתורו, כמתואר למעלה.
בגלל הסימטריות של לוח השחמט, בפרט כאשר מדובר על סדר
זוגי של המטריצה מסדר 8, מספר גדול של הפתרונות הנוצרים חופפים
לפתרונות שכבר התגלו ולכן אינם נספרים.
כאמור, 12 הפתרונות הייחודיים מייצרים 92 פתרונות בסה"כ.

קישורים:

הכללת חידת 8 המלכות ללוח שחמט כמטריצה ריבועית מסדר N

תיאור גרפי של 12 הפתרונות הייחודיים

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

התכנית המצורפת מדפיסה את כל 92 הפתרונות.

דוגמה לפתרון ייחודי מתוך 12 הפתרונות הקיימים46831752 .
פירוש: המלכה הראשונה מוצבת בעמודה הראשונה בשורה הרביעית.
המלכה השנייה מוצבת בעמודה השנייה בשורה השישית.

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

שיקוף אנכי, שיקוף אפקי וסיבובים של הפתרון על לוח השחמט:
הפתרון לאחר סיבוב לוח השחמט 900 ימינה: 41582736.
הפתרון לאחר סיבוב לוח השחמט 1800 ימינה: 74286135.
הפתרון לאחר סיבוב לוח השחמט 2700 ימינה: 36271485.

הפתרון לאחר שיקוף אפקי של לוח השחמט (מימין לשמאל): 25713864.

הפתרון לאחר שיקוף אנכי של לוח השחמט (מלמעלה למטה): 64158273.

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

 

 

פלט התכנית:

 

 

ההערות בגוף התכנית כקובץ טקסט:

המלכה הנוכחית מיוצגת ע"י a ואילו המלכה שכבר הצבנו על הלוח מיוצגת ע"י ind
הבדיקה מתבצעת על הלוח ששורותיו ממוספרות מ-0 עד 7

כל עוד לא חרגנו מגבולות לוח השחמט

בדיקה האם 8 המלכות סודרו במקומן. אם לא, עוברים להדפסת התוצאות.

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

 

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

אם עברנו בהצלחה את שני התנאים הקודמים, יורדים שורה ובודקים
את שאר המלכות אשר הוצבו על הלוח ע"י חזרה ללולאה הראשית.

כלומר, יש התנגשות ואי-אפשר להציב את המלכה החדשה במקומה הנוכחי.

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

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

אם ההפרש בין מיקומי שתי המלכות גדול מאחד, אז מקדמים את המלכה
החדשה מקום אחד קדימה ומעדכנים את ind  כדי להתחיל שוב את הבדיקה.

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

עדכון הסריקה מהסוף להתחלה.

לוקחים את המלכה הבאה ומנסים למקם אותה.

 

את המלכה החדשה נבדוק ביחס למיקומים של המלכה האחרונה שהצבנו.
הבדיקה תחל מהסוף ובהדרגה נגיע לשורה הראשונה, לתחילת לוח השחמט.

 

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

970x90