سازگاریِ کمانی بررسی می‌کند آیا هر مقدارِ باقی‌ماندهٔ یک متغیر، در دامنهٔ متغیرِ همسایه دست‌کم یک مقدارِ پشتیبان دارد که قیدِ دوتایی را نقض نکند. AC-3 با صفِ کمان‌ها، مقدارهای بدون پشتیبان را حذف می‌کند. اما خالی‌نشدنِ دامنه‌ها لزوماً یعنی جوابِ مشترک وجود دارد نیست. در این تمرین، هم انتشارِ حذف را می‌بینیم و هم یک مسئلهٔ سازگارِ کمانی ولی بی‌جواب را واقعاً می‌شماریم.
قیدِ ساده: دو همسایه هم‌رنگ نباشند
سه متغیرِ A، B و C داریم. A فقط می‌تواند قرمز باشد؛ B و C در ابتدا قرمز یا آبی‌اند. قیدها می‌گویند A≠B و B≠C. هر یالِ بی‌جهتِ قید را با دو کمانِ جهت‌دار در صف می‌گذاریم؛ «جهت» اینجا مشخص می‌کند دامنهٔ کدام سر را با دامنهٔ کدام همسایه بازبینی می‌کنیم، نه اینکه قیدِ نابرابری یک‌طرفه باشد.
برای کمان B→A، مقدارِ قرمزِ B هیچ پشتیبانی در A ندارد، چون A فقط قرمز است و قیدِ نابرابری را نقض می‌کند. پس قرمز از B حذف و دامنهٔ B فقط آبی می‌شود. حالا تغییرِ B می‌تواند پشتیبان‌های C را تغییر دهد؛ باید کمان C→B دوباره بررسی شود. در آن بررسی، آبیِ C حذف و C فقط قرمز می‌شود.
| متغیر | دامنهٔ آغاز | دامنهٔ پایان |
|---|---|---|
| A | قرمز | قرمز |
| B | قرمز، آبی | آبی |
| C | قرمز، آبی | قرمز |
چرا یک بار عبور از کمان‌ها کافی نبود؟
فایل عمداً صف را به ترتیبِ C→B، B→C، B→A و A→B شروع می‌کند. وقتی C→B اولین بار پردازش می‌شود، B هنوز هر دو رنگ را دارد و چیزی از C حذف نمی‌شود. پس از حذفِ قرمز از B، همین کمان دوباره به صف می‌رود و این بار آبیِ C را حذف می‌کند. دفترِ اجرا، کمانِ پردازش‌شده، مقدارهای حذف‌شده، دامنهٔ تازه، کمان‌های بازافزوده و صفِ باقی‌مانده را ثبت می‌کند.
کد برای قیدِ متقارنِ نابرابری، هنگام کوچک‌شدن دامنهٔ یک سر، همسایه‌های دیگر را برای بازبینی به سمت آن سر برمی‌گرداند و کمانِ ازقبلحاضر در صف را تکراری اضافه نمی‌کند. این به معنای یک‌بار پردازش‌شدنِ هر کمان در کل اجرا نیست؛ همان دادهٔ عوض‌شده علتِ بازبینیِ دوباره است.
مقدارِ حذف‌شده چرا قابل اتکا نبود؟
اگر برای یک مقدارِ X هیچ مقدارِ مجاز در دامنهٔ همسایهٔ Y باقی نمانده باشد، هیچ جوابِ کاملِ سازگار با همان قید نمی‌تواند آن مقدارِ X را داشته باشد. پس حذف، جوابِ معتبر را از بین نمی‌برد. برای زنجیرهٔ آموزشی، تابع مستقل همهٔ ترکیب‌های دامنهٔ اولیه را می‌سنجد؛ همان یک جوابِ A=قرمز، B=آبی، C=قرمز قبل و بعد از AC-3 باقی است. این کنترل از صفِ AC-3 استفاده نمی‌کند.
در یک نمونهٔ جدا که A و B هر دو فقط قرمز دارند و باید متفاوت باشند، بازبینی واقعاً یک دامنه را خالی می‌کند. این وضعیت نشانهٔ ناسازگاری همین مسئله است، نه «دادهٔ گم‌شده را رنگ تصادفی پر کنیم». فایل در همین نقطه نتیجهٔ شکستِ دامنه را ثبت می‌کند.
سه گره، دو رنگ و هیچ جوابِ کامل
حالا هر سه متغیر هر دو رنگ را دارند و علاوه بر A≠B و B≠C، قید A≠C هم اضافه می‌شود؛ یک مثلث. برای هر رنگ در هر سر، همسایه رنگِ مخالف را دارد. بنابراین AC-3 چیزی حذف نمی‌کند، همهٔ دامنه‌ها غیرخالی و همهٔ کمان‌ها سازگار می‌مانند.
بااین‌حال نمی‌توان سه رأسِ مثلث را فقط با دو رنگ طوری رنگ کرد که هر دو همسایه متفاوت باشند. تابع مستقل هر هشت انتساب را واقعاً بررسی می‌کند و هیچ جوابِ کامل پیدا نمی‌کند. پس «پشتیبان جداگانه برای هر همسایه» با «یک انتسابِ مشترکِ سازگار با همهٔ قیدها» فرق دارد. ممکن است پس از AC-3 هنوز به جست‌وجو و عقب‌گرد نیاز باشد.
چه چیزی در این کد اجرا نشده است؟
فایل فقط دامنه‌های متناهی و قیدِ دوتاییِ نابرابری را برای مثال‌های کوچک می‌گیرد؛ حل‌کنندهٔ عمومیِ همهٔ CSPها، قیدهای چندمتغیره یا برنامه‌ریزِ واقعی نیست. حذفِ مبتنی بر قید، به معنی یادگیری مدل یا سنجش رضایت مشتری هم نیست؛ CSP در این بحث «مسئلهٔ ارضای محدودیت» است. دادهٔ نامعتبرِ دارای سرِ ناشناخته یا قیدِ یک گره به خودش، قرارداد این نمونه را ندارد.
در ترتیب توپولوژیک مسئله، رعایتِ وابستگیِ کارها در یک گراف است؛ اینجا انتخابِ مقدار از دامنه و سازگاریِ قید را بررسی کردیم. برای کاربرد در پاسخ‌گویی و پیگیری، پیش از انتخاب فناوری قیدهای معتبر، مسئول تصمیم و حالتِ بی‌جواب را در راهکارهای اپرا مشخص کنید؛ این تمرین قابلیت CSP در محصول را وعده نمی‌دهد.
فایل تمرین و منبع
کد کامل Python؛ محاسبه و کنترل‌های مستقل · ورودیِ ساخته‌شده، مراحل و خروجیِ اجرای واقعی
منابع در 2026-11-04 خوانده شدند؛ این تاریخ، تاریخ انتشار منبع نیست. مثال‌ها و فایل‌های این راهنما آموزشی و ساختهٔ تحریریه‌اند.