مسألة الملكات الـN

طريقان إلى نفس الفكرة

المتطلبات قبل البداية

المفاهيم الأساسية

المطلوب: ضع N ملكة على رقعة N×N بحيث لا تهاجم أي ملكة أخرى، واطبع كل الحلول الممكنة. والملكة في الشطرنج تهاجم في صفّها وعمودها وقطريها بلا حدود.

1لماذا لا تنفع القوة الغاشمة

لو جرّبت كل توزيعات الملكات الثماني على 64 مربعًا لواجهت أكثر من أربعة مليارات حالة. وحتى لو حسّنتها قليلًا بوضع ملكة في كل صف، يبقى عندك Nᴺ احتمالًا لـ N=8‏، أي 16.7 مليون. المشكلة ليست في الحساب، بل في أنك تكتشف الفشل في آخر خطوة بعد أن بنيت الحل كاملًا.

2التمثيل الذكي: ملكة واحدة لكل صف

أول قرار تصميمي، وهو يحذف نصف المسألة مجانًا: بما أن ملكتين في نفس الصف تتهاجمان حتمًا، فكل حل فيه ملكة واحدة بالضبط في كل صف. فلا نسأل «أين أضع الملكات؟» بل «ما عمود ملكة كل صف؟». الحل صار قائمة أعمدة بطول N‏.

3متى تتهاجم ملكتان؟ الحيلة الحسابية

بقي الصف محلولًا بالتمثيل، فبقي ثلاثة فحوص. والعمود سهل، أما القطران فلهما خدعة جميلة:

وبهذا يصير الفحص ثلاث عمليات طرح وجمع بدل المرور على كل ملكة موضوعة. نحتفظ بثلاث مجموعات: الأعمدة المستعملة، وقيم r - c المستعملة، وقيم r + c المستعملة. والفحص كله:

if col in cols or (row - col) in diag or (row + col) in anti:
    continue

4التراجع: ابنِ، وتراجع لحظة الاستحالة

فكرة التراجع (backtracking) في جملة: ابنِ الحل جزءًا جزءًا، وفي اللحظة التي يصير فيها الجزء الحالي مستحيلًا، ارجع وجرّب غيره. الفرق عن القوة الغاشمة أنك تقطع فرعًا كاملًا من الاحتمالات دفعة واحدة، لا احتمالًا واحدًا.

وكل خطوة تراجع تتطلّب التنظيف: ترفع الملكة من اللوح، وتمسح تسجيلها من المجموعات الثلاث. نسيان التنظيف هو الخطأ الأول في التراجع، لأن اللوح يبقى ملوّثًا بمحاولة فاشلة.

5التحقّق من المدخلات: اقرأ النص حرفيًا

هذا الجزء يُفقد فيه الكثير من الدرجات بلا سبب، لأن الرسائل محدّدة بالضبط:

والترتيب مهم: تفحص العدد أولًا، ثم النوع، ثم القيمة. ولا تستورد شيئًا غير sys‏، فالمشروع يمنع غيره صراحة.

كيف يعمل؟

ثلاث صور: دورة التراجع، ثم شجرة البحث الحقيقية لـ N=4، ثم متى تتهاجم ملكتان.

شكل 15، دورة التراجع كاملة: ضع، انزل، وإن فشلت ارفع وجرّب التالي، وإن نفدت الأعمدة فتراجع صفًا للأعلى.

شكل 16، شجرة البحث لـ N=4 من العمود 0 والعمود 1. الفرع الأيسر كله يموت عند الصف 2، والتراجع يقطعه دفعة واحدة بدل تجربة ما تحته.

شكل 17، شجرة قرار التهديد: الصف محلول بالتمثيل، فيبقى العمود والقطران، وكل قطر يُختصر في عدد واحد.

الحل خطوة بخطوة

نكتب الحل، نشغّله على المثالين المطلوبين، نفحص رسائل الخطأ، ثم نقيس أثر التقليم بالأرقام. كل مخرج تحت حقيقي.

الخطوة 1، الحل

#!/usr/bin/python3
"""Solve the N queens puzzle."""
import sys


def solve(n, row, cols, diag, anti, board, out):
    """Place one queen per row, backtracking when a row has no safe column."""
    if row == n:
        out.append([pair[:] for pair in board])
        return
    for col in range(n):
        if col in cols or (row - col) in diag or (row + col) in anti:
            continue
        cols.add(col)
        diag.add(row - col)
        anti.add(row + col)
        board.append([row, col])
        solve(n, row + 1, cols, diag, anti, board, out)
        board.pop()
        anti.discard(row + col)
        diag.discard(row - col)
        cols.discard(col)


def main():
    """Validate the argument, then print every solution."""
    if len(sys.argv) != 2:
        print("Usage: nqueens N")
        sys.exit(1)
    try:
        n = int(sys.argv[1])
    except ValueError:
        print("N must be a number")
        sys.exit(1)
    if n < 4:
        print("N must be at least 4")
        sys.exit(1)
    out = []
    solve(n, 0, set(), set(), set(), [], out)
    for sol in out:
        print(sol)


if __name__ == "__main__":
    main()

لاحظ [pair[:] for pair in board] في حفظ الحل: بدونها تحفظ إشارة إلى اللوح نفسه الذي سيتغيّر بعد سطر واحد، فتخرج لك حلول متطابقة أو فارغة.

الخطوة 2، المثالان المطلوبان

$ ./0-nqueens.py 4
[[0, 1], [1, 3], [2, 0], [3, 2]]
[[0, 2], [1, 0], [2, 3], [3, 1]]

$ ./0-nqueens.py 6
[[0, 1], [1, 3], [2, 5], [3, 0], [4, 2], [5, 4]]
[[0, 2], [1, 5], [2, 1], [3, 4], [4, 0], [5, 3]]
[[0, 3], [1, 0], [2, 4], [3, 1], [4, 5], [5, 2]]
[[0, 4], [1, 2], [2, 0], [3, 5], [4, 3], [5, 1]]

الخطوة 3، رسائل الخطأ ورمز الخروج

$ ./0-nqueens.py ; echo "exit=$?"
Usage: nqueens N
exit=1

$ ./0-nqueens.py hello ; echo "exit=$?"
N must be a number
exit=1

$ ./0-nqueens.py 3 ; echo "exit=$?"
N must be at least 4
exit=1

الخطوة 4، كيف يبدو الحل على الرقعة

[[0, 1], [1, 3], [2, 0], [3, 2]]   ->   . Q . .
                                        . . . Q
                                        Q . . .
                                        . . Q .

اقرأ القائمة هكذا: الصف 0 ملكته في العمود 1، والصف 1 في العمود 3، وهكذا. تحقّق بعينك أن لا اثنتين تشتركان في عمود أو قطر.

الخطوة 5، لماذا تعمل حيلة القطر

      col0   col1   col2   col3        <- each cell shows (row-col)/(row+col)
row0  +0/0   -1/1   -2/2   -3/3
row1  +1/1   +0/2   -1/3   -2/4
row2  +2/2   +1/3   +0/4   -1/5
row3  +3/3   +2/4   +1/5   +0/6

(0,1) and (1,3):  row-col = -1 and -2  ->  different
                  row+col =  1 and  4  ->  different   ->  safe
(0,1) and (1,2):  row-col = -1 and -1  ->  SAME        ->  same diagonal, attacking

الخطوة 6، امشِ على N=4 خطوة خطوة

الخطوة 7، كم وفّر التقليم فعلًا؟

  N  solutions   placements tried              N^N             N!
  4          2                 60              256             24
  5         10                220            3,125            120
  6          4                894           46,656            720
  7         40              3,584          823,543          5,040
  8         92             15,720       16,777,216         40,320
  9        352             72,378      387,420,489        362,880
 10        724            348,150   10,000,000,000      3,628,800

العمود الأهم هو الثالث مقابل الرابع: عند N=8 يجرّب الحل 15,720 وضعًا بدل 16.7 مليون ترتيب، أي أقل من واحد بالألف. وكلما كبرت N اتّسعت الفجوة.

N=8 :     92 solutions,       15,720 placements tried,  0.002s
N=10:    724 solutions,      348,150 placements tried,  0.045s
N=12: 14,200 solutions,   10,103,868 placements tried,  1.234s

اعتقاد شائع × الحقيقة

أين نستخدمه فعليًا؟

جرّب بنفسك

بطاقات مراجعة سريعة

تحقّق من فهمك