58. خوارزميات التراجع (Backtracking): مفهوم مشكلة N-Queens

التراجع هو تقنية خوارزمية تُستخدم لحل مشاكل إرضاء القيود (Constraint Satisfaction Problems - CSPs). تبحث بشكل منهجي عن حل من خلال محاولة تمديد حل جزئي بشكل تدريجي.

الآلية الأساسية

البناء (Build): البدء بحل فارغ.
الاختبار (Test): إذا كان الحل الجزئي الحالي غير صالح أو ينتهك القيود، التوقف (التقليم).
العودية (Recurse): إذا كان الحل الجزئي صالحاً، حاول تمديده أكثر.
التراجع (Backtrack): إذا لم ينجح أي تمديد، التراجع عن الاختيار الأخير وتجربة البديل التالي.

مثال: مشكلة N-Queens

الهدف: وضع N من ملكات الشطرنج على رقعة شطرنج N x N بحيث لا تهاجم ملكتان بعضهما البعض.

النهج: وضع ملكة واحدة في كل صف.
العملية: وضع ملكة في العمود الأول من الصف الأول. التحقق مما إذا كانت آمنة. إذا كانت آمنة، الانتقال إلى الصف التالي. إذا كانت غير آمنة، أو إذا فشلت جميع الخيارات في الصف التالي، التراجع وتحريك الملكة في الصف الحالي إلى العمود التالي، والمحاولة مرة أخرى.