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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
מהלכים אפשריים של מלכה על לוח בגודל 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 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 המשבצות שעל הלוח, כשאין חשיבות לסדר הבחירה, ולכן מספר המצבים האפשריים הוא \binom{64}{8} = {64! \over 8!56!}, כלומר 4,426,165,368 - יותר מארבעה מיליארד. מספר רב מדי של מצבים לבדיקה בידי אדם, אך מספר סביר בהחלט לבדיקה באמצעות מחשב. אפשר לצמצם את מספר המצבים הנבדקים באמצעות אלגוריתם מורכב יותר, למשל כזה שאינו בודק שורה ועמודה שבהם הוצבה כבר מלכה.

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

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

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

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

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

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

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

ניתן לשאול את החידה גם על לוח בגודל אחר מגודל 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]

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

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

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