حل مشكلة N-Queens باستخدام Python

لحل مشكلتك، يمكننا استخدام خوارزمية بسيطة لفحص وجود أي ملكة على نفس القطر من موضع محدد. يجب عليك أولاً فهم كيفية عمل القطرين الرئيسيين في لوحة الشطرنج.

لنفترض أننا لدينا ملكة واحدة في الموضع (row، col)، سنركز على فحص وجود ملكة أخرى على القطر الرئيسي الأيمن والأيسر.

القطر الأيمن:

• يتحرك الفحص من (row، col) بزيادة الصف والعمود بمقدار واحد في كل خطوة حتى نصل إلى حافة اللوحة.
• خلال كل تحرك، نقوم بفحص ما إذا كان هناك ملكة في الخانة الحالية.
• إذا كان هناك ملكة، فإن الوضع غير صالح.

القطر الأيسر:

• يتحرك الفحص من (row، col) بزيادة الصف ونقصان العمود بمقدار واحد في كل خطوة حتى نصل إلى حافة اللوحة.
• خلال كل تحرك، نقوم بفحص ما إذا كان هناك ملكة في الخانة الحالية.
• إذا كان هناك ملكة، فإن الوضع غير صالح.

وبناءً على هذا الفهم، يمكننا كتابة خوارزمية لفحص القطرين الرئيسيين. إليك مثال على كيفية تنفيذ ذلك بلغة Python:

pythonCopy code
def diagonal_check(board, row, col):
    # Check right diagonal
    for i in range(1, len(board)):
        if row + i < len(board) and col + i < len(board):
            if board[row + i][col + i] == 1:
                return False
        else:
            break
    
    for i in range(1, len(board)):
        if row - i >= 0 and col - i >= 0:
            if board[row - i][col - i] == 1:
                return False
        else:
            break
    
    # Check left diagonal
    for i in range(1, len(board)):
        if row + i < len(board) and col - i >= 0:
            if board[row + i][col - i] == 1:
                return False
        else:
            break
    
    for i in range(1, len(board)):
        if row - i >= 0 and col + i < len(board):
            if board[row - i][col + i] == 1:
                return False
        else:
            break
    
    return True

هذه الوظيفة تأخذ المصفوفة (اللوحة) وموقع الملكة (الصف والعمود) وتقوم بفحص وجود أي ملكة على القطرين الرئيسيين. إذا لم يكن هناك أي ملكة على القطرين، فإن الوظيفة تعيد True، وإلا فإنها تعيد False.

بالطبع! سنواصل الآن مع توضيح بعض النقاط الهامة حول هذا الحل وكيفية تطبيقه في مشكلة N-Queens.

قبل الدخول في تفاصيل الخوارزمية، دعنا نلقي نظرة سريعة على مشكلة N-Queens. في هذه المشكلة، يتعين وضع N ملكات على لوحة الشطرنج بحيث لا تهاجم بعضها البعض. يعني ذلك أنه لا يجب أن تكون هناك ملكتان في نفس الصف أو العمود أو القطر. تُعد هذه مشكلة تحديًا شهيرة في علم الحوسبة.

الآن، سندمج خوارزمية فحص القطرين الرئيسيين التي كتبناها في وظيفة diagonal_check في حل لمشكلة N-Queens. لتحقيق ذلك، سنقوم بتحديد مواقع الملكات على اللوحة بشكل تتابعي ونستخدم وظيفة diagonal_check للتحقق مما إذا كان هناك تعارض في المواقع.

إليك كيف يمكننا تنفيذ ذلك:

pythonCopy code
def solve_n_queens(n):
    def backtrack(row):
        nonlocal result
        if row == n:
            result += 1
            return
        for col in range(n):
            if can_place(row, col):
                board[row][col] = 1
                backtrack(row + 1)
                board[row][col] = 0
    
    def can_place(row, col):
        return row_check[row] == 0 and col_check[col] == 0 and diagonal_check(board, row, col)
    
    # Initialize the board and auxiliary arrays
    board = [[0] * n for _ in range(n)]
    row_check = [0] * n
    col_check = [0] * n
    result = 0
    
    # Start backtracking
    backtrack(0)
    
    return result

# Example usage:
n = 8
print(f"Number of solutions for {n}-Queens problem: {solve_n_queens(n)}")

في هذا الحل، نقوم بتكوين وظيفة solve_n_queens التي تأخذ حجم اللوحة N كمدخل وتُعيد عدد الحلول الممكنة لمشكلة N-Queens. تستخدم هذه الوظيفة تقنية الإرجاع المتكرر (Backtracking) للتحقق من جميع التوزيعات الممكنة.

تحتوي الوظيفة على دالة مساعدة backtrack التي تقوم بالتجريب عبر كل صف في اللوحة وتحاول وضع ملكة في كل خانة من الصف الحالي. إذا كان من الممكن وضع ملكة في الموقع الحالي دون تعارض، فإنها تقوم بوضع الملكة وتقوم بالتوجه إلى الصف التالي. إذا تم وضع جميع الملكات بنجاح، يتم زيادة العداد result بواحد.

تحتوي الوظيفة أيضًا على دالة مساعدة can_place التي تقوم بالتحقق مما إذا كان بإمكاننا وضع ملكة في موضع محدد دون تعارض في الصف والعمود والقطر.

باستخدام هذا الحل، يمكننا بسهولة حساب عدد الحلول الممكنة لمشكلة N-Queens بشكل فعال وبدون تعارضات.