חידת שמונה המלכות
חידת שמונה המלכות היא חידת שחמט שבה יש למקם שמונה מלכות שחמט על לוח שחמט כך שאף אחת מהן לא מאיימת על אף אחת מחברותיה. החידה היא מקרה פרטי של בעיית n המלכות, בעיה דומה בה יש להציב n מלכות על לוח בגודל n x n.
לחידה 92 פתרונות: 12 פתרונות יסודיים, ומהם מקבלים בעזרת שיקוף וסיבוב הלוח את שאר הפתרונות.
היסטוריה
[עריכת קוד מקור | עריכה]החידה הוצגה לראשונה בשנת 1848 על ידי שחקן השחמט מקס בזל. במשך השנים, מתמטיקאים רבים, לרבות גאוס, חקרו את הבעיה. בשנת 1874 הציע ס. גונת'ר דרך לפתרון בעזרת דטרמיננטות וגלישר שיפר פתרון זה.
החידה כבעיה במדעי המחשב
[עריכת קוד מקור | עריכה]
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
פתרון אפשרי לבעיית שמונה המלכות |
חידת שמונה המלכות משמשת כדוגמה נפוצה לבעיה הניתנת לפתרון בעזרת מחשב, בטכניקה הקרויה "כוח גס", כלומר בדיקת כל המצבים האפשריים, ומציאת אלה מתוכם העונים על תנאי החידה. לשם מיקום המלכות עלינו לבחור 8 משבצות מתוך 64 המשבצות שעל הלוח, כשאין חשיבות לסדר הבחירה, ולכן מספר המצבים האפשריים הוא , כלומר 4,426,165,368 - יותר מארבעה מיליארד. מספר רב מדי של מצבים לבדיקה בידי אדם, אך מספר סביר בהחלט לבדיקה באמצעות מחשב. אפשר לצמצם את מספר המצבים הנבדקים באמצעות אלגוריתם מורכב יותר, למשל כזה שאינו בודק שורה ועמודה שבהם הוצבה כבר מלכה, באלגוריתם כזה יהיו שמונה מצבים להצבת המלכה בשורה הראשונה, שבעה בשורה השנייה וכו' מה שגורר רק מצבים.
כיוון שניסוח החידה פשוט והפתרון איננו טריוויאלי, החידה משמשת כתרגיל נפוץ בתכנות. קיימות שיטות תכנות שונות בהם נתן לממש פתרון, בהן התפשטות אילוצים, תכנות לוגי, אלגוריתמים גנטיים וחיפוש מקומי.
בקורסים בסיסיים במדעי המחשב, נהוג לפתור את החידה באמצעות אלגוריתם רקורסיבי בשיטת הנסיגה. אלגוריתם זה איננו יעיל ביחס לאלגוריתמים ידועים אחרים אך הוא פשוט יחסית למימוש. ניתן לתאר את האלגוריתם בקווים כלליים באופן הבא: התחילו מהשורה העליונה (8) והציבו מלכה בתחילת השורה (א). עברו לשורה הבאה, התחילו מתחילת השורה והתקדמו לסופה עד שתמצאו את המקום הראשון שאינו מאוים על ידי המלכה הקודמת. המשיכו כך שורה אחרי שורה, בכל אחת, מצאו את המקום הראשון בשורה שלא מאוים על ידי המלכות מהשורות הקודמות. אם הגעתם לשורה שבה לא קיים מקום לא מאוים, חזרו לשורה הקודמת והציבו את המלכה במקום הבא שאינו מאוים באותה השורה. יש להמשיך בביצוע האלגוריתם (להתקדם ולסגת במידת הצורך) עד למילוי כל השורות.
השאלה האם ניתן, בהינתן פתרון חלקי, להשלים אותו לפתרון מלא עבור לוח כללי, היא NP שלמה [1]
וריאציות
[עריכת קוד מקור | עריכה]ניתן לשאול שאלה דומה גם לגבי שאר כלי המשחק: מהו המספר המקסימלי של מלכים, צריחים, פרשים או רצים שניתן להציב על הלוח בלי שאף שניים יאיימו זה על זה?
פתרונות | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
|
|
|
שאלה נוספת שניתן לשאול היא - מה המספר המינימלי של כלים שיש להציב כך שכל הלוח יהיה מאוים? (המשבצת עליה מוצב הכלי נחשבת מאוימת).
שאלות אלה ניתן לשאול גם על כלים אגדתיים שונים.
גודל הלוח
[עריכת קוד מקור | עריכה]ניתן לשאול את החידה גם על לוח בגודל אחר מגודל 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].
ראו גם
[עריכת קוד מקור | עריכה]קישורים חיצוניים
[עריכת קוד מקור | עריכה]- פתרון מודרך
- חידת מלכות דומה
- חידת שמונה המלכות, באתר MathWorld (באנגלית)
- The 8 Queen Problem - Numberphile, סרטון בערוץ "Numberphile", באתר יוטיוב (אורך: 7:03) (באנגלית)
- פתרון לחידת 8 המלכות בעברית, באתר G4A