تعلّم حل مسائل التراجع الخلفي في المقابلات البرمجية باحتراف

ما هي خوارزمية Backtracking ولماذا تهمك في المقابلات البرمجية؟

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

الفكرة الأساسية بسيطة: نبني الحل خطوة بخطوة، وفي كل خطوة نختار احتمالاً مناسباً. إذا اتضح لاحقاً أن هذا الاحتمال يؤدي إلى طريق مسدود، فإننا نتراجع ونجرّب اختياراً آخر. لهذا السبب تُسمى هذه التقنية بالتراجع الخلفي.

هذا الأسلوب مفيد جداً عند التعامل مع المسائل التي تطلب:

• إيجاد جميع الحلول الممكنة.
• إيجاد حل صحيح واحد فقط.
• استكشاف الترتيبات أو التركيبات أو المسارات.
• الالتزام بقيود محددة أثناء بناء الحل.

فهم فكرة الحالة State في مسائل Backtracking

لفهم Backtracking بشكل صحيح، يجب أولاً استيعاب مفهوم State أو الحالة. الحالة هي تمثيل جزئي أو كامل للحل أثناء بنائه.

في العديد من المسائل، لا نصل إلى الحل دفعة واحدة، بل ننتقل من حالة إلى أخرى حتى نصل إلى حالة نهائية صالحة.

مثال توضيحي: مسألة N-Queens

في مسألة N-Queens نريد وضع n ملكات على رقعة شطرنج بحجم n × n بحيث لا تهاجم أي ملكة الأخرى.

الملكة في الشطرنج تتحرك في:

• الصف نفسه.
• العمود نفسه.
• القطرين.

لذلك يكون الحل صحيحاً فقط إذا لم تشترك أي ملكتين في صف أو عمود أو قطر.

يمكن أن تكون الحالة في هذه المسألة تمثيلاً لمواضع بعض الملكات التي وُضعت حتى الآن. ثم نحاول إضافة ملكة جديدة في موضع لا يخالف القيود. إذا لم نجد موضعاً صالحاً، نتراجع إلى الخطوة السابقة ونغيّر الاختيار.

كيف تعمل خوارزمية Backtracking عملياً؟

تعتمد هذه التقنية على ثلاث أفكار مترابطة:

1. بناء الحل تدريجياً.
2. التحقق من صلاحية الاختيار الحالي.
3. التراجع عند فشل المسار الحالي.

عند كل خطوة، نحدد مجموعة الخيارات الممكنة أو ما يُعرف باسم Candidates. بعد ذلك نجرّب كل خيار على حدة. إذا قادنا خيار ما إلى حل صالح، نحتفظ به. وإذا قادنا إلى حالة غير قابلة للاستمرار، نتراجع فوراً.

متى نعرف أن الحالة الحالية صالحة؟

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

في مسألة N-Queens مثلاً، تكون الحالة النهائية صالحة عندما نضع جميع الملكات دون أي تعارض.

القالب العام لحل مسائل Backtracking

من أفضل الطرق لتسهيل هذا النوع من المسائل هو الاعتماد على قالب ذهني ثابت. غالباً ما يتكون الحل من أربع دوال رئيسية:

• is_valid_state: تتحقق مما إذا كانت الحالة الحالية تمثل حلاً نهائياً صالحاً.
• get_candidates: تُعيد الخيارات الممكنة التي يمكن إضافتها للحالة الحالية.
• search: الدالة التراجعية recursive التي تستكشف الحالات.
• solve: نقطة البداية التي تهيّئ البيانات وتستدعي البحث.

وظيفة الدالة is_valid_state

هذه الدالة تستقبل الحالة الحالية وتعيد قيمة منطقية Boolean. دورها هو الإجابة عن السؤال التالي: هل وصلنا إلى حل نهائي صحيح؟

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

وظيفة الدالة get_candidates

هذه الدالة مسؤولة عن استخراج الخيارات التالية الممكنة. جودة هذه الدالة تؤثر كثيراً في كفاءة الحل، لأن تقليل عدد الخيارات غير المفيدة يسرّع البحث بشكل ملحوظ.

في مسألة N-Queens مثلاً، لا نعيد جميع الخانات، بل نعيد فقط الأعمدة التي لا تسبب تعارضاً مع الملكات الموضوعة سابقاً.

وظيفة الدالة search

هذه هي قلب الحل الحقيقي. تقوم بما يلي:

1. فحص ما إذا كانت الحالة الحالية تمثل حلاً صالحاً.
2. إن لم تكن كذلك، تستخرج الخيارات المتاحة.
3. تجرّب كل خيار بإضافته إلى الحالة.
4. تستدعي نفسها بشكل تراجعي.
5. تتراجع بعد انتهاء كل محاولة لإعادة الحالة كما كانت.

هذا التراجع مهم جداً، لأننا نعيد استخدام البنية نفسها للحالة أثناء التنقل بين الاحتمالات المختلفة.

وظيفة الدالة solve

غالباً ما تكون هذه الدالة بسيطة. تقوم بإنشاء الحالة الابتدائية، وتجهيز مصفوفة النتائج إن كانت المسألة تتطلب جميع الحلول، ثم تستدعي search.

مثال عملي: حل مسألة N-Queens

تُعد مسألة LeetCode 51 من أشهر مسائل Backtracking. والمطلوب فيها هو إرجاع جميع الطرق المختلفة لوضع الملكات على الرقعة.

كيف نمثل الحالة بكفاءة؟

قد يبدو من الطبيعي استخدام مصفوفة ثنائية الأبعاد 2D Array لتمثيل الرقعة، لكن هذا ليس الخيار الأكثر كفاءة هنا.

بما أن كل صف سيحتوي على ملكة واحدة فقط، يمكننا تمثيل الحالة باستخدام قائمة أحادية البعد 1D List بحيث تمثل كل قيمة رقم العمود الذي وُضعت فيه الملكة داخل الصف المقابل.

على سبيل المثال، إذا كانت الحالة هي [1, 3, 0, 2] فهذا يعني:

• في الصف الأول، الملكة في العمود الثاني.
• في الصف الثاني، الملكة في العمود الرابع.
• في الصف الثالث، الملكة في العمود الأول.
• في الصف الرابع، الملكة في العمود الثالث.

هذا التمثيل أبسط، ويوفر مساحة، ويسهّل فحص الأعمدة والأقطار.

منطق التحقق من المرشحين

عند محاولة وضع ملكة جديدة، يجب التأكد من أنها لا تتعارض مع أي ملكة سابقة. لذلك نستبعد:

• الأعمدة المستخدمة مسبقاً.
• الخانات الواقعة على القطر الرئيسي.
• الخانات الواقعة على القطر الثانوي.

ويُحسب التعارض القطري من خلال فرق الصفوف والأعمدة.

شكل الحل البرمجي

def solveNQueens(n):
    solutions = []
    state = []
    search(state, solutions, n)
    return solutions


def is_valid_state(state, n):
    return len(state) == n


def get_candidates(state, n):
    if not state:
        return range(n)

    position = len(state)
    candidates = set(range(n))

    for row, col in enumerate(state):
        candidates.discard(col)
        distance = position - row
        candidates.discard(col + distance)
        candidates.discard(col - distance)

    return candidates


def search(state, solutions, n):
    if is_valid_state(state, n):
        solutions.append(state.copy())
        return

    for candidate in get_candidates(state, n):
        state.append(candidate)
        search(state, solutions, n)
        state.pop()

تحويل الحالة إلى تنسيق الإخراج المطلوب

في هذه المسألة، لا يكفي إرجاع مواقع الأعمدة، لأن منصة LeetCode تطلب تمثيل الرقعة كسلاسل نصية تحتوي على Q و..

لذلك نحتاج إلى دالة مساعدة لتحويل كل صف إلى سلسلة نصية مناسبة.

def state_to_string(state, n):
    result = []
    for col in state:
        row = "." * col + "Q" + "." * (n - col - 1)
        result.append(row)
    return result

مثال عملي آخر: حل مسألة Sudoku Solver

مسألة Sudoku Solver أو LeetCode 37 من المسائل القوية التي تختبر قدرتك على تطبيق Backtracking في بيئة تحتوي على قيود متعددة.

المطلوب هو ملء شبكة 9 × 9 بحيث:

• يظهر كل رقم من 1 إلى 9 مرة واحدة في كل صف.
• يظهر كل رقم من 1 إلى 9 مرة واحدة في كل عمود.
• يظهر كل رقم من 1 إلى 9 مرة واحدة في كل مربع فرعي 3 × 3.

تمثل الخلايا الفارغة بالرمز ..

كيف نطبّق Backtracking هنا؟

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

استخراج المرشحين في Sudoku

لاختيار قيمة خلية فارغة، نحتاج إلى معرفة الأرقام المستخدمة مسبقاً في:

• الصف الحالي.
• العمود الحالي.
• المربع الفرعي الحالي.

بعد ذلك تكون القيم المرشحة هي الأرقام غير المستخدمة.

هيكل مبسط للحل

DIGITS = set(str(num) for num in range(1, 10))
EMPTY = "."


def solveSudoku(board):
    search(board)


def get_candidates(board, row, col):
    used = set()
    used.update(get_row(board, row))
    used.update(get_col(board, col))
    used.update(get_box(board, row, col))
    used.discard(EMPTY)
    return DIGITS - used


def search(board):
    for row in range(9):
        for col in range(9):
            if board[row][col] == EMPTY:
                for candidate in get_candidates(board, row, col):
                    board[row][col] = candidate
                    if search(board):
                        return True
                    board[row][col] = EMPTY
                return False
    return True

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

متى يكون Backtracking هو الحل المناسب؟

هناك علامات واضحة تساعدك على اكتشاف هذا النوع من المسائل أثناء المقابلات:

• المطلوب إيجاد جميع الترتيبات أو التركيبات الممكنة.
• المسألة تسمح بإرجاع الحل بأي ترتيب.
• يوجد قيد يجب احترامه في كل خطوة.
• الحل يتطلب تجربة احتمالات متعددة ثم التراجع عن الخاطئ.

من الأمثلة الشهيرة على ذلك:

• Subsets
• Permutations
• N-Queens
• Sudoku Solver
• Combination Sum

نصائح عملية لاجتياز مسائل Backtracking في المقابلات

1. حدّد شكل الحالة أولاً

قبل كتابة أي كود، اسأل نفسك: ما أبسط طريقة لتمثيل الحل الجزئي؟ أحياناً يكون التمثيل الذكي للحالة هو نصف الحل.

2. لا تفحص أكثر مما تحتاج

بدلاً من التحقق من الحل الكامل كل مرة، حاول تصفية المرشحين مبكراً داخل get_candidates. هذا يقلل عدد المسارات المستكشفة ويجعل الحل أكثر كفاءة.

3. فرّق بين النسخ السطحي والعميق

إذا كنت تحفظ الحلول النهائية، فغالباً ستحتاج إلى نسخة عميقة deep copy أو على الأقل نسخة مستقلة من الحالة الحالية، لأن الحالة الأصلية ستتغير لاحقاً أثناء التراجع.

4. تعلّم متى تتوقف مبكراً

إذا كانت المسألة تتطلب حلاً واحداً فقط، فلا داعي لمتابعة البحث بعد العثور عليه. الإيقاف المبكر يوفّر وقت التنفيذ بشكل واضح.

5. درّب نفسك على القالب العام

كلما تدربت على مسائل أكثر باستخدام القالب نفسه، أصبحت أسرع في تمييز النمط أثناء المقابلة التقنية.

مقارنة بين مسألتي N-Queens وSudoku Solver

أفضل طريقة للتدرب على Backtracking

إذا أردت إتقان هذا النمط، فابدأ بمسائل متدرجة الصعوبة:

1. Subsets
2. Permutations
3. Combination Sum
4. N-Queens
5. Sudoku Solver

أثناء التدريب، حاول في كل مرة أن تجيب عن الأسئلة التالية:

• ما هي الحالة؟
• متى تكون الحالة حلاً نهائياً؟
• كيف أستخرج المرشحين؟
• كيف أضيف المرشح وأتراجع عنه؟

هذه الأسئلة ستجعل بناء الحل أكثر وضوحاً وأقل عشوائية.

الخلاصة التقنية

خوارزمية Backtracking ليست مجرد أسلوب brute force منظم، بل هي طريقة ذكية لاستكشاف فضاء الحلول مع استبعاد المسارات غير المفيدة مبكراً. قوتها الحقيقية تظهر عندما تحسن تمثيل الحالة، وتضبط شروط التحقق، وتقلّص عدد المرشحين قدر الإمكان. إذا أتقنت هذا القالب وطبّقته على مسائل مثل N-Queens وSudoku Solver وSubsets، فستكون أكثر جاهزية للتعامل مع أسئلة المقابلات البرمجية الصعبة بثقة وكفاءة.