ความสอดคล้องของโหนดกำหนดให้ข้อจำกัดเอกภาคทุกข้อของตัวแปรต้องเป็นไปตามค่าทั้งหมดในโดเมนของตัวแปรนั้น และในทางกลับกัน เงื่อนไขนี้สามารถบังคับใช้ได้อย่างง่ายดายโดยการลดโดเมนของแต่ละตัวแปรให้เหลือเฉพาะค่าที่สอดคล้องกับข้อจำกัดเอกภาคทั้งหมดของตัวแปรนั้น ผลที่ได้คือ สามารถละเลยข้อจำกัดเอกภาคและถือว่าข้อจำกัดเหล่านั้นรวมอยู่ในโดเมนแล้ว

ตัวอย่างเช่น เมื่อกำหนดตัวแปรหนึ่งตัว${\displaystyle V}$ด้วยโดเมนของ${\displaystyle \left\{1,2,3,4\right\}}$และข้อจำกัด${\displaystyle V\leq 3}$ความสอดคล้องของโหนดจะจำกัดขอบเขตไว้ที่${\displaystyle \left\{1,2,3\right\}}$และสามารถละทิ้งข้อจำกัดนั้นได้ ขั้นตอนการประมวลผลล่วงหน้านี้ช่วยลดความซับซ้อนในขั้นตอนต่อๆ ไป

ตัวแปรหนึ่งในปัญหาการแก้ข้อจำกัดจะสอดคล้องกับตัวแปรอีกตัวหนึ่งก็ต่อเมื่อค่าที่ยอมรับได้แต่ละค่าของตัวแปรนั้นสอดคล้องกับค่าที่ยอมรับได้บางค่าของตัวแปรที่สอง กล่าวอย่างเป็นทางการคือ ตัวแปรหนึ่งสอดคล้องกับค่าที่ยอมรับได้ของตัวแปรที่สอง${\displaystyle x_{i}}$ส่วนโค้งนั้นสอดคล้องกับตัวแปรอื่นหรือไม่${\displaystyle x_{j}}$ถ้าสำหรับทุกค่า${\displaystyle a}$ในขอบเขตของ ${\displaystyle x_{i}}$มีค่าอยู่${\displaystyle b}$ในขอบเขตของ${\displaystyle x_{j}}$โดยที่${\displaystyle (a,b)}$ตรงตามข้อจำกัดแบบไบนารีระหว่าง${\displaystyle x_{i}}$และ${\displaystyle x_{j}}$ปัญหาจะเรียกว่ามีความสอดคล้องเชิงเส้นโค้ง (arc consistent) ถ้าตัวแปรทุกตัวมีความสอดคล้องเชิงเส้นโค้งกับตัวแปรอื่นๆ ทุกตัว

ตัวอย่างเช่น พิจารณาข้อจำกัดนี้${\displaystyle x<y}$โดยที่ตัวแปรมีค่าอยู่ในช่วง 1 ถึง 3 เนื่องจาก${\displaystyle x}$ไม่สามารถเป็น 3 ได้ เพราะไม่มีเส้นโค้งจาก 3 ไปยังค่าใดๆ ใน 3${\displaystyle y}$ดังนั้นจึงปลอดภัยที่จะลบค่า 3 ออกจาก${\displaystyle x}$โดเมนของ ส่งผลให้${\displaystyle \{1,2\}}$. เช่นเดียวกัน,${\displaystyle y}$ไม่สามารถเป็น 1 ได้ ดังนั้นจึงไม่มีส่วนโค้ง ดังนั้นจึงสามารถลบ 1 ออกได้${\displaystyle y}$โดเมนของ ส่งผลให้${\displaystyle \{2,3\}}$.

ความสอดคล้องของส่วนโค้งยังสามารถกำหนดได้โดยสัมพันธ์กับข้อจำกัดแบบไบนารีที่เฉพาะเจาะจง: ข้อจำกัดแบบไบนารีจะมีความสอดคล้องของส่วนโค้งก็ต่อเมื่อทุกค่าของตัวแปรหนึ่งมีค่าของตัวแปรที่สองที่ทำให้เป็นไปตามข้อจำกัดนั้น คำจำกัดความของความสอดคล้องของส่วนโค้งนี้คล้ายกับข้างต้น แต่กำหนดขึ้นโดยเฉพาะสำหรับข้อจำกัดหนึ่งๆ ความแตกต่างนี้มีความสำคัญอย่างยิ่งสำหรับปัญหาที่ไม่ได้รับการทำให้เป็นมาตรฐาน ซึ่งคำจำกัดความข้างต้นจะพิจารณาข้อจำกัดทั้งหมดระหว่างตัวแปรสองตัว ในขณะที่คำจำกัดความนี้พิจารณาเฉพาะข้อจำกัดที่เฉพาะเจาะจงเท่านั้น

หากตัวแปรหนึ่งไม่สอดคล้องกับอีกตัวแปรหนึ่งในแง่ของส่วนโค้ง สามารถทำให้สอดคล้องกันได้โดยการลบค่าบางส่วนออกจากโดเมนของตัวแปรนั้น นี่คือรูปแบบของการแพร่กระจายข้อจำกัดที่บังคับให้เกิดความสอดคล้องกันของส่วนโค้ง: มันจะลบค่าทุกค่าที่ไม่สอดคล้องกับค่าของตัวแปรอื่นออกจากโดเมนของตัวแปร การแปลงนี้จะรักษาคำตอบของปัญหาไว้ เนื่องจากค่าที่ถูกลบออกไปนั้นไม่มีอยู่ในคำตอบอยู่แล้ว

การแพร่กระจายข้อจำกัดสามารถทำให้ปัญหาทั้งหมดมีความสอดคล้องกันได้โดยการทำซ้ำการลบนี้สำหรับตัวแปรทุกคู่ กระบวนการนี้อาจต้องพิจารณาตัวแปรคู่ใดคู่หนึ่งมากกว่าหนึ่งครั้ง อันที่จริง การลบค่าออกจากโดเมนของตัวแปรอาจทำให้ตัวแปรอื่นๆ ไม่สอดคล้องกับตัวแปรนั้นอีกต่อไป ตัวอย่างเช่น ถ้า${\displaystyle x_{3}}$ส่วนโค้งนั้นสอดคล้องกับ${\displaystyle x_{2}}$แต่ขั้นตอนวิธีนี้จะลดขอบเขตของ${\displaystyle x_{2}}$ความสม่ำเสมอของส่วนโค้ง${\displaystyle x_{3}}$กับ${\displaystyle x_{2}}$กฎหมายดังกล่าวใช้การไม่ได้อีกต่อไปแล้ว และต้องบังคับใช้ใหม่อีกครั้ง

อัลกอริทึมแบบง่ายๆ จะวนซ้ำไปตามคู่ตัวแปร โดยบังคับใช้ความสอดคล้องของส่วนโค้ง และทำซ้ำวงจรไปเรื่อยๆ จนกว่าจะไม่มีโดเมนใดเปลี่ยนแปลงตลอดทั้งวงจรอัลกอริทึม AC-3ปรับปรุงจากอัลกอริทึมนี้โดยการละเว้นข้อจำกัดที่ไม่ได้ถูกแก้ไขนับตั้งแต่ได้รับการวิเคราะห์ครั้งล่าสุด โดยเฉพาะอย่างยิ่ง มันทำงานกับชุดข้อจำกัดที่ประกอบด้วยข้อจำกัดทั้งหมดตั้งแต่เริ่มต้น ในแต่ละขั้นตอน มันจะเลือกข้อจำกัดหนึ่งข้อและบังคับใช้ความสอดคล้องของส่วนโค้ง หากการดำเนินการนี้อาจทำให้เกิดการละเมิดความสอดคล้องของส่วนโค้งกับข้อจำกัดอื่น มันจะนำข้อจำกัดนั้นกลับไปอยู่ในชุดข้อจำกัดที่จะวิเคราะห์ ด้วยวิธีนี้ เมื่อบังคับใช้ความสอดคล้องของส่วนโค้งกับข้อจำกัดแล้ว ข้อจำกัดนั้นจะไม่ถูกนำมาพิจารณาอีกเว้นแต่โดเมนของตัวแปรใดตัวหนึ่งจะเปลี่ยนแปลงไป

ความสอดคล้องของเส้นทาง (Path consistency) เป็นคุณสมบัติที่คล้ายกับความสอดคล้องของส่วนโค้ง (Arc consistency) แต่พิจารณาตัวแปรเป็นคู่ๆ แทนที่จะเป็นตัวแปรเดียว ตัวแปรคู่หนึ่งจะมีความสอดคล้องของเส้นทางกับตัวแปรที่สามได้ก็ต่อเมื่อการประเมินค่าที่สอดคล้องกันของคู่ตัวแปรนั้นสามารถขยายไปยังตัวแปรอื่นได้ในลักษณะที่ตรงตาม ข้อจำกัด แบบไบนารี ทั้งหมด กล่าวอย่างเป็นทางการคือ${\displaystyle x_{i}}$และ${\displaystyle x_{j}}$เส้นทางนั้นสอดคล้องกับ${\displaystyle x_{k}}$ถ้าสำหรับทุกคู่ค่า${\displaystyle (a,b)}$ที่ตรงตามข้อจำกัดแบบไบนารีระหว่าง${\displaystyle x_{i}}$และ${\displaystyle x_{j}}$มีค่าอยู่ค่าหนึ่ง${\displaystyle c}$ในขอบเขตของ${\displaystyle x_{k}}$โดยที่${\displaystyle (a,c)}$และ${\displaystyle (b,c)}$ปฏิบัติตามข้อจำกัดระหว่าง${\displaystyle x_{i}}$และ${\displaystyle x_{k}}$และระหว่าง${\displaystyle x_{j}}$และ${\displaystyle x_{k}}$ตามลำดับ

รูปแบบการแพร่กระจายข้อจำกัดที่บังคับใช้ความสอดคล้องของเส้นทางนั้นทำงานโดยการลบการกำหนดค่าที่ตรงตามเงื่อนไขบางอย่างออกจากข้อจำกัด ที่จริงแล้ว ความสอดคล้องของเส้นทางสามารถบังคับใช้ได้โดยการลบการประเมินทั้งหมดที่ไม่สามารถขยายไปยังตัวแปรอื่นได้ ออกจากข้อจำกัดแบบไบนารี ส่วนความสอดคล้องของส่วนโค้งนั้น การลบนี้อาจต้องพิจารณาข้อจำกัดแบบไบนารีมากกว่าหนึ่งครั้ง สำหรับความสอดคล้องของส่วนโค้งนั้น ปัญหาที่ได้จะมีคำตอบเหมือนกับปัญหาเดิม เนื่องจากค่าที่ถูกลบออกไปนั้นไม่มีอยู่ในคำตอบใดๆ

รูปแบบการแพร่กระจายข้อจำกัดที่บังคับใช้ความสอดคล้องของเส้นทางอาจนำมาซึ่งข้อจำกัดใหม่ๆ เมื่อตัวแปรสองตัวไม่มีความสัมพันธ์กันโดยข้อจำกัดแบบไบนารี ตัวแปรทั้งสองจะมีความสัมพันธ์กันโดยปริยายโดยข้อจำกัดที่อนุญาตให้มีค่าใดๆ ก็ได้ อย่างไรก็ตาม ค่าบางคู่ก็อาจถูกกำจัดออกไปโดยการแพร่กระจายข้อจำกัด ข้อจำกัดที่ได้จึงไม่เป็นไปตามเงื่อนไขของค่าทุกคู่ ดังนั้นจึงไม่ใช่ข้อจำกัดเสมือนที่ไม่มีนัยสำคัญอีกต่อไป

ชื่อ "ความสอดคล้องของเส้นทาง" มาจากนิยามดั้งเดิม ซึ่งเกี่ยวข้องกับตัวแปรสองตัวและเส้นทางระหว่างตัวแปรทั้งสองนั้น แทนที่จะเป็นตัวแปรสองตัวและตัวแปรเดี่ยว แม้ว่านิยามทั้งสองจะแตกต่างกันสำหรับตัวแปรสองตัว แต่ก็มีความหมายเทียบเท่ากันเมื่อกล่าวถึงปัญหาทั้งหมด

ความสอดคล้องของส่วนโค้งและเส้นทางสามารถขยายไปสู่ข้อจำกัดที่ไม่ใช่ไบนารีได้โดยใช้ทูเปิลของตัวแปรแทนที่จะใช้ตัวแปรเดียวหรือคู่หนึ่ง ทูเปิลของ${\displaystyle i-1}$ตัวแปรคือ${\displaystyle i}$-สอดคล้องกับตัวแปรอื่น หากการประเมินที่สอดคล้องกันทุกครั้งของ${\displaystyle i-1}$ตัวแปรสามารถขยายได้ด้วยค่าของตัวแปรอื่นในขณะที่ยังคงรักษาความสอดคล้องไว้ นิยามนี้สามารถขยายไปสู่ปัญหาโดยรวมได้อย่างชัดเจน (แข็งแกร่ง)${\displaystyle i}$-ความสม่ำเสมอคือ ${\displaystyle j}$-ความสม่ำเสมอสำหรับทุกคน${\displaystyle j\leq i}$.

กรณีเฉพาะของความสอดคล้องแบบ 2 นั้นตรงกับความสอดคล้องของส่วนโค้ง (ในบทความนี้ถือว่าปัญหาทั้งหมดมีความสอดคล้องของโหนด) ในทางกลับกัน ความสอดคล้องแบบ 3 จะตรงกับความสอดคล้องของเส้นทางก็ต่อเมื่อข้อจำกัดทั้งหมดเป็นแบบไบนารีเท่านั้น เพราะความสอดคล้องของเส้นทางไม่เกี่ยวข้องกับข้อจำกัดแบบไตรนารี ในขณะที่ความสอดคล้องแบบ 3 เกี่ยวข้อง

อีกวิธีหนึ่งในการทำให้ความสอดคล้องของส่วนโค้งเป็นแบบทั่วไปคือความสอดคล้องของส่วนโค้งขั้นสูงหรือความสอดคล้องของส่วนโค้งแบบทั่วไปซึ่งต้องการความสามารถในการขยายของตัวแปรเดียวเพื่อให้เป็นไปตามข้อจำกัด กล่าวคือ ตัวแปรจะมีความสอดคล้องของส่วนโค้งขั้นสูงกับข้อจำกัดก็ต่อเมื่อทุกค่าของตัวแปรสามารถขยายไปยังตัวแปรอื่นๆ ของข้อจำกัดได้ในลักษณะที่ทำให้ข้อจำกัดนั้นเป็นไปตามที่กำหนด

การแพร่กระจายข้อจำกัด (การบังคับใช้ความสอดคล้องในระดับท้องถิ่น) อาจทำให้เกิดโดเมนว่างเปล่าหรือ ข้อจำกัด ที่ไม่สามารถหาคำตอบได้ ในกรณีนี้ ปัญหาจะไม่มีทางออก แต่ในทางกลับกันนั้นไม่เป็นจริงเสมอไป กล่าวคือ ตัวอย่างที่ไม่สอดคล้องกันอาจมีความสอดคล้องกันในส่วนของส่วนโค้งหรือเส้นทาง ในขณะที่ไม่มีโดเมนว่างเปล่าหรือข้อจำกัดที่ไม่สามารถหาคำตอบได้

อันที่จริง ความสอดคล้องในระดับท้องถิ่นนั้นเป็นเพียงความสัมพันธ์กับความสอดคล้องของกลุ่มตัวแปรเท่านั้น ตัวอย่างเช่น ความสอดคล้องของส่วนโค้งรับประกันว่าการประเมินค่าตัวแปรที่สอดคล้องกันทุกครั้งสามารถขยายไปสู่ตัวแปรอื่นได้อย่างสอดคล้อง อย่างไรก็ตาม เมื่อค่าเดียวของตัวแปรถูกขยายไปสู่ตัวแปรอื่นอีกสองตัว ก็ไม่มีการรับประกันว่าค่าทั้งสองนั้นจะสอดคล้องกัน ตัวอย่างเช่น${\displaystyle x_{1}=1}$อาจสอดคล้องกับ${\displaystyle x_{2}=1}$และด้วย${\displaystyle x_{3}=1}$แต่การประเมินทั้งสองนี้อาจไม่สอดคล้องกัน

อย่างไรก็ตาม การแพร่กระจายข้อจำกัดสามารถใช้เพื่อพิสูจน์ความสามารถในการทำให้เป็นจริงได้ในบางกรณี ชุดของข้อจำกัดแบบไบนารีที่สอดคล้องกันและไม่มีโดเมนว่าง จะไม่สอดคล้องกันได้ก็ต่อเมื่อเครือข่ายของข้อจำกัดมีวงจรเท่านั้น อันที่จริง หากข้อจำกัดเป็นแบบไบนารีและสร้างกราฟที่ไม่มีวงจร ค่าต่างๆ สามารถแพร่กระจายข้ามข้อจำกัดได้เสมอ: สำหรับทุกค่าของตัวแปร ตัวแปรทั้งหมดในข้อจำกัดที่มีตัวแปรนั้นจะมีค่าที่สอดคล้องกับข้อจำกัดนั้น ผลลัพธ์ที่ได้คือ สามารถหาคำตอบได้โดยการเลือกตัวแปรที่ยังไม่ได้กำหนดค่าซ้ำๆ และแพร่กระจายข้ามข้อจำกัดแบบเรียกซ้ำ อัลกอริทึมนี้จะไม่พยายามกำหนดค่าให้กับตัวแปรที่กำหนดค่าไว้แล้ว เนื่องจากนั่นจะหมายถึงการมีอยู่ของวงจรในเครือข่ายของข้อจำกัด

เงื่อนไขที่คล้ายกันนี้ใช้ได้กับความสอดคล้องของเส้นทางด้วย กรณีพิเศษที่สามารถสร้างความพึงพอใจได้โดยการบังคับใช้ความสอดคล้องของส่วนโค้งและความสอดคล้องของเส้นทางมีดังต่อไปนี้

1. การบังคับใช้ความสอดคล้องของส่วนโค้งทำให้ปัญหาที่ประกอบด้วยข้อจำกัดแบบไบนารีที่ไม่มีวงจร ( ต้นไม้ของข้อจำกัดแบบไบนารี) สามารถแก้ไขได้
2. การบังคับใช้ความสอดคล้องของเส้นทางจะสร้างความพึงพอใจให้กับข้อจำกัดแบบไบนารี (อาจมีวงจร) ที่มีโดเมนแบบไบนารี
3. บังคับใช้อย่างเข้มงวด${\displaystyle n}$ความสอดคล้องสร้างความพึงพอใจให้กับปัญหาที่มีอยู่${\displaystyle n}$ตัวแปร

คำจำกัดความหรือผลลัพธ์บางอย่างเกี่ยวกับความสอดคล้องเชิงสัมพัทธ์นั้นใช้ได้เฉพาะในกรณีพิเศษเท่านั้น

เมื่อโดเมนประกอบด้วยจำนวนเต็มความสอดคล้องแบบขอบเขตสามารถกำหนดได้ ความสอดคล้องในรูปแบบนี้ขึ้นอยู่กับความสอดคล้องของค่าสุดขั้วของโดเมน กล่าวคือ ค่าต่ำสุดและค่าสูงสุดที่ตัวแปรสามารถรับได้

เมื่อข้อจำกัดเป็นแบบพีชคณิตหรือแบบบูลีนความสอดคล้องของส่วนโค้งจะเทียบเท่ากับการเพิ่มข้อจำกัดใหม่หรือการแก้ไขข้อจำกัดเดิมในเชิงไวยากรณ์ ซึ่งสามารถทำได้โดยการประกอบข้อจำกัดเข้าด้วยกันอย่างเหมาะสม

ข้อจำกัดบางประเภทถูกนำมาใช้กันอย่างแพร่หลาย ตัวอย่างเช่น ข้อจำกัดที่ว่าตัวแปรบางตัวต้องแตกต่างกันทั้งหมด มักถูกนำมาใช้ มีอัลกอริธึมเฉพาะทางที่มีประสิทธิภาพสำหรับการบังคับใช้ความสอดคล้องของส่วนโค้งภายใต้ข้อจำกัดดังกล่าวอยู่แล้ว

ข้อจำกัดที่บังคับให้ตัวแปรจำนวนหนึ่งแตกต่างกัน มักจะเขียนในรูปแบบนี้${\displaystyle \mathop {\rm {alldifferent}} (x_{1},\ldots ,x_{n})}$หรือalldifferent([X1,...,Xn]). ข้อจำกัดนี้เทียบเท่ากับการที่ตัวแปรต่างกันทุกคู่ไม่เท่ากัน นั่นคือ${\displaystyle x_{i}\not =x_{j}}$สำหรับทุกๆ${\displaystyle i\not =j}$เมื่อขอบเขตของตัวแปรลดลงเหลือเพียงค่าเดียว ค่านี้สามารถถูกลบออกจากขอบเขตอื่นๆ ทั้งหมดได้โดยการแพร่กระจายข้อจำกัดเมื่อบังคับใช้ความสอดคล้องของส่วนโค้ง การใช้ข้อจำกัดเฉพาะนี้ช่วยให้สามารถใช้ประโยชน์จากคุณสมบัติที่ไม่มีในความไม่เท่าเทียม กันแบบไบนารีแต่ละแบบ ได้

คุณสมบัติข้อแรกคือ จำนวนองค์ประกอบทั้งหมดในโดเมนของตัวแปรทั้งหมดต้องมีอย่างน้อยเท่ากับจำนวนตัวแปร กล่าวคือ หลังจากบังคับใช้ความสอดคล้องของส่วนโค้งแล้ว จำนวนตัวแปรที่ไม่ได้กำหนดต้องไม่เกินจำนวนค่าในผลรวมของโดเมน มิฉะนั้น ข้อจำกัดจะไม่สามารถเป็นไปตามเงื่อนไขได้ เงื่อนไขนี้สามารถตรวจสอบได้ง่ายบนข้อจำกัดในรูปalldifferentแบบ แต่ไม่สอดคล้องกับความสอดคล้องของส่วนโค้งของเครือข่ายความไม่เท่าเทียมกัน คุณสมบัติข้อที่สองของalldifferentข้อจำกัดเดียวคือ สามารถตรวจสอบความสอดคล้องของส่วนโค้งไฮเปอร์ได้อย่างมีประสิทธิภาพโดยใช้ อัลกอริทึม การจับคู่แบบทวิภาค โดยเฉพาะอย่างยิ่ง กราฟจะถูกสร้างขึ้นโดยมีตัวแปรและค่าเป็นสองชุดของโหนด และ อัลกอริทึมการจับคู่ กราฟแบบ ทวิภาคเฉพาะ จะถูกเรียกใช้บนกราฟนั้นเพื่อตรวจสอบการมีอยู่ของการจับคู่ดังกล่าว^{[ 1 ]}

ข้อจำกัดอีกประเภทหนึ่งที่ใช้กันทั่วไปคือข้อจำกัดแบบสะสม ซึ่งcumulativeถูกนำมาใช้ในปัญหาเกี่ยวกับการจัดตารางเวลาและการจัดวาง ตัวอย่างเช่นcumulative([S1,...,Sm], [D1,...,Dm], [R1,...,Rm], L)สามารถใช้เพื่อกำหนดเงื่อนไขที่มีmกิจกรรมต่างๆ โดยแต่ละกิจกรรมมีเวลาเริ่มต้นsiระยะเวลา และใช้ ทรัพยากรdiจำนวนหนึ่ง ข้อจำกัดนี้ระบุว่าปริมาณทรัพยากรทั้งหมดที่มีอยู่คือ เทคนิคการแพร่กระจายข้อจำกัดแบบสะสมเฉพาะทางก็มีอยู่ โดยใช้เทคนิคที่แตกต่างกันไปขึ้นอยู่กับว่าโดเมนของตัวแปรใดถูกลดเหลือค่าเดียวแล้วriL

ข้อจำกัดเฉพาะประการที่สามที่ใช้ในการเขียนโปรแกรมเชิงตรรกะแบบมีข้อ จำกัด คือelementข้อจำกัดแบบลิสต์ ในการเขียนโปรแกรมเชิงตรรกะแบบมีข้อจำกัด อนุญาตให้ใช้ลิสต์เป็นค่าของตัวแปรได้ ข้อจำกัดelement(I, L, X)จะถือว่าเป็นจริงก็ต่อเมื่อLเป็นลิสต์ และXเป็นIองค์ประกอบที่ ของลิสต์นี้ มีกฎการแพร่กระจายข้อจำกัดเฉพาะสำหรับข้อจำกัดเหล่านี้อยู่ ตัวอย่างเช่น ถ้าLและIถูกลดทอนให้เหลือโดเมนค่าเดียว ค่าที่ไม่ซ้ำกันสำหรับXสามารถกำหนดได้ โดยทั่วไปแล้ว ค่าที่เป็นไปไม่ได้ของXสามารถอนุมานได้จากโดเมนของ${\displaystyle I}$และในทางกลับกัน

หากอัลกอริทึมประเมินตัวแปรตามลำดับ${\displaystyle x_{1},\ldots ,x_{n}}$ความสอดคล้องจะมีประโยชน์ก็ต่อเมื่อรับประกันได้ว่าค่าของตัวแปรที่มีดัชนีต่ำกว่านั้นสอดคล้องกับค่าของตัวแปรที่มีดัชนีสูงกว่าทั้งหมด

ในการเลือกค่าสำหรับตัวแปร ค่าที่ไม่สอดคล้องกับค่าทั้งหมดของตัวแปรที่ยังไม่ได้กำหนดค่าสามารถละเลยได้ อันที่จริง แม้ว่าค่าเหล่านี้จะสอดคล้องกับการประเมินค่าบางส่วนในปัจจุบัน แต่ในภายหลังอัลกอริทึมก็จะล้มเหลวในการหาค่าที่สอดคล้องกับตัวแปรที่ยังไม่ได้กำหนดค่า ในทางกลับกัน การบังคับให้สอดคล้องกับตัวแปรที่ได้รับการประเมินค่าแล้วนั้นไม่จำเป็น: หากอัลกอริทึมเลือกค่าที่ไม่สอดคล้องกับการประเมินค่าบางส่วนในปัจจุบัน ความไม่สอดคล้องนั้นก็จะถูกตรวจพบอยู่ดี

โดยสมมติว่าลำดับการประเมินค่าของตัวแปรเป็นดังนี้${\displaystyle x_{1},\ldots ,x_{n}}$ปัญหาการแก้ข้อจำกัดจะมีความสอดคล้องเชิงทิศทางก็ต่อเมื่อตัวแปรทุกตัว${\displaystyle x_{i}}$ส่วนโค้งนั้นสอดคล้องกับตัวแปรอื่นหรือไม่${\displaystyle x_{j}}$โดยที่${\displaystyle i<j}$ความสอดคล้องของเส้นทางทิศทางนั้นคล้ายกัน แต่มีตัวแปรสองตัว${\displaystyle x_{i},x_{j}}$จะต้องสอดคล้องกับเส้นทาง${\displaystyle x_{z}}$เฉพาะในกรณีที่${\displaystyle i,j<z}$ความสอดคล้องของเส้นทางทิศทางที่แข็งแกร่ง หมายถึงทั้งความสอดคล้องของเส้นทางทิศทางและความสอดคล้องของส่วนโค้งทิศทาง สามารถให้คำจำกัดความที่คล้ายกันสำหรับความสอดคล้องในรูปแบบอื่นๆ ได้เช่นกัน

การแพร่กระจายข้อจำกัดที่บังคับใช้ความสอดคล้องของส่วนโค้งทิศทางจะวนซ้ำตัวแปรจากตัวสุดท้ายไปยังตัวแรก โดยในแต่ละขั้นตอนจะบังคับใช้ความสอดคล้องของส่วนโค้งของตัวแปรทุกตัวที่มีดัชนีต่ำกว่ากับตัวแปรนั้น หากลำดับของตัวแปรเป็น${\displaystyle x_{1},\ldots ,x_{n}}$อัลกอริทึมนี้จะวนซ้ำตัวแปรต่างๆ จาก${\displaystyle x_{n}}$ถึง${\displaystyle x_{1}}$; สำหรับตัวแปร${\displaystyle x_{j}}$โดยจะบังคับให้ตัวแปรทุกตัวที่มีดัชนีต่ำกว่ามีความสอดคล้องกันในส่วนโค้ง${\displaystyle j}$กับ${\displaystyle x_{j}}$.

ตัวอย่างที่ไม่สอดคล้องกับส่วนโค้งทิศทาง:${\displaystyle x_{1}=2}$ไม่สอดคล้องกับค่าใดๆ ของ${\displaystyle x_{2}}$และ${\displaystyle x_{2}=3}$ไม่สอดคล้องกับค่าใดๆ ของ${\displaystyle x_{3}}$ไม่มีข้อจำกัดใดๆ ระหว่างกัน${\displaystyle x_{1}}$และ${\displaystyle x_{3}}$(ละเว้นขอบที่เกี่ยวข้อง)	การบังคับใช้ความสม่ำเสมอของเส้นโค้งทิศทางเริ่มต้นด้วย${\displaystyle x_{3}}$และทำให้${\displaystyle x_{2}}$ส่วนโค้งนั้นสอดคล้องกับการลบค่าออก${\displaystyle x_{2}=3}$.	การบังคับใช้ความสม่ำเสมอของส่วนโค้งทิศทางดำเนินต่อไปด้วย${\displaystyle x_{2}}$. เนื่องจาก${\displaystyle x_{2}=3}$ได้ถูกลบออกไปแล้วทั้งสองอย่าง${\displaystyle x_{1}=2}$และ${\displaystyle x_{1}=3}$ถูกลบออกแล้ว

ความสอดคล้องของเส้นทางทิศทางและความสอดคล้องของเส้นทางทิศทางที่เข้มงวดสามารถบังคับใช้ได้ด้วยอัลกอริธึมที่คล้ายกับอัลกอริธึมสำหรับความสอดคล้องของส่วนโค้ง โดยจะประมวลผลตัวแปรจาก${\displaystyle x_{n}}$ถึง${\displaystyle x_{1}}$สำหรับทุกตัวแปร${\displaystyle x_{z}}$ตัวแปรสองตัว${\displaystyle x_{i},x_{j}}$กับ${\displaystyle i,j<z}$ได้รับการพิจารณาแล้ว และความสอดคล้องของเส้นทางของพวกมันด้วย${\displaystyle x_{z}}$มีการบังคับใช้ ไม่จำเป็นต้องดำเนินการใดๆ หากปัญหานั้นไม่มีข้อจำกัดใดๆ${\displaystyle x_{i}}$และ${\displaystyle x_{z}}$หรือไม่มีข้อจำกัดระหว่าง${\displaystyle x_{j}}$และ${\displaystyle x_{z}}$อย่างไรก็ตาม แม้ว่าจะไม่มีข้อจำกัดใดๆ ระหว่างกันก็ตาม${\displaystyle x_{i}}$และ${\displaystyle x_{j}}$โดยทั่วไปจะถือว่าเป็นข้อจำกัดที่ไม่สำคัญ หากการแพร่กระจายข้อจำกัดลดชุดของการกำหนดค่าที่ตรงตามเงื่อนไขลง มันจะสร้างข้อจำกัดใหม่ที่ไม่ใช่เรื่องไม่สำคัญขึ้นมา การแพร่กระจายข้อจำกัดที่บังคับใช้ความสอดคล้องของเส้นทางทิศทางที่เข้มงวดนั้นคล้ายกัน แต่ยังบังคับใช้ความสอดคล้องของส่วนโค้งด้วย

ความสอดคล้องเชิงทิศทางรับประกันว่าคำตอบบางส่วนที่ตรงตามเงื่อนไขสามารถขยายไปยังตัวแปรอื่นที่มีดัชนีสูงกว่าได้อย่างสอดคล้อง อย่างไรก็ตาม มันไม่รับประกันว่าการขยายไปยังตัวแปรที่แตกต่างกันจะสอดคล้องกัน ตัวอย่างเช่น คำตอบบางส่วนอาจขยายไปยังตัวแปรได้อย่างสอดคล้อง${\displaystyle x_{i}}$หรือเป็นตัวแปร${\displaystyle x_{j}}$แต่ถึงกระนั้น ส่วนขยายทั้งสองนี้ก็ไม่สอดคล้องกัน

มีสองกรณีที่สิ่งนี้ไม่เกิดขึ้น และความสอดคล้องเชิงทิศทางรับประกันความสามารถในการทำให้เป็นจริงได้หากไม่มีโดเมนว่างเปล่าและไม่มีข้อจำกัดใดที่ไม่สามารถทำให้เป็นจริงได้

กรณีแรกคือปัญหาข้อจำกัดแบบไบนารีที่มีลำดับของตัวแปรที่ทำให้กราฟข้อจำกัดมีความกว้าง 1 ลำดับดังกล่าวมีอยู่ก็ต่อเมื่อกราฟข้อจำกัดเป็นต้นไม้เท่านั้น หากเป็นเช่นนั้น ความกว้างของกราฟจะจำกัดจำนวนสูงสุดของโหนดที่ต่ำกว่า (ตามลำดับ) ที่โหนดหนึ่งเชื่อมต่อด้วย ความสอดคล้องของส่วนโค้งทิศทางรับประกันว่าการกำหนดค่าที่สอดคล้องกันทุกค่าให้กับตัวแปรสามารถขยายไปยังโหนดที่สูงกว่าได้ และความกว้าง 1 รับประกันว่าโหนดจะไม่เชื่อมต่อกับโหนดที่ต่ำกว่ามากกว่าหนึ่งโหนด ผลก็คือ เมื่อกำหนดค่าให้กับตัวแปรที่ต่ำกว่าแล้ว ค่าของมันสามารถขยายไปยังตัวแปรที่สูงกว่าทุกตัวที่เชื่อมต่อด้วยได้อย่างสอดคล้อง การขยายนี้จะไม่นำไปสู่ความไม่สอดคล้องกันในภายหลัง อันที่จริงแล้ว ไม่มีตัวแปรที่ต่ำกว่าอื่นใดเชื่อมต่อกับตัวแปรที่สูงกว่านั้นอีก เนื่องจากกราฟมีความกว้าง 1

ด้วยเหตุนี้ หากปัญหาข้อจำกัดมีความกว้าง 1 เมื่อพิจารณาตามลำดับของตัวแปร (ซึ่งหมายความว่ากราฟที่เกี่ยวข้องเป็นต้นไม้) และปัญหานั้นมีความสอดคล้องของส่วนโค้งในทิศทางเดียวกันเมื่อพิจารณาตามลำดับเดียวกันนั้นแล้ว จะสามารถหาคำตอบได้ (ถ้ามี) โดยการกำหนดตัวแปรซ้ำๆ ตามลำดับนั้น

กรณีที่สองที่ความสอดคล้องเชิงทิศทางรับประกันความสามารถในการหาคำตอบได้หากไม่มีโดเมนว่างเปล่าและไม่มีข้อจำกัดใดที่ไม่สามารถหาคำตอบได้ คือกรณีของปัญหาข้อจำกัดแบบไบนารีที่มีกราฟความกว้างเหนี่ยวนำเท่ากับ 2 โดยใช้ความสอดคล้องเชิงเส้นทางแบบทิศทางที่แข็งแกร่ง อันที่จริง ความสอดคล้องในรูปแบบนี้รับประกันว่าการกำหนดค่าให้กับตัวแปรหรือคู่ของตัวแปรทุกตัวสามารถขยายไปยังตัวแปรที่สูงกว่าได้ และความกว้าง 2 รับประกันว่าตัวแปรนี้จะไม่ถูกเชื่อมโยงกับคู่ของตัวแปรที่ต่ำกว่าอีกคู่หนึ่ง

เหตุผลที่พิจารณาความกว้างที่เหนี่ยวนำแทนความกว้างปกติก็คือ การบังคับใช้ความสอดคล้องของเส้นทางแบบทิศทางอาจเพิ่มข้อจำกัด กล่าวคือ หากตัวแปรสองตัวไม่ได้อยู่ในข้อจำกัดเดียวกัน แต่ไปอยู่ในข้อจำกัดที่มีตัวแปรที่สูงกว่า ค่าบางคู่ของตัวแปรเหล่านั้นอาจละเมิดความสอดคล้องของเส้นทาง การลบคู่ค่าดังกล่าวจะสร้างข้อจำกัดใหม่ ส่งผลให้การแพร่กระจายของข้อจำกัดอาจทำให้กราฟของปัญหามีจำนวนขอบมากกว่ากราฟเดิม อย่างไรก็ตาม ขอบทั้งหมดเหล่านี้จำเป็นต้องอยู่ในกราฟที่เหนี่ยวนำ เนื่องจากขอบเหล่านั้นอยู่ระหว่างโหนดแม่สองโหนดของโหนดเดียวกัน ความกว้าง 2 รับประกันว่าการประเมินค่าบางส่วนที่สอดคล้องกันทุกครั้งสามารถขยายไปสู่คำตอบได้ แต่ความกว้างนี้สัมพันธ์กับกราฟที่สร้างขึ้น ดังนั้น ความกว้างที่เหนี่ยวนำต้องเป็น 2 จึงจำเป็นสำหรับความสอดคล้องของเส้นทางแบบทิศทางที่เข้มแข็ง เพื่อรับประกันการมีอยู่ของคำตอบ

ทิศทาง${\displaystyle i}$-ความสม่ำเสมอคือการรับประกันว่าการมอบหมายงานที่สอดคล้องกันทุกครั้งจะเป็นไปอย่างราบรื่น${\displaystyle i-1}$ตัวแปรสามารถขยายไปยังตัวแปรอื่นที่มีลำดับสูงกว่าได้อย่างสม่ำเสมอ มีทิศทางที่ชัดเจน${\displaystyle i}$-ความสอดคล้องถูกกำหนดในลักษณะที่คล้ายคลึงกัน แต่กลุ่มทั้งหมดไม่เกิน${\displaystyle i-1}$มีการพิจารณาตัวแปรต่างๆ หากปัญหามีทิศทางที่ชัดเจนมาก${\displaystyle i}$-สม่ำเสมอและมีความกว้างน้อยกว่า${\displaystyle i}$และหากไม่มีโดเมนว่างเปล่าหรือข้อจำกัดที่ไม่สามารถหาคำตอบได้ ก็ย่อมมีคำตอบ

ทุกปัญหาสามารถกำหนดทิศทางได้อย่างชัดเจน${\displaystyle i}$- สอดคล้องกัน แต่การดำเนินการนี้อาจเพิ่มความกว้างของกราฟที่เกี่ยวข้องได้ ขั้นตอนการแพร่กระจายข้อจำกัดที่บังคับใช้ความสอดคล้องในทิศทางนั้นคล้ายกับที่ใช้สำหรับความสอดคล้องของส่วนโค้งในทิศทางและความสอดคล้องของเส้นทาง ตัวแปรจะถูกพิจารณาตามลำดับ จากตัวสุดท้ายไปจนถึงตัวแรก สำหรับตัวแปร${\displaystyle x_{k}}$อัลกอริทึมจะพิจารณากลุ่มทุกกลุ่มของ${\displaystyle i-1}$ตัวแปรที่มีดัชนีต่ำกว่า${\displaystyle k}$และอยู่ในข้อจำกัดกับ${\displaystyle x_{k}}$ความสอดคล้องของตัวแปรเหล่านี้กับ${\displaystyle x_{k}}$มีการตรวจสอบและอาจบังคับใช้โดยการลบการกำหนดค่าที่ตรงตามเงื่อนไขออกจากข้อจำกัดในบรรดาสิ่งเหล่านี้ทั้งหมด${\displaystyle i}$ตัวแปร (ถ้ามี หรือสร้างตัวแปรใหม่หากไม่มี)

กระบวนการนี้ก่อให้เกิดทิศทางที่ชัดเจนมาก${\displaystyle i}$-อินสแตนซ์ที่สอดคล้องกัน อย่างไรก็ตาม มันอาจเพิ่มข้อจำกัดใหม่ให้กับอินสแตนซ์ด้วย ส่งผลให้แม้ว่าความกว้างของปัญหาเดิมจะเป็น${\displaystyle i}$ความกว้างของอินสแตนซ์ที่ได้อาจมีขนาดใหญ่ขึ้น หากเป็นเช่นนั้นความสอดคล้องที่แข็งแกร่ง ในทิศทางเดียว ไม่ได้หมายความถึงความสามารถในการทำให้เป็นจริงได้ แม้ว่าจะไม่มีโดเมนใดว่างเปล่าและไม่มีข้อจำกัดใดที่ไม่สามารถทำให้เป็นจริงได้ ก็ตาม

อย่างไรก็ตาม การแพร่กระจายข้อจำกัดจะเพิ่มข้อจำกัดให้กับตัวแปรที่มีค่าน้อยกว่าตัวแปรที่กำลังพิจารณาอยู่เท่านั้น ดังนั้น เมื่ออัลกอริทึมได้จัดการกับตัวแปรนั้นแล้ว ข้อจำกัดใดๆ เกี่ยวกับตัวแปรจะไม่ถูกแก้ไขหรือเพิ่มเติม แทนที่จะพิจารณาค่าคงที่${\displaystyle i}$เราสามารถปรับเปลี่ยนให้เป็นจำนวนผู้ปกครองของตัวแปรแต่ละตัวที่พิจารณา (ผู้ปกครองของตัวแปรคือตัวแปรที่มีดัชนีต่ำกว่าตัวแปรนั้นและมีความสัมพันธ์แบบจำกัดกับตัวแปรนั้น) ซึ่งสอดคล้องกับการพิจารณาผู้ปกครองทั้งหมดของตัวแปรที่กำหนดในแต่ละขั้นตอน กล่าวอีกนัยหนึ่งคือ สำหรับแต่ละตัวแปร${\displaystyle x_{i}}$จากตัวสุดท้ายไปจนถึงตัวแรก พ่อแม่ทั้งหมดของมันจะถูกรวมอยู่ในข้อจำกัดใหม่ที่จำกัดค่าของพวกมันให้อยู่ในขอบเขตที่สอดคล้องกับ${\displaystyle x_{i}}$เนื่องจากอัลกอริธึมนี้สามารถมองได้ว่าเป็นการดัดแปลงจากอัลกอริธึมก่อนหน้าโดยมีค่าหนึ่ง${\displaystyle i}$ หากค่าดังกล่าวถูกเปลี่ยนแปลงไปตามจำนวนของโหนดแม่ของแต่ละโหนด จะเรียกว่าความสอดคล้องแบบปรับตัวได้ (adaptive consistency )

อัลกอริทึมนี้บังคับใช้ทิศทางที่ชัดเจนอย่างมาก${\displaystyle i}$-ความสอดคล้องกับ${\displaystyle i}$เท่ากับความกว้างที่เหนี่ยวนำของปัญหา อินสแตนซ์ที่ได้จะสามารถหาคำตอบได้ก็ต่อเมื่อไม่มีโดเมนหรือข้อจำกัดใดว่างเปล่า หากเป็นเช่นนั้น สามารถหาคำตอบได้ง่ายๆ โดยการกำหนดค่าให้กับตัวแปรที่ไม่ได้กำหนดค่าไว้ซ้ำๆ เป็นค่าใดๆ ก็ได้ และกระจายการประเมินค่าบางส่วนนี้ไปยังตัวแปรอื่นๆ อัลกอริทึมนี้ไม่ได้ใช้เวลาแบบพหุนามเสมอไป เนื่องจากจำนวนข้อจำกัดที่นำมาใช้โดยการบังคับใช้ความสอดคล้องเชิงทิศทางที่เข้มงวดอาจทำให้ขนาดเพิ่มขึ้นแบบเลขชี้กำลัง อย่างไรก็ตาม ปัญหาสามารถแก้ไขได้ในเวลาแบบพหุนามหากการบังคับใช้ความสอดคล้องเชิงทิศทางที่เข้มงวดไม่ได้ทำให้ ขนาดของอินสแตนซ์ขยายใหญ่ขึ้น เกินพหุนามดังนั้น หากอินสแตนซ์มีความกว้างที่เหนี่ยวนำซึ่งถูกจำกัดด้วยค่าคงที่ ก็สามารถแก้ไขได้ในเวลาแบบพหุนาม

การกำจัดบัคเก็ต (Bucket elimination) เป็นอัลกอริธึมที่ทำให้เป็นจริงได้ (satisfiability algorithm) สามารถนิยามได้ว่าเป็นการปรับปรุงใหม่ของความสอดคล้องแบบปรับตัว (adaptive consistency) คำนิยามของมันใช้บัคเก็ต ซึ่งเป็นภาชนะสำหรับข้อจำกัด โดยแต่ละตัวแปรจะมีบัคเก็ตที่เกี่ยวข้อง ข้อจำกัดจะอยู่ในกลุ่มของตัวแปรที่มีค่าสูงสุดเสมอ

อัลกอริทึมการกำจัดกลุ่มจะดำเนินการจากตัวแปรที่มีค่าสูงสุดไปยังตัวแปรที่มีค่าต่ำสุดตามลำดับ ในแต่ละขั้นตอน ข้อจำกัดในกลุ่มของตัวแปรนี้จะถูกปรับเปลี่ยน${\displaystyle x_{i}}$จะถูกนำมาพิจารณา ตามคำจำกัดความ ข้อจำกัดเหล่านี้จะเกี่ยวข้องเฉพาะตัวแปรที่มีค่าน้อยกว่าเท่านั้น${\displaystyle x_{i}}$อัลกอริทึมจะปรับเปลี่ยนข้อจำกัดระหว่างตัวแปรล่างเหล่านี้ (ถ้ามี มิฉะนั้นจะสร้างข้อจำกัดใหม่) โดยเฉพาะอย่างยิ่ง จะบังคับให้ค่าของตัวแปรเหล่านั้นสามารถขยายได้${\displaystyle x_{i}}$สอดคล้องกับข้อจำกัดในถังของ${\displaystyle x_{i}}$ข้อจำกัดใหม่นี้ (ถ้ามี) จะถูกจัดไว้ในหมวดหมู่ที่เหมาะสม เนื่องจากข้อจำกัดนี้เกี่ยวข้องเฉพาะตัวแปรที่มีค่าน้อยกว่า${\displaystyle x_{i}}$โดยจะถูกเพิ่มเข้าไปในถังของตัวแปรที่มีค่าต่ำกว่า${\displaystyle x_{i}}$.

อัลกอริทึมนี้เทียบเท่ากับการบังคับใช้ความสอดคล้องแบบปรับตัวได้ เนื่องจากทั้งสองวิธีบังคับใช้ความสอดคล้องของตัวแปรกับตัวแปรแม่ทั้งหมด และเนื่องจากไม่มีการเพิ่มข้อจำกัดใหม่หลังจากพิจารณาตัวแปรแล้ว ผลลัพธ์ที่ได้คือกรณีที่สามารถแก้ไขได้โดยไม่ต้องย้อนกลับ

เนื่องจากกราฟของอินสแตนซ์ที่สร้างขึ้นเป็นกราฟย่อยของกราฟที่เหนี่ยวนำ หากความกว้างที่เหนี่ยวนำถูกจำกัดด้วยค่าคงที่ อินสแตนซ์ที่สร้างขึ้นจะมีขนาดเป็นพหุนามของขนาดอินสแตนซ์ดั้งเดิม ดังนั้น หากความกว้างที่เหนี่ยวนำของอินสแตนซ์ถูกจำกัดด้วยค่าคงที่ การแก้ปัญหาจึงสามารถทำได้ในเวลาพหุนามโดยอัลกอริทึมทั้งสอง

ปัญหาการแก้ข้อจำกัดอาจมีความสอดคล้องเชิงสัมพันธ์ ไม่มีโดเมนว่างเปล่า หรือข้อจำกัดที่ไม่สามารถหาคำตอบได้ แต่ก็ยังไม่สามารถหาคำตอบได้ อย่างไรก็ตาม มีบางกรณีที่สิ่งนี้เป็นไปไม่ได้

กรณีแรกคือกรณีที่มีความสัมพันธ์อย่างแน่นแฟ้น${\displaystyle m}$-ปัญหาที่เกิดขึ้นอย่างสม่ำเสมอเมื่อโดเมนมีจำนวนไม่เกิน${\displaystyle m}$องค์ประกอบ ในกรณีนี้ การประเมินอย่างสม่ำเสมอของ${\displaystyle k}$ตัวแปรสามารถขยายไปเป็นตัวแปรอื่นได้เพียงตัวเดียวเสมอ ถ้า${\displaystyle x_{1}=a_{1},\ldots ,x_{k}=a_{k}}$การประเมินเช่นนั้นและ${\displaystyle x_{k+1}}$คือตัวแปร มีเพียงเท่านั้น${\displaystyle m}$ค่าที่เป็นไปได้ที่ตัวแปรสามารถรับได้ หากค่าทั้งหมดเหล่านั้นไม่สอดคล้องกับการประเมิน จะมี${\displaystyle m}$ข้อจำกัด (ที่ไม่จำเป็นต้องเป็นเอกลักษณ์) ที่ถูกละเมิดโดยการประเมินและค่าที่เป็นไปได้ค่าหนึ่ง ส่งผลให้การประเมินไม่สามารถขยายให้ตรงตามข้อจำกัดเหล่านี้ทั้งหมดได้${\displaystyle m}$ข้อจำกัด -หรือ-น้อยกว่านั้น ละเมิดเงื่อนไขของความสัมพันธ์ที่แข็งแกร่ง${\displaystyle m}$-ความสม่ำเสมอ

กรณีที่สองเกี่ยวข้องกับการวัดข้อจำกัดมากกว่าขอบเขต ข้อจำกัดคือ${\displaystyle m}$- แน่น หากการประเมินค่าทุกค่าของตัวแปรทั้งหมด ยกเว้นตัวแปรเดียว สามารถขยายให้สอดคล้องกับข้อจำกัดได้ ไม่ว่าจะโดยค่าที่เป็นไปได้ทั้งหมดของตัวแปรอื่น หรือโดยค่าไม่เกิน${\displaystyle m}$ของค่าของมัน ปัญหาที่มี${\displaystyle m}$ข้อจำกัดที่เข้มงวดจะสามารถปฏิบัติตามได้ก็ต่อเมื่อมีความสัมพันธ์กันอย่างแน่นแฟ้นเท่านั้น${\displaystyle m+1}$-สม่ำเสมอ.

กรณีที่สามคือข้อจำกัดแบบไบนารีที่สามารถแสดงได้ด้วยเมทริกซ์แบบนูนตามแถว ข้อจำกัดแบบไบนารีสามารถแสดงได้ด้วยเมทริกซ์สองมิติ${\displaystyle M}$, ที่ไหน${\displaystyle M_{ij}}$มีค่าเป็น 0 หรือ 1 ขึ้นอยู่กับว่า${\displaystyle i}$ค่าลำดับที่ - ของโดเมนของ${\displaystyle x_{i}}$และ${\displaystyle j}$ค่าลำดับที่ - ของโดเมนของ${\displaystyle x_{j}}$เป็นไปตามเงื่อนไขที่กำหนด แถวของเมทริกซ์นี้จะเป็นเมทริกซ์นูนก็ต่อเมื่อเลข 1 ในแถวนั้นเรียงติดกัน (กล่าวคือ ถ้าเลข 1 สองตัวในแถวนั้น เลข 1 ระหว่างสองตัวนั้นก็จะเป็น 1 ด้วย) เมทริกซ์จะเป็นเมทริกซ์นูนตามแถวก็ต่อเมื่อทุกแถวของเมทริกซ์นั้นเป็นเมทริกซ์นูน

เงื่อนไขที่ทำให้ความสอดคล้องของเส้นทางเชิงสัมพันธ์ที่แข็งแกร่งเทียบเท่ากับความสามารถในการทำให้เป็นจริงได้ คือ เงื่อนไขของปัญหาการแก้ข้อจำกัด ซึ่งมีลำดับของตัวแปรที่ทำให้ข้อจำกัดทั้งหมดสามารถแทนด้วยเมทริกซ์นูนแถวได้ ผลลัพธ์นี้อิงจากข้อเท็จจริงที่ว่า เซตของแถวนูนที่มีองค์ประกอบร่วมกันเป็นคู่ๆ จะมีองค์ประกอบร่วมกันโดยรวมด้วย พิจารณาการประเมินค่าเหนือ${\displaystyle k}$ตัวแปร ค่าที่อนุญาตสำหรับ${\displaystyle k+1}$ลำดับที่ - ได้มาจากการเลือกบางแถวจากข้อจำกัดบางประการ โดยเฉพาะอย่างยิ่ง สำหรับตัวแปรทุกตัวในกลุ่ม${\displaystyle k}$หนึ่ง แถวที่สัมพันธ์กับค่าในเมทริกซ์ที่แสดงถึงข้อจำกัดที่เชื่อมโยงกับ${\displaystyle k+1}$หนึ่งแสดงถึงค่าที่อนุญาตของตัวแปรหลัง เนื่องจากแถวเหล่านี้เป็นแบบนูน และมีองค์ประกอบร่วมกันเป็นคู่ๆ เนื่องมาจากความสอดคล้องของเส้นทาง จึงมีองค์ประกอบร่วมที่ใช้ร่วมกัน ซึ่งแสดงถึงค่าของตัวแปรสุดท้ายที่สอดคล้องกับตัวแปรอื่นๆ