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

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

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

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

היסטוריה

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

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

8 Chess l44.png Chess d44.png Chess l44.png מלכה לבנה Chess l44.png Chess d44.png Chess l44.png Chess d44.png
7 Chess d44.png Chess l44.png Chess d44.png Chess l44.png Chess d44.png Chess l44.png מלכה לבנה Chess l44.png
6 Chess l44.png Chess d44.png מלכה לבנה Chess d44.png Chess l44.png Chess d44.png Chess l44.png Chess d44.png
5 Chess d44.png Chess l44.png Chess d44.png Chess l44.png Chess d44.png Chess l44.png Chess d44.png מלכה לבנה
4 Chess l44.png מלכה לבנה Chess l44.png Chess d44.png Chess l44.png Chess d44.png Chess l44.png Chess d44.png
3 Chess d44.png Chess l44.png Chess d44.png Chess l44.png מלכה לבנה Chess l44.png Chess d44.png Chess l44.png
2 מלכה לבנה Chess d44.png Chess l44.png Chess d44.png Chess l44.png Chess d44.png Chess l44.png Chess d44.png
1 Chess d44.png Chess l44.png Chess d44.png Chess l44.png Chess d44.png מלכה לבנה Chess d44.png Chess l44.png
א ב ג ד ה ו ז ח
פתרון אפשרי לבעיית שמונה המלכות

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

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

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

וריאציות

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

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

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

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

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

גודל הלוח

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

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].

ראו גם

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

הערות שוליים

  1. ^ סדרה A000170, באתר OEIS – האנציקלופדיה המקוונת לסדרות של מספרים שלמים
Logo hamichlol 3.png
הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

אוחזר מתוך "https://www.hamichlol.org.il/w/index.php?title=חידת_שמונה_המלכות&oldid=1782867"