اتّساق القوس

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

والقوس من X إلى Y متّسق حين تكون لكلّ قيمة باقية في X قيمةٌ في Y تُحقّق القيد بينهما. وجعله متّسقًا هو حذف قيم X التي لا سند لها. والدقّة أنّ ذلك قد يكسر أقواسًا كانت متّسقة، لأنّ قيمةً في متغيّر ثالث Z ربّما كانت تعتمد على قيمة من X زالت الآن. والخوارزميّة القياسيّة AC-3 تعالج ذلك بطابور: فكلّما تقلّص مجال عادت إلى الطابور كلُّ الأقواس المشيرة إلى ذلك المتغيّر.

والعائد نتيجةٌ لا يبلغها فحص محلّيّ. فإن فرغ مجال فلا حلّ تحت هذه النقطة من البحث، ويمكن هجر الفرع فورًا. ولهذا يُتشابك النشر مع البحث بدل تشغيله مرّة في البداية، ولهذا يغلب الجمعُ بينهما كلًّا منهما وحده.

وما لا تستطيعه هو البتّ في المسألة. فاتّساق القوس لا ينظر إلّا في الأزواج، فيَسلَم منه تناقضٌ لا يظهر إلّا من ثلاثة متغيّرات فأكثر معًا. وقد تظلّ المسألة المتّسقة قوسيًّا بلا حلّ، ومفاهيم أقوى وأغلى - اتّساق المسار، واتّساق k - موجودة بالضبط لترى أبعد بثمن أعلى.

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

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

والقوّة الغاشمة على الإسنادات 3^7 = 2,187 تؤكّد ذلك: فلهذا الإسناد الجزئيّ صفرٌ من التتمّات بالضبط، من بين الثمانية عشر التي للمسألة. أمّا الفحص الأماميّ، الذي لا يشذّب إلّا جيران المتغيّر عند إسناده، فيترك المجالين عند قيمة واحدة، ولا يرى خطأً، ويواصل البحث.