לדלג לתוכן

חידת שמונה המלכות

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

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

לחידה 92 פתרונות: 12 פתרונות יסודיים, ומהם מקבלים בעזרת שיקוף וסיבוב הלוח את שאר הפתרונות.

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

החידה כבעיה במדעי המחשב

[עריכת קוד מקור | עריכה]
8 מלכה לבנה
7 מלכה לבנה
6 מלכה לבנה
5 מלכה לבנה
4 מלכה לבנה
3 מלכה לבנה
2 מלכה לבנה
1 מלכה לבנה
א ב ג ד ה ו ז ח
פתרון אפשרי לבעיית שמונה המלכות

חידת שמונה המלכות משמשת כדוגמה נפוצה לבעיה הניתנת לפתרון בעזרת מחשב, בטכניקה הקרויה "כוח גס", כלומר בדיקת כל המצבים האפשריים, ומציאת אלה מתוכם העונים על תנאי החידה. לשם מיקום המלכות עלינו לבחור 8 משבצות מתוך 64 המשבצות שעל הלוח, כשאין חשיבות לסדר הבחירה, ולכן מספר המצבים האפשריים הוא , כלומר 4,426,165,368 - יותר מארבעה מיליארד. מספר רב מדי של מצבים לבדיקה בידי אדם, אך מספר סביר בהחלט לבדיקה באמצעות מחשב. אפשר לצמצם את מספר המצבים הנבדקים באמצעות אלגוריתם מורכב יותר, למשל כזה שאינו בודק שורה ועמודה שבהם הוצבה כבר מלכה, באלגוריתם כזה יהיו שמונה מצבים להצבת המלכה בשורה הראשונה, שבעה בשורה השנייה וכו' מה שגורר רק מצבים.

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

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

השאלה האם ניתן, בהינתן פתרון חלקי, להשלים אותו לפתרון מלא עבור לוח כללי, היא NP שלמה [1]

ניתן לשאול שאלה דומה גם לגבי שאר כלי המשחק: מהו המספר המקסימלי של מלכים, צריחים, פרשים או רצים שניתן להציב על הלוח בלי שאף שניים יאיימו זה על זה?

פתרונות
8 מלך לבן מלך לבן
7 מלך לבן מלך לבן
6 מלך לבן מלך לבן
5 מלך לבן מלך לבן
4 מלך לבן מלך לבן
3 מלך לבן מלך לבן
2 מלך לבן מלך לבן
1 מלך לבן מלך לבן
א ב ג ד ה ו ז ח
מלכים - 16
8 צריח לבן
7 צריח לבן
6 צריח לבן
5 צריח לבן
4 צריח לבן
3 צריח לבן
2 צריח לבן
1 צריח לבן
א ב ג ד ה ו ז ח
צריחים - 8
8 רץ לבן רץ לבן רץ לבן רץ לבן רץ לבן רץ לבן רץ לבן רץ לבן
7
6
5
4
3
2
1 רץ לבן רץ לבן רץ לבן רץ לבן רץ לבן רץ לבן
א ב ג ד ה ו ז ח
רצים - 14
8 פרש לבן פרש לבן פרש לבן פרש לבן
7 פרש לבן פרש לבן פרש לבן פרש לבן
6 פרש לבן פרש לבן פרש לבן פרש לבן
5 פרש לבן פרש לבן פרש לבן פרש לבן
4 פרש לבן פרש לבן פרש לבן פרש לבן
3 פרש לבן פרש לבן פרש לבן פרש לבן
2 פרש לבן פרש לבן פרש לבן פרש לבן
1 פרש לבן פרש לבן פרש לבן פרש לבן
א ב ג ד ה ו ז ח
פרשים - 32

שאלה נוספת שניתן לשאול היא - מה המספר המינימלי של כלים שיש להציב כך שכל הלוח יהיה מאוים? (המשבצת עליה מוצב הכלי נחשבת מאוימת).

פתרונות
8
7 מלך לבן מלך לבן מלך לבן
6
5
4 מלך לבן מלך לבן מלך לבן
3
2
1 מלך לבן מלך לבן מלך לבן
א ב ג ד ה ו ז ח
מלכים - 9
8
7 מלכה לבנה
6
5 מלכה לבנה
4 מלכה לבנה
3 מלכה לבנה
2
1 מלכה לבנה
א ב ג ד ה ו ז ח
מלכות - 5
8 צריח לבן צריח לבן צריח לבן צריח לבן צריח לבן צריח לבן צריח לבן צריח לבן
7
6
5
4
3
2
1
א ב ג ד ה ו ז ח
צריחים - 8
8 רץ לבן
7 רץ לבן
6 רץ לבן
5 רץ לבן
4 רץ לבן
3 רץ לבן
2 רץ לבן
1 רץ לבן
א ב ג ד ה ו ז ח
רצים - 8
8
7 פרש לבן
6 פרש לבן פרש לבן פרש לבן פרש לבן
5 פרש לבן
4 פרש לבן
3 פרש לבן פרש לבן פרש לבן פרש לבן
2 פרש לבן
1
א ב ג ד ה ו ז ח
פרשים - 12

שאלות אלה ניתן לשאול גם על כלים אגדתיים שונים.

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

n: 1 2 3 4 5 6 7 8 9 10 11 12 13 14
פתרונות יסודיים 1 0 0 1 2 1 6 12 46 92 341 1,787 9,233 45,752
כל הפתרונות 1 0 0 2 10 4 40 92 352 724 2,680 14,200 73,712 365,596

מספר הפתרונות המדויק באופן כללי אינו ידוע[1].

קישורים חיצוניים

[עריכת קוד מקור | עריכה]
ויקישיתוף מדיה וקבצים בנושא חידת שמונה המלכות בוויקישיתוף

הערות שוליים

[עריכת קוד מקור | עריכה]