مسألة إرضاء القيود

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

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

وفكرتان تجعلان الصورة قابلة للمعالجة عمليًا. أولاهما الإبدالية: فبلوغُ إسناد جزئي بترتيب من الإسنادات هو نفسه بلوغه بأي ترتيب آخر، فالترتيب لا يحمل معلومة وللحلّال أن يثبّت متغيّرًا واحدًا في كل مستوى من شجرته. ومع سبعة متغيّرات وثلاث قيم يحوّل ذلك ‎7! × 3⁷‎ ورقة إلى ‎3⁷‎، أي بعامل 5,040 بلا ثمن. وثانيتهما النشر: فقبل البحث وأثناءه يمكن حذف القيم التي لا شريك ممكن لها حذفًا صريحًا. واتّساق القوس، الذي تفرضه خوارزمية AC-3، يجعل كل زوج مرتّب من المتغيّرات متّسقًا في زمن كثير الحدود في حجم المسألة.

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

يستعمل تلوين أستراليا سبعة متغيّرات بالمجال {red, green, blue} وتسعة قيود عدم مساواة، قيدًا لكل حدود مشتركة. وتشغيل AC-3 على المسألة التي لم تُمسّ لا يجري أي مراجعة: إذ ما زالت لكل إقليم ثلاثة ألوان، فلا يمكن حذف أي قيمة ولا شيء لدى النشر ليعمل به حتى يخلق إسنادٌ لاتناظرًا.

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

وقياسُ مسألة N ملكة يبيّن لماذا تُعرض الإرشادات عادةً عرضًا مضلّلًا. فعند n = 24 يجرّب التراجع المجرّد 411,608 إسنادًا؛ وإضافة إرشاد أقلّ القيم المتبقّية وحده تجرّب العدد نفسه بالضبط، لأن لا شيء يحذف القيم وكل المجالات متعادلة. والتحقّق الأمامي وحده ينزل به إلى 286,963، والاثنان معًا إلى 43.