إرضاء القيود ونشرها

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

أ. الصورة القياسية

مسألة إرضاء القيود هي مجموعة متغيّرات، ومجال من القيم المسموحة لكلٍّ منها، وقيود تقيّد أي التركيبات يجوز أن تجتمع. والإسناد متّسق إن لم يخرق شيئًا، وتامّ إن كان لكل متغيّر قيمة، وحلّ إن كان الأمرين معًا.

لوّن أقاليم أستراليا السبعة بثلاثة ألوان بحيث لا يتطابق إقليمان متجاوران. سبعة متغيّرات، والمجال $\{\text{red}, \text{green}, \text{blue}\}$، وتسعة قيود، قيدٌ لكل حدود مشتركة. وتسمانيا جزيرة فلا تظهر في أيٍّ منها.

وتستحثّ القيود الثنائية بيان القيود، وأنفع ما يُقرأ منه هو الدرجة، أي عدد القيود التي يشارك فيها المتغيّر:

$$\begin{array}{ll} \mathrm{SA} & 5 \\ \mathrm{NT},\ \mathrm{Q},\ \mathrm{NSW} & 3 \\ \mathrm{WA},\ \mathrm{V} & 2 \\ \mathrm{T} & 0 \end{array}$$

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

والصورة نفسها تبتلع مسائل لا صلة بينها. فالجدولة تصير متغيّرًا واحدًا لكل مهمّة قيمته زمن البدء، مع قيود أسبقية $T_1 + d_1 \le T_2$ وموعدٍ نهائي تقييدًا على كل مجال. والسودوكو يصير 81 متغيّرًا مع 27 قيدَ اختلافٍ تامّ. ولا تحتاج أيٌّ منها حلّالًا خاصًّا بها.

ب. الإبدالية، بلا ثمن

تعامل الشجرة الساذجة «أسند WA ثم NT» معاملةً مختلفة عن «أسند NT ثم WA». وعُدّ أوراقها: $n!$ ترتيبًا مضروبة في $d^n$ تركيبة،

$$7! \times 3^7 = 5{,}040 \times 2{,}187 = 11{,}022{,}480 .$$

لكن الإسناد إبدالي - فأي ترتيب يبلغ الإسناد الجزئي نفسه - ومن ثمّ فالترتيب لا يحمل معلومة، وللحلّال أن يثبّت متغيّرًا واحدًا في كل مستوى. وذلك يعطي $d^n = 2{,}187$ ورقة، أي أصغر بعامل 5,040، ودون أي تنازل. وهو ليس إرشادًا. بل هو حشو ما كان ينبغي للصياغة الساذجة أن تحمله.

ج. النشر، وما الذي يستطيع برهنته

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

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

فأنشئ إسنادين إذن. اجعل $\mathrm{WA} = \text{red}$ و$\mathrm{Q} = \text{green}$.

والتحقّق الأمامي، وهو أرخص استدلال مفيد، يحذف القيمة المُسنَدة من كل جار غير مُسنَد. فيترك $\mathrm{NT} = \{\text{blue}\}$ و$\mathrm{SA} = \{\text{blue}\}$ - مجالين أحاديّين، ولا شيء فارغ - ويمضي البحث.

أما اتّساق القوس فيخطو خطوة أبعد. فـNT صار أحاديًا؛ وSA مجاور لـNT؛ والقيمة الوحيدة الباقية لـSA هي الأزرق وكذلك قيمة NT، فيفقد الأزرق سنده ويفرغ $D_{\mathrm{SA}}$. فالفرع ميّت، وتقول AC-3 ذلك قبل أن يُجرى إسناد آخر.

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

والفرق هو المدى. فالتحقّق الأمامي ينشر إلى الخارج من المتغيّر المُسنَد لتوّه ثم يقف، فلا يقارن NT بـSA قطّ. أما AC-3 فتنشر حتى لا يتغيّر شيء.

والنشر سليم: فهو لا يحذف أبدًا قيمة يمكن أن تظهر في حلّ. لكنه ليس تامًّا. جرّب تلوين أستراليا بلونين، فتُبلّغ AC-3 أن المسألة متّسقة قوسيًا دون أن تحذف شيئًا، ومع ذلك لا حلول ألبتّة. إذ يفحص اتّساق القوس متغيّرين في كل مرة، ولا زوج متناقض؛ والمتناقض هو دورة من ثلاثة أقاليم تحتاج ثلاثة ألوان. ورؤية ذلك تقتضي اتّساق المسار، والاتّساق-$k$ التامّ يكلّف زمنًا وفضاءً أسّيَّين في $k$. واتّساق القوس هو النقطة التي يظلّ عندها الاستدلال رخيصًا بما يكفي لتشغيله عند كل عقدة.

د. البحث، والإرشاد الذي لا يفعل شيئًا

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

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

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

والآن القياس. خذ مسألة $N$ ملكة على هيئة مسألة إرضاء قيود، متغيّرًا واحدًا لكل عمود قيمته الصفّ، وعُدّ الإسنادات المُنجَزة (فالقيمة التي تتعارض مع ملكة موضوعة تُرفض دون أن تُعدّ؛ ولو عُدّت هي أيضًا لجرّب التراجع المجرّد 876 قيمة عند 8 ملكات):

$$\begin{array}{r|rrrr} n & \text{plain} & \text{MRV} & \text{FC} & \text{MRV + FC} \\ \hline 8 & 113 & 113 & 88 & 75 \\ 16 & 10{,}052 & 10{,}052 & 7{,}560 & 44 \\ 24 & 411{,}608 & 411{,}608 & 286{,}963 & 43 \end{array}$$

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

والتحقّق الأمامي وحده يوفّر نحو الربع: 22٪ عند 8 ملكات، و30٪ عند 24. ومعًا ينزلان بـ411,608 إسنادًا إلى 43.

جدول كهذا يستحقّ التحقّق لا التصديق، ولذلك يُشغّل الشكل أدناه البحث بدل نقله. انتقل إلى MRV فلن يتحرّك العدّ؛ وبدّل حجم الرقعة فلن يتحرّك كذلك. ثم انتقل إلى الاقتران واسحب حتى 16، وانظر 10,052 إسنادًا تصير 44. ويقف المزلاج هناك لأن السطر الأخير، 24 وزيرة، يطلب 411,608 إسنادًا، وذاك حسابٌ حقيقي لا مجرّد إعادة رسم.

أين يضعك هذا

وصف المسألة وصفًا سليمًا ليس عملًا ورقيًا؛ بل هو ما يتيح للحلّال أن يستدلّ بدل أن يخمّن. فالإبدالية تزيل عامل $n!$ قبل أن يجري أي شيء. والنشر يحذف ما لا يمكن أن ينجح ويقتل أحيانًا فرعًا قتلًا صريحًا، مع أمانته في أن اجتيازه لا يبرهن شيئًا. والإرشادات الترتيبية الشهيرة ليست حيلًا قائمة بذاتها: فأقلّ القيم المتبقّية مستهلِك للاستدلال، لا يساوي شيئًا بالضبط ما لم يكن شيء آخر يقلّص المجالات ليقرأها. ومسار التدريب إرضاء القيود يعالج كلًّا من هذه يدويًا وبالشيفرة.