תכנות — שיעור 87 7/May/2009    

הצבת מלכות על לוח שחמט

אנו רוצים להציב 8 מלכות על לוח שחמט כך שלא "תאיימנה" אחת על רעותה. הנה פתרון עבור 5 מלכות על לוח של lteq1.png

כלומר מלכות במשבצות:

a1 b4 c2 d5 e3
אנו נעדיף את הסימון הבא:
lteq2.png
כלומר את המשבצות כזוגות של טור ושורה:
lteq3.png
ובפייתון נתאר את קבוצת המשבצות הללו בצורה חסכונית כרשימת השורות:
[0, 3, 1, 4, 2]
שימו לב: אין צורך לציין את הטור כי הוא נובע מהמקום ברשימה.

נמשיך לדון בבעייה מאוחר יותר. תחילה נקל על עצמנו.

הצבת צריחים

ניתן להציב 3 צריחים על לוח של lteq4.png כך שלא יהיה ביניהם איום ב-6 הצורות הבאות:

lteq5.png

למעשה מדובר ב-6 האפשרויות לסדר בסדרה את lteq6.png

תמורות (permutations) ועצרת (factorial)

נגדיר את פעולת עצרת (factorial) באופן הבא:
lteq7.png
לדוגמא:
lteq8.png

קל לראות כי מספר התמורות שהן האפשרויות בהן ניתן לסדר lteq9.png אברים שונים הוא lteq10.png

תרגילים

  1. השלם תרגילים קודמים.
  2. קרא היטב את הסיכום שלמעלה.
  3. כתוב פונקציה def rows_to_chess_str(rows) שמקבלת רשימת מספרים lteq11.png שמתארים סדרת משבצות על לוח שחמט, בסימון שלנו את המשבצות:
    lteq12.png
    ומחזירה מחרוזת של שמות שחמט של המשבצות עם רוחים בינהן.
    לדוגמא (כמו למעלה): אם הפונציה תקבל lteq13.png אז היא תחזיר את המחרוזת:
    "a1 b4 c2 d5 e3"
חזרה לעמוד האם