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 بتات منخفضة مضبوطة. يعزل 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 يقرأ ذاكرة خارج المصفوفة، وفي Python تقرأanti[-2]بهدوء علامة قطر آخر، لذا يكون العدد خاطئًا دون ظهور أي خطأ. - تحديد حجم مصفوفات الأقطار لتحتوي على
nعناصر. تحتوي لوحةn × nعلى2n-1قطرًا في كل اتجاه. - التحقق من اتجاه واحد للأقطار فقط، أو من الأعمدة فقط. كلا اتجاهَي الأقطار يتيحان الهجوم.
- نسيان إيقاف العلامات بعد انتهاء الاستدعاء التكراري. عندها يرى كل فرع لاحق ملكات لم تعد على اللوحة، وينخفض العدد.
- إغفال
& fullعند حسابfree. يضبط~xأيضًا كل البتات التي تتجاوز العمودn-1، لذا تختار الحلقة مربعات خارج اللوحة، وفي Python أو Ruby، حيث لا يكون للأعداد الصحيحة عرض ثابت، تصبحfreeسالبة ولا تنتهي الحلقة أبدًا. - اعتبار الصور المعكوسة لوحة واحدة. تحتسبها المسألة على نحو منفصل: لدى
n = 4لوحتان، وهما صورتان معكوستان إحداهما للأخرى. - التعامل مع اللوحات الصغيرة بحالات خاصة على نحو خاطئ. لدى
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 ومسألة الملكات N II؟
تطلب مسألة N-Queens إيجاد كل لوحة، معروضة على هيئة صفوف من النص. أما N-Queens II فتطلب معرفة عدد اللوحات فقط. يستخدم البحث أسلوب التراجع نفسه، لكن العد لا يتطلب الاحتفاظ بلوحة في الذاكرة، بل مجموعات الأعمدة والأقطار فقط، لذا فهو أسرع وأخف. وهذا ما يجعل استخدام الأقنعة الثنائية مناسبًا هنا أيضًا.
هل يمكنك استخدام التناظر لتسريع حل مسألة الملكات الثماني II؟
نعم. إن عكس اللوحة من اليسار إلى اليمين يعطي لوحة صالحة أخرى، لذا فإن اللوحات التي يكون فيها الوزير الأول في النصف الأيسر تطابق تلك التي يكون فيها في النصف الأيمن. احسب اللوحات التي يكون فيها الوزير الأول في الأعمدة من 0 إلى n/2 - 1 وضاعف العدد. عندما يكون n فرديًا، أضف مرة واحدة اللوحات التي يكون فيها الوزير الأول في العمود الأوسط. وهذا يقلّص مساحة البحث إلى النصف.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def totalNQueens(n):
# اكتب الكود هناالحالة 1
الحالة 2
المدخلات
n = 4
المتوقع
2