N-Queens II
מלכה על לוח שחמט תוקפת כל משבצת בשורה שלה, בעמודה שלה ולאורך שני האלכסונים שלה, גם כשהמשבצת רחוקה. נתון לך מספר שלם n. החזר את מספר הדרכים להציב n מלכות על לוח n × n כך שאף שתי מלכות לא יתקפו זו את זו.
שתי דרכים נחשבות שונות אם יש משבצת שבה באחת מהן יש מלכה ובשנייה היא ריקה. לכן לוח ותמונת המראה שלו נחשבים לשתי דרכים, אף על פי שהם נראים זהים.
פונקציה
- ninteger
- גודל הלוח ומספר המלכות
- מחזירהinteger
- מספר הדרכים להציב את המלכות כך שאף אחת מהן לא תתקוף אחרת
אילוצים
1 ≤ n ≤ 12- התשובה עבור
n = 12היא 14,200, ולכן היא נכנסת למספר שלם בן 32 סיביות.
דוגמאות
- קלט
- n = 4
- פלט
- 2
- הסבר
- אם כותבים מלמעלה למטה את העמודה שבה נמצאת המלכה בכל שורה, שני הלוחות הם
1, 3, 0, 2ו־2, 0, 3, 1. כל אחד מהם הוא תמונת ראי של האחר, והם נחשבים לשתי דרכים. כל בחירה אחרת מציבה שתי מלכות באותה עמודה או על אותו אלכסון.
- קלט
- n = 3
- פלט
- 0
- הסבר
- מלכה בפינה השמאלית העליונה משאירה רק את הקצה הימני של השורה האמצעית, ואז אין בשורה התחתונה אף משבצת בטוחה. הפינה הימנית העליונה נכשלת באותו אופן, ומלכה באמצע השורה העליונה תוקפת את כל שלוש המשבצות של השורה האמצעית. לכן אף לוח לא מתאים.
+10 בדיקות נסתרות בשליחה
שאלת המשך
האם אפשר לספור רק את הלוחות שנותרים שונים לאחר סיבוב ושיקוף של הלוח? עבור n = 8, 92 הלוחות מתחלקים ל־12 קבוצות כאלה.
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
שתי מלכות באותה שורה תוקפות זו את זו, ולכן בכל שורה יש בדיוק מלכה אחת. מה נשאר לבחור אחרי שיודעים זאת?
מלאו את הלוח שורה אחת בכל פעם, מלמעלה למטה. ברגע שמלכה חדשה מותקפת, נטשו את הלוח החלקי הזה, כי שום דבר שתוסיפו מתחת לא יוכל לתקן אותו. כדי לבדוק משבצת בלי להסתכל על הלוח כולו, זכרו באילו עמודות ובאילו אלכסונים כבר יש מלכה. בכיוון אחד של האלכסונים,
row + colזהה בכל המשבצות, ובכיוון השניrow - colזהה.כתבו
place(row), שמחזירה כמה לוחות מלאים אפשר להשלים מכאן. היא מחזירה 1 כאשרrow == n. אחרת, היא מנסה כל עמודהcשהעמודה שלה, האלכסוןrow + cוהאלכסוןrow - cשלה פנויים: סמנו את שלושתם, הוסיפו אתplace(row + 1)לסכום מצטבר, ואז בטלו את הסימונים שלהם. התשובה היאplace(0).
פתרון
מיקום נקבע על ידי בחירת עמודה אחת לכל שורה, מכיוון ששתי מלכות באותה שורה תמיד תוקפות זו את זו. עדיין יש n^n אפשרויות, בערך 8.9 × 10^12 עבור n = 12, ולכן אי אפשר לרשום את כולן. שני רעיונות פותרים את הבעיה. בונים את הלוח שורה אחר שורה וזונחים לוח חלקי ברגע שמלכה מותקפת, מה שמצמצם את החיפוש לפחות ממיליון לוחות חלקיים עבור n = 12. בנוסף, מתעדים אילו עמודות ואלכסונים תפוסים, כך שבדיקת משבצת דורשת שלוש גישות במקום לסרוק כל מלכה שהוצבה עד כה.
נסו כל סידור שבו יש מלכה אחת בכל שורה
נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר
האינטואיציה
בכל שורה חייבת להיות בדיוק מלכה אחת, לכן הצבה היא רשימה cols שבה cols[r] היא העמודה של המלכה בשורה r. כל איבר יכול להיות אחת מתוך n עמודות, ולכן יש n^n רשימות. עוברים על כולן כמו שמונה־ספרות: מעלים את האיבר האחרון באחד, וכשהוא עובר את n-1, מאפסים אותו ל־0 ומעבירים את הנשא לאיבר שלפניו.
עבור כל רשימה, משווים כל זוג שורות i < j. שתי המלכות מאיימות זו על זו כשהן חולקות עמודה, cols[i] == cols[j], או אלכסון. באלכסון, ירידה של שורה אחת מזיזה אותך עמודה אחת שמאלה או ימינה, ולכן שתי מלכות חולקות אלכסון בדיוק כאשר הפער בין העמודות שווה לפער בין השורות: |cols[i] - cols[j]| == j - i. רשימה שעוברת את הבדיקה של כל זוג היא לוח תקין אחד. מכיוון שכל רשימה נבדקת, אף אחת לא מוחמצת ואף אחת לא נספרת פעמיים.
השיטה איטית כי היא אף פעם לא מפסיקה מוקדם. שתי מלכות באותו אלכסון בשתי השורות הראשונות חורצות את גורל הלוח, ובכל זאת המונה עדיין מנסה את כל n^(n-2) הדרכים למלא את השורות האחרות. עבור n = 8 מדובר ב־16,777,216 רשימות כדי למצוא 92 לוחות. עבור n = 12 מדובר בכ־8.9 × 10^12 רשימות. אפילו בקצב של ננו־שנייה לרשימה, מדובר בכ־2.5 שעות.
אלגוריתם
- מתחילים כשכל הערכים ב-
colsהם אפס: כל מלכה בעמודה 0. - בודקים כל זוג שורות
i < j: הרשימה אינה תקינה אםcols[i] == cols[j]או|cols[i] - cols[j]| == j - i. - אם אף זוג אינו מתנגש, מוסיפים 1 למונה.
- מקדמים את
colsכמו מד מרחק: מהשורה האחרונה כלפי מעלה, מאפסים כל ערך ששווה ל-n-1ל-0, ואז מוסיפים 1 לערך הראשון שאינו כזה. - כשכל הערכים היו
n-1, כלn^nהרשימות כבר נבדקו: מחזירים את המונה.
def totalNQueens(n):
def is_valid(cols):
# cols[r] is the column of the queen in row r, so rows never clash.
for i in range(n):
for j in range(i + 1, n):
if cols[i] == cols[j] or abs(cols[i] - cols[j]) == j - i:
return False
return True
cols = [0] * n
count = 0
while True:
if is_valid(cols):
count += 1
# Move to the next placement, like an odometer with n digits in base n.
row = n - 1
while row >= 0 and cols[row] == n - 1:
cols[row] = 0
row -= 1
if row < 0:
return count
cols[row] += 1חזרה לאחור באמצעות קבוצות עמודות ואלכסונים
האינטואיציה
מקמו את המלכות שורה אחר שורה, מלמעלה, ובדקו כל מלכה חדשה ברגע שממקמים אותה. אם היא מאוימת, אין דרך למלא את השורות שמתחתיה שתוכל לתקן זאת, לכן דלגו מיד על המשבצת. אם היא בטוחה, בצעו קריאה רקורסיבית לשורה הבאה, וכשהקריאה הזאת חוזרת, הסירו את המלכה ונסו את העמודה הבאה. קריאה שמגיעה לשורה n הציבה n מלכות בטוחות ונחשבת כלוח אחד. זוהי נסיגה לאחור, והיא גוזמת ביעילות: עבור n = 12 היא מבקרת ב-856,189 לוחות חלקיים במקום ב-8.9 × 10^12 לוחות מלאים.
החצי השני הוא בדיקה מהירה של משבצת. השורות שמתחת ריקות, ובשורה של המלכה החדשה אין מלכות אחרות, ולכן רק שלושה קווים יכולים לאיים על המשבצת (row, c): העמודה שלה, האלכסון / והאלכסון \. לכל המשבצות שעל אותו אלכסון / יש אותו ערך row + c, מ-0 עד 2n-2. לכל המשבצות שעל אותו אלכסון \ יש אותו ערך row - c, מ--(n-1) עד n-1, ולכן נוסיף n-1 כדי לקבל אינדקס מ-0 עד 2n-2. החזיקו שלושה מערכי דגלים: cols בגודל n, ו-diag ו-anti בגודל 2n-1. המשבצת בטוחה בדיוק כאשר שלושת הדגלים כבויים: שלוש גישות למערך, O(1), בעוד שהשוואה מול כל מלכה שהוצבה עד כה הייתה עולה O(n).
קו יכול להכיל לכל היותר מלכה אחת, ולכן הצבת מלכה מדליקה את שלושת הדגלים שלה והסרתה מכבה אותם שוב, כך שהמערכים חוזרים בדיוק למצבם הקודם. בלוח בגודל 4 על 4, מלכה ב-(0, 0) מסמנת את cols[0], את diag[0] ואת anti[3]. בשורה 1, העמודה 1 נמצאת על anti[3], ולכן מדלגים עליה בלי לבדוק את המלכה עצמה.
בשורה הראשונה יש n עמודות אפשריות, בשנייה לכל היותר n-1, וכן הלאה, ולכן החיפוש חסום על ידי O(n!), והאלכסונים מצמצמים אותו הרבה מתחת לכך. עבור n = 12 הלולאות בודקות בסך הכול 10,103,868 משבצות. הרקורסיה מגיעה לעומק של n קריאות, והמערכים מכילים בערך 5n דגלים, לכן דרישת המקום היא O(n).
אלגוריתם
- צרו שלושה מערכי דגלים, כולם כבויים:
colsעםnאיברים, ו-diagו-antiעם2n-1איברים כל אחד. - כתבו את
place(row). אםrow == n, החזירו 1: בכל שורה יש מלכה בטוחה. - אחרת, עבור כל עמודה
c, דלגו עליה אםcols[c],diag[row + c]אוanti[row - c + n - 1]מופעלים. - עבור עמודה בטוחה, הפעילו את שלושת הדגלים, הוסיפו את
place(row + 1)לסך הכול, ואז כבו אותם. - החזירו את הסך הכול. התשובה היא
place(0).
def totalNQueens(n):
cols = [False] * n # cols[c]: column c holds a queen
diag = [False] * (2 * n - 1) # diag[r + c]: that / diagonal holds a queen
anti = [False] * (2 * n - 1) # anti[r - c + n - 1]: that \ diagonal holds a queen
def place(row):
if row == n:
return 1 # a queen in every row: one complete board
count = 0
for c in range(n):
if cols[c] or diag[row + c] or anti[row - c + n - 1]:
continue # attacked: three lookups, no scan of the board
cols[c] = diag[row + c] = anti[row - c + n - 1] = True
count += place(row + 1)
cols[c] = diag[row + c] = anti[row - c + n - 1] = False # take it back
return count
return place(0)חזרה לאחור עם מסכות סיביות
האינטואיציה
החיפוש באמצעות קבוצות מהיר, אבל בכל שורה הוא עדיין בודק את כל n העמודות, שרובן מותקפות. מסכת סיביות מאפשרת לדלג ישירות לעמודות הפנויות. נניח שהסיבית c של מספר שלם מייצגת את העמודה c בשורה שעומדים למלא, ונחזיק שלוש מסכות: cols, העמודות שכבר תפוסות, left, המשבצות בשורה זו שנפגעות לאורך אחד מכיווני האלכסון, ו-right, המשבצות שנפגעות לאורך הכיוון האחר.
את המשבצות הפנויות מחשבים בביטוי אחד: free = ~(cols | left | right) & full, כאשר הסיביות הנמוכות של full מכילות n סיביות שערכן 1. הביטוי free & -free מבודד את המשבצת הפנויה הנמוכה ביותר, והחסרתה מאפשרת לעבור לבאה אחריה. כשמניחים מלכה ב-bit ויורדים שורה אחת, העמודה שלה נשארת תפוסה, בעוד שכל התקפת אלכסון זזה עמודה אחת. לכן השורה הבאה מקבלת את cols | bit, את ((left | bit) << 1) & full ואת (right | bit) >> 1. אין צורך לבטל דבר: כל קריאה מקבלת שלושה מספרים שלמים משלה. כאשר cols == full, כל n המלכות הונחו.
ניקח n = 4 ואת המלכה הראשונה בעמודה 1, bit = 0010, כאשר העמודה 0 מיוצגת על ידי הסיבית הימנית ביותר. השורה 1 מקבלת cols = 0010, left = 0100 ו-right = 0001, ולכן free = 1000: העמודה 3 היא האפשרות היחידה, והיא נמצאת בלי לבדוק את העמודות 0, 1 או 2.
החיפוש מבקר באותם לוחות חלקיים כמו גרסת הקבוצות, אבל בכל צעד של הלולאה הוא מניח כעת מלכה. עבור n = 12, מדובר ב-856,188 צעדים במקום 10,103,868 בדיקות של משבצות, עם כמה פעולות של מספרים שלמים בכל צעד. זמן הריצה עדיין חסום על ידי O(n!), והעומק של הרקורסיה הוא n קריאות. קוד R מריץ את אותן מסכות ללא רקורסיה: הוא שומר וקטור של כל הלוחות החלקיים בשורה, ומגדיל את כולם שורה אחת בכל פעם, כך שהוא מחזיק בזיכרון רמה שלמה של לוחות במקום n קריאות.
אלגוריתם
- הגדר את
full = (1 << n) - 1, המסכה של כלnהעמודות. - כתוב את
count(cols, left, right). אםcols == full, החזר 1. - חשב את
free = ~(cols | left | right) & full. - כל עוד
freeאינו 0, קח אתbit = free & -free, הסר אותו מ-free, והוסף לסכום אתcount(cols | bit, ((left | bit) << 1) & full, (right | bit) >> 1). - החזר את הסכום. התשובה היא
count(0, 0, 0).
def totalNQueens(n):
full = (1 << n) - 1 # bit c stands for column c of the current row
def count(cols, left, right):
# cols: columns taken. left, right: squares of this row hit along a diagonal.
if cols == full:
return 1 # every column used: n queens placed
total = 0
free = full & ~(cols | left | right)
while free:
bit = free & -free # the lowest free square
free -= bit
# Moving down a row shifts each diagonal attack one column over.
total += count(cols | bit, ((left | bit) << 1) & full, (right | bit) >> 1)
return total
return count(0, 0, 0)
מלכודות ומקרי קצה
החיפוש עצמו קצר. רוב הבאגים נמצאים בחישוב האלכסונים ובשלב הביטול.
- שימוש ב־
row - cכאינדקס בלי להוסיףn-1. ב-Java הפעולה תגרום לשגיאה, ב-C היא תקרא זיכרון מחוץ למערך, וב-Pythonanti[-2]יקרא בשקט את הדגל של אלכסון אחר, ולכן הספירה תהיה שגויה בלי שתתקבל שגיאה. - הגדרת מערכי האלכסונים עם
nאיברים. בלוחn × nיש2n-1אלכסונים בכל כיוון. - בדיקת כיוון אלכסוני אחד בלבד, או בדיקת העמודות בלבד. אלכסונים בשני הכיוונים תוקפים.
- שכחה לכבות את הדגלים לאחר שהקריאה הרקורסיבית חוזרת. כל ענף מאוחר יותר יראה מלכות שכבר אינן על הלוח, והספירה תרד.
- השמטת
& fullבעת חישובfree.~xגם מסמן כל ביט מעל עמודהn-1, ולכן הלולאה בוחרת משבצות מחוץ ללוח, וב-Python או ב-Ruby, שבהן למספרים שלמים אין רוחב קבוע,freeהופך לשלילי והלולאה לעולם לא מסתיימת. - התייחסות לתמונות מראה כאילו הן לוח אחד. הבעיה סופרת אותן בנפרד: עבור
n = 4יש 2 לוחות, והם תמונות מראה זה של זה. - טיפול שגוי בלוחות קטנים באמצעות מקרים מיוחדים. עבור
n = 1יש לוח אחד, ואילו עבורn = 2ועבורn = 3אין לוחות. החיפוש מטפל נכון בכל שלושת המקרים ללא מקרה מיוחד.
שאלות נפוצות4
מהי סיבוכיות הזמן של N-Queens II?
החיפוש עם חזרה לאחור חסום על ידי O(n!): בשורה הראשונה יש n אפשרויות, בשורה הבאה לכל היותר n-1, וכן הלאה. בדיקות האלכסונים מצמצמות את החיפוש הרבה מתחת לחסם הזה, ל־856,189 לוחות חלקיים עבור n = 12. לא ידועה שיטה פולינומית לספירת הפתרונות, ולכן חיפוש כזה הוא הפתרון המקובל. סיבוכיות המקום היא O(n).
איך אפשר לדעת על איזו אלכסונית נמצא ריבוע?
התקדמות בצעד אחד לאורך אלכסון / מוסיפה 1 לשורה ומחסירה 1 מהעמודה, ולכן row + col לעולם אינו משתנה. התקדמות לאורך אלכסון \ מוסיפה 1 לשניהם, ולכן row - col לעולם אינו משתנה. כל סכום מציין אלכסון אחד, והוספת n-1 להפרש הופכת אותו לאינדקס במערך מ-0 עד 2n-2.
מה ההבדל בין N-Queens ל-N-Queens II?
ב־N-Queens מבקשים להציג כל לוח באמצעות שורות טקסט. ב־N-Queens II שואלים רק כמה לוחות כאלה יש. החיפוש משתמש באותה שיטת נסיגה, אבל לצורך הספירה אין צורך לשמור לוח בזיכרון, אלא רק את קבוצות העמודות והאלכסונים, ולכן הוא מהיר וקל יותר. זו גם הסיבה שגרסת מסכת הסיביות מתאימה כאן באופן טבעי.
האם אפשר להשתמש בסימטריה כדי להאיץ את פתרון N-Queens II?
כן. שיקוף של לוח משמאל לימין יוצר לוח תקין נוסף, ולכן הלוחות שבהם המלכה הראשונה נמצאת בחצי השמאלי תואמים לאלה שבהם היא נמצאת בחצי הימני. סופרים את הלוחות שבהם המלכה הראשונה נמצאת בעמודות 0 עד n/2 - 1 ומכפילים את המספר הזה ב-2. כאשר n אי-זוגי, מוסיפים פעם אחת את הלוחות שבהם המלכה הראשונה נמצאת בעמודה האמצעית. כך מצמצמים את החיפוש בחצי.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
Python
def totalNQueens(n):
# כתבו כאן את הקודמקרה 1
מקרה 2
קלט
n = 4
צפוי
2