תכנות — שיעור 95 1/October/2009    

מלכות על לוח שחמט

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

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

בדיקת אלכסונים

בדיקת איום מלכות

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

הדוגמא בתמונה (שהיא פתרון טוב לצריחים!) מתוארת על ידי התמורה

תרגילים

1. השלם תרגילים קודמים.
2. קרא היטב את הסיכום שלמעלה.
3. כתוב פונקציה def same_diagonal(x0, y0, x1, y1): שמקבלת 4 מספרים שמתארים שתי משבצות ומחזירה True אם המשבצות על אותו אלכסון ומחזירה False אם הן לא על אותו אלכסון שכזה.
   הערה: מַמֵש את הפונקציה ללא שימוש בקבועים: False, True .
4. כתוב פונקציה: def threatless_queens(a): שמקבלת תמורה a (המתארת משבצות של פתרון צריחים) ומחזירה True אם אין זוג משבצות על אותו אלכסון, ומחזירה False אחרת.
5. כתוב תכנית מסכמת לפתרון בעית המלכות: התכנית תקבל כפרמטר את גודל הלוח n (מענין כמובן המקרה: n=8). התכנית:
   • תעבור על כל התמורות.
   • תמצא את התמורות שמהוות פתרון למלכות שאינן מאימות אחת על השניה.
   • תדפיס את הפתרונות למלכות, בסימון משבצות שחמט, בעזרת הפונקציה def rows_to_chess_str(rows) .

   ---

   חזרה לעמוד האם