חידת שמונה המלכות – הבדלי גרסאות

'''חידת שמונה המלכות''' היא [[חידת שחמט]] שבה יש למקם שמונה [[מלכה (שחמט)|מלכות שחמט]] על [[לוח שחמט]] כך שאף אחת מהן לא מאיימת על אף אחת מחברותיה. החידה היא מקרה פרטי של '''בעיית n המלכות''', בעיה דומה בה יש להציב n מלכות על לוח בגודל n x n{{כ}}.

 

 

==היסטוריה==

חידת שמונה המלכות משמשת כדוגמה נפוצה לבעיה הניתנת לפתרון בעזרת מחשב, בטכניקה הקרויה "[[כוח גס]]", כלומר בדיקת כל המצבים האפשריים, ומציאת אלה מתוכם העונים על תנאי החידה. לשם מיקום המלכות עלינו לבחור 8 משבצות מתוך 64 המשבצות שעל הלוח, כשאין חשיבות לסדר הבחירה, ולכן מספר המצבים האפשריים הוא <math>\binom{64}{8} = {64! \over 8!56!}</math>, כלומר 4,426,165,368 - יותר מארבעה מיליארד. מספר רב מדי של מצבים לבדיקה בידי אדם, אך מספר סביר בהחלט לבדיקה באמצעות [[מחשב]]. אפשר לצמצם את מספר המצבים הנבדקים באמצעות [[אלגוריתם]] מורכב יותר, למשל כזה שאינו בודק שורה ועמודה שבהם הוצבה כבר מלכה, באלגוריתם כזה יהיו שמונה מצבים להצבת המלכה בשורה הראשונה, שבעה בשורה השנייה וכו' מה שגורר רק <math>8!</math> מצבים.

 

 

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

 

==וריאציות==

{| class="toccolours mw-collapsible mw-collapsed" width="1000"

! פתרונות