ปัญหาการแก้ข้อจำกัด ( Constraint Satisfaction Problems : CSPs ) คือคำถามทางคณิตศาสตร์ที่กำหนดไว้เป็นชุดของวัตถุซึ่งสถานะของวัตถุ เหล่านั้น ต้องเป็นไปตามข้อจำกัดหรือเงื่อนไข จำนวนหนึ่ง CSPs แสดงถึงเอนทิตีในปัญหาในรูปของชุดข้อจำกัดที่จำกัดและเหมือนกันสำหรับตัวแปรต่างๆซึ่งสามารถแก้ไขได้ด้วย วิธี การแก้ปัญหาข้อจำกัด CSPs เป็นหัวข้อการวิจัยในทั้งปัญญาประดิษฐ์และการวิจัยเชิงปฏิบัติการเนื่องจากความสม่ำเสมอในการกำหนดรูปแบบของปัญหาทำให้มีพื้นฐานร่วมกันในการวิเคราะห์และแก้ปัญหาในหลายๆ ตระกูลที่ดูเหมือนไม่เกี่ยวข้องกันCSPs มักมีความซับซ้อนสูงจึงต้องใช้การผสมผสานระหว่าง วิธีการ ฮิวริสติกและการค้นหาเชิงผสมผสานเพื่อแก้ปัญหาให้เสร็จภายในเวลาที่เหมาะสมการเขียนโปรแกรมข้อจำกัด (Constraint Programming : CP) คือสาขาการวิจัยที่มุ่งเน้นการแก้ปัญหาประเภทนี้โดยเฉพาะ^{[ 1 ] [ 2 ]}นอกจากนี้ปัญหาความพึงพอใจของบูลีน (SAT) ความพึงพอใจโมดูลทฤษฎี (SMT) การเขียนโปรแกรมจำนวนเต็มแบบผสม (MIP) และการเขียนโปรแกรมชุดคำตอบ (ASP) ล้วนเป็นสาขาการวิจัยที่มุ่งเน้นการแก้ปัญหาความพึงพอใจข้อจำกัดในรูปแบบเฉพาะ

ตัวอย่างของปัญหาที่สามารถจำลองได้ในรูปแบบของปัญหาการแก้ข้อจำกัด ได้แก่:

• การอนุมานประเภท^{[ 3 ] [ 4 ]}
• ปริศนาราชินีแปดองค์
• ปัญหาการระบายสีแผนที่
• ปัญหาการตัดสูงสุด^{[ 5 ]}
• ซูโดกุ , ปริศนาอักษรไขว้ , ฟูโตชิกิ , คาคุโระ (ผลรวมไขว้), นัมบริกซ์ / ฮิดาโตะ , ปริศนาม้าลายและปริศนาตรรกะ อื่นๆ อีกมากมาย

โดยทั่วไปแล้ว สิ่งเหล่านี้มักมีบทเรียนเกี่ยวกับ การแก้ปัญหา CP , ASP, Boolean SAT และ SMT โดยทั่วไปแล้ว ปัญหาข้อจำกัดอาจยากกว่ามาก และอาจไม่สามารถแสดงออกมาได้ในระบบที่ง่ายกว่าเหล่านี้ ตัวอย่าง "ในชีวิตจริง" ได้แก่การวางแผนอัตโนมัติ [ ^{6 ] [ 7 ]}การแยกความหมายของคำศัพท์^{[ 8 ] [ 9 ]}ดนตรีวิทยา [ ^{10 ] การ กำหนด}ค่าผลิตภัณฑ์^{[ 11 ]}และการ^{จัดสรร}ทรัพยากร^{[ 12 ]}

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

ในทางรูปแบบ ปัญหาความพึงพอใจของข้อจำกัดถูกกำหนดให้เป็นสามสิ่งโดยที่^{[ 13 ]}${\displaystyle \langle X,D,C\rangle }$

• ${\displaystyle X=\{X_{1},\ldots ,X_{n}\}}$คือชุดของตัวแปร
• ${\displaystyle D=\{D_{1},\ldots ,D_{n}\}}$คือชุดของโดเมนค่าของแต่ละฝ่าย และ
• ${\displaystyle C=\{C_{1},\ldots ,C_{m}\}}$คือชุดของข้อจำกัด

แต่ละตัวแปรสามารถรับค่าได้ในโดเมนที่ไม่ว่างเปล่า ข้อจำกัดแต่ละข้อเป็นคู่โดยที่คือเซตของดัชนี และคือความสัมพันธ์ แบบ n-ary บนผลคูณของโดเมนที่สอดคล้องกัน โดยผลคูณจะเรียงลำดับดัชนีจากน้อยไปมากการประเมินค่าของตัวแปรเป็นฟังก์ชันจากเซตย่อยของตัวแปรไปยังเซตของค่าเฉพาะในเซตย่อยของโดเมนที่สอดคล้องกัน การประเมินค่าจะตรงตามข้อจำกัดก็ต่อเมื่อค่าที่กำหนดให้กับตัวแปรตรงตามความสัมพันธ์ ${\displaystyle X_{i}}$${\displaystyle D_{i}}$${\displaystyle C_{j}\in C}$${\displaystyle \langle t_{j},R_{j}\rangle }$${\displaystyle t_{j}\subseteq \{1,2,\ldots ,n\}}$${\displaystyle k}$${\displaystyle R_{j}}$${\displaystyle k}$${\displaystyle \times _{i\in t_{j}}D_{i}}$${\displaystyle v}$${\displaystyle \langle t_{j},R_{j}\rangle }$${\displaystyle t_{j}}$${\displaystyle R_{j}}$

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

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

การย้อนกลับ (Backtracking)เป็นอัลกอริทึมแบบเรียกซ้ำ โดยจะรักษาการกำหนดค่าบางส่วนของตัวแปรไว้ ในขั้นต้น ตัวแปรทั้งหมดจะยังไม่มีการกำหนดค่า ในแต่ละขั้นตอน จะเลือกตัวแปรหนึ่งตัว และกำหนดค่าที่เป็นไปได้ทั้งหมดให้กับตัวแปรนั้นทีละค่า สำหรับแต่ละค่า จะตรวจสอบความสอดคล้องของการกำหนดค่าบางส่วนกับข้อจำกัด หากสอดคล้อง จะทำการเรียก ซ้ำเมื่อลองใช้ค่าทั้งหมดแล้ว อัลกอริทึมจะย้อนกลับ ในอัลกอริทึมการย้อนกลับพื้นฐานนี้ ความสอดคล้องถูกกำหนดให้เป็นการตรงตามข้อจำกัดทั้งหมดที่ตัวแปรได้รับการกำหนดค่าแล้ว มีการย้อนกลับหลายรูปแบบ การทำเครื่องหมายย้อนกลับ (Backmarking)ช่วยเพิ่มประสิทธิภาพในการตรวจสอบความสอดคล้อง การกระโดดย้อนกลับ (Backjumping)ช่วยประหยัดเวลาในการค้นหาโดยการย้อนกลับ "มากกว่าหนึ่งตัวแปร" ในบางกรณีการเรียนรู้ข้อจำกัด (Constraint learning)อนุมานและบันทึกข้อจำกัดใหม่ๆ ที่สามารถนำมาใช้ในภายหลังเพื่อหลีกเลี่ยงส่วนหนึ่งของการค้นหาการมองไปข้างหน้ามักถูกนำมาใช้ในการย้อนกลับเพื่อพยายามคาดการณ์ผลกระทบของการเลือกตัวแปรหรือค่า ซึ่งบางครั้งอาจช่วยกำหนดล่วงหน้าได้ว่าปัญหาย่อยนั้นสามารถแก้ไขได้หรือไม่อาจแก้ไขได้

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

วิธี การค้นหาแบบโลคอล (Local search)เป็นอัลกอริธึมที่มีความสามารถในการหาคำตอบที่ไม่สมบูรณ์ อาจพบคำตอบของปัญหาได้ แต่ก็อาจล้มเหลวได้แม้ว่าปัญหาจะสามารถหาคำตอบได้ก็ตาม วิธีการทำงานคือการปรับปรุงการกำหนดค่าที่สมบูรณ์ให้กับตัวแปรอย่างต่อเนื่อง ในแต่ละขั้นตอน จะมีการเปลี่ยนแปลงค่าของตัวแปรจำนวนเล็กน้อย โดยมีเป้าหมายโดยรวมคือการเพิ่มจำนวนข้อจำกัดที่ตรงตามการกำหนดค่านี้อัลกอริธึม min-conflictsเป็นอัลกอริธึมการค้นหาแบบโลคอลที่เฉพาะเจาะจงสำหรับปัญหา CSP (Constant Significant Problem) และมีพื้นฐานมาจากหลักการดังกล่าว ในทางปฏิบัติ การค้นหาแบบโลคอลดูเหมือนจะทำงานได้ดีเมื่อการเปลี่ยนแปลงเหล่านี้ได้รับผลกระทบจากการเลือกแบบสุ่มด้วย มีการพัฒนาการบูรณาการการค้นหากับการค้นหาแบบโลคอล ซึ่งนำไปสู่อัลกอริธึมแบบไฮบริด

CSP ยังได้รับการศึกษาในทฤษฎีความซับซ้อนของการคำนวณทฤษฎีแบบจำลองจำกัดและพีชคณิตสากลปรากฏว่าคำถามเกี่ยวกับความซับซ้อนของ CSP แปลงเป็นคำถามพีชคณิตสากลที่สำคัญเกี่ยวกับพีชคณิตพื้นฐาน แนวทางนี้เรียกว่าแนวทางพีชคณิตสำหรับ CSP ^{[ 15 ]}

เนื่องจากปัญหาการตัดสินใจเชิงคำนวณทุกปัญหาเทียบเท่ากับ CSP ที่มีแม่แบบอนันต์ใน เวลาพหุนาม ^{[ 16 ]} CSP ทั่วไปจึงสามารถมีความซับซ้อนได้ตามอำเภอใจ โดยเฉพาะอย่างยิ่ง ยังมี CSP อยู่ในกลุ่ม ปัญหา NP-ระดับกลางซึ่งการมีอยู่ของปัญหาเหล่านี้ได้รับการพิสูจน์โดยLadnerภายใต้สมมติฐานที่ว่าP ≠ NP

อย่างไรก็ตาม CSP จำนวนมากที่เกิดขึ้นจากแอปพลิเคชันตามธรรมชาติเป็นไปตามหลักการแบ่งความซับซ้อน ซึ่งหมายความว่า CSP ทุกตัวในกลุ่มนั้นจะอยู่ในPหรือNP-complete CSP เหล่านี้จึงเป็นหนึ่งในเซตย่อยที่ใหญ่ที่สุดของNP ที่รู้จัก ซึ่งหลีกเลี่ยง ปัญหา NP-intermediateหลักการแบ่งความซับซ้อนได้รับการพิสูจน์ครั้งแรกโดยSchaeferสำหรับ CSP แบบบูลีน กล่าวคือ CSP บนโดเมน 2 องค์ประกอบและที่ซึ่งความสัมพันธ์ที่มีอยู่ทั้งหมดเป็นตัวดำเนินการบูลีนผลลัพธ์นี้ได้รับการขยายความสำหรับ CSP หลายประเภท โดยเฉพาะอย่างยิ่งสำหรับ CSP ทั้งหมดบนโดเมนจำกัด ข้อสันนิษฐานการแบ่งโดเมนจำกัด นี้ ได้รับการกำหนดขึ้นครั้งแรกโดย Tomás Feder และ Moshe Vardi ^{[ 17 ]}และได้รับการพิสูจน์อย่างอิสระโดย Andrei Bulatov ^{[ 18 ]}และ Dmitriy Zhuk ในปี 2017 ^{[ 19 ]}

กลุ่มอื่นๆ ที่ได้รับการยืนยันว่ามีการแบ่งระดับความซับซ้อน ได้แก่

• การลดลำดับแรก ทั้งหมดของ, ^{[ 20 ]}${\displaystyle (\mathbb {Q} ,<)}$
• การลดลำดับแรกทั้งหมดของกราฟสุ่มที่นับได้^{[ 21 ]}
• รีดักต์ลำดับแรกทั้งหมดของคู่โมเดลของคลาสของความสัมพันธ์ C ทั้งหมด^{[ 22 ]}
• ^{รี ดัก}ต์ลำดับแรกทั้งหมดของโพเซต เอกพันธุ์สากล [ ^{23 ]}
• รีดักต์ลำดับแรกทั้งหมดของกราฟที่ไม่มีทิศทางแบบเอกพันธุ์^{[ 24 ]}
• รีดิวซ์ลำดับแรกทั้งหมดของโครงสร้างเอกภาคทั้งหมด^{[ 25 ]}
• CSP ทั้งหมดในคลาสความซับซ้อน MMSNP ^{[ 26 ]}

คลาสส่วนใหญ่ของ CSP ที่ทราบกันว่าสามารถจัดการได้คือคลาสที่ไฮเปอร์กราฟของข้อจำกัดมีtreewidth ที่จำกัด [ ^{27 ] หรือคลาสที่ข้อจำกัดมีรูป แบบ}ตามอำเภอใจ แต่มี polymorphism ที่ไม่ใช่สมการธรรมดาของชุดความสัมพันธ์ของข้อจำกัด^{[ 28 ]}

ข้อสันนิษฐานการแบ่งแยกโดเมนอนันต์^{[ 29 ]}ได้รับการกำหนดขึ้นสำหรับ CSP ทั้งหมดของการลดทอนของโครงสร้างเอกพันธุ์ที่มีขอบเขตจำกัด โดยระบุว่า CSP ของโครงสร้างดังกล่าวอยู่ใน P ก็ต่อเมื่อโคลนโพลีมอร์ฟิซึม ของมัน ไม่ธรรมดาในเชิงสมการ และจะเป็น NP-hard ในกรณีอื่น

ความซับซ้อนของ CSP โดเมนอนันต์ดังกล่าว รวมถึงการสรุปทั่วไปอื่นๆ (CSP ที่มีค่า, CSP ที่มีปริมาณ, CSP ที่มีคำมั่นสัญญา) ยังคงเป็นหัวข้อการวิจัยที่กำลังดำเนินอยู่^{[ 30 ]}

CSP ทุกตัวสามารถถือได้ว่าเป็นปัญหาการบรรจุแบบสอบถามแบบเชื่อมโยง เช่นกัน ^{[ 31 ]}

สถานการณ์ที่คล้ายกันนี้เกิดขึ้นระหว่างคลาสฟังก์ชันFPและ#Pโดยการวางนัยทั่วไปของทฤษฎีบทของ Ladnerยังมีปัญหาที่ไม่สมบูรณ์แบบ FP หรือ #P ตราบใด ที่ FP ≠ #P เช่นเดียวกับกรณีการตัดสินใจ ปัญหาใน #CSP ถูกกำหนดโดยชุดของความสัมพันธ์ แต่ละปัญหารับ สูตร บูลีนเป็นอินพุต และงานคือการคำนวณจำนวนการกำหนดค่าที่ตรงตามเงื่อนไข สิ่งนี้สามารถวางนัยทั่วไปได้อีกโดยใช้ขนาดโดเมนที่ใหญ่ขึ้นและแนบน้ำหนักให้กับการกำหนดค่าที่ตรงตามเงื่อนไขแต่ละรายการ และคำนวณผลรวมของน้ำหนักเหล่านี้ เป็นที่ทราบกันว่าปัญหา #CSP ที่ซับซ้อนที่มีน้ำหนักใดๆ ก็ตามจะอยู่ใน FP หรือ #P-hard ^{[ 32 ]}

แบบจำลองคลาสสิกของปัญหาความพึงพอใจข้อจำกัดกำหนดแบบจำลองของข้อจำกัดแบบคงที่และไม่ยืดหยุ่น แบบจำลองที่แข็งทื่อนี้เป็นข้อบกพร่องที่ทำให้ยากต่อการแสดงปัญหาได้อย่างง่ายดาย^{[ 33 ]}มีการเสนอการปรับเปลี่ยนคำจำกัดความพื้นฐานของ CSP หลายประการเพื่อปรับแบบจำลองให้เข้ากับปัญหาที่หลากหลาย

CSP แบบไดนามิก^{[ 34 ]} ( DCSP ) มีประโยชน์เมื่อการกำหนดปัญหาดั้งเดิมถูกเปลี่ยนแปลงในบางวิธี โดยทั่วไปเนื่องจากชุดข้อจำกัดที่ต้องพิจารณาพัฒนาไปตามสภาพแวดล้อม^{[ 35 ]} DCSP ถูกมองว่าเป็นลำดับของ CSP แบบคงที่ โดยแต่ละอันเป็นการแปลงจากอันก่อนหน้า ซึ่งสามารถเพิ่มตัวแปรและข้อจำกัด (ข้อจำกัด) หรือลบออก (การผ่อนคลาย) ได้ ข้อมูลที่พบในการกำหนดปัญหาเริ่มต้นสามารถนำมาใช้เพื่อปรับปรุงอันถัดไป วิธีการแก้ปัญหาสามารถจำแนกได้ตามวิธีการถ่ายโอนข้อมูล:

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

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

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

ใน DCSP ^{[ 36 ]}ตัวแปรข้อจำกัดแต่ละตัวถือว่ามีตำแหน่งทางภูมิศาสตร์ที่แยกจากกัน มีการกำหนดข้อจำกัดที่เข้มงวดในการแลกเปลี่ยนข้อมูลระหว่างตัวแปร ซึ่งต้องใช้อัลกอริธึมแบบกระจายอย่างสมบูรณ์เพื่อแก้ปัญหาความพึงพอใจของข้อจำกัด

• กราฟคอมโพสิตข้อจำกัด
• การเขียนโปรแกรมแบบมีข้อจำกัด
• การเขียนโปรแกรมเชิงประกาศ
• การหาค่าเหมาะสมที่สุดแบบมีข้อจำกัด (COP)
• การเพิ่มประสิทธิภาพข้อจำกัดแบบกระจาย
• กราฟโฮโมมอร์ฟิซึม
• การคาดเดาเกมที่ไม่เหมือนใคร
• ปัญหาการแก้ข้อจำกัดแบบถ่วงน้ำหนัก (WCSP)

• บทนำสั้นๆ เกี่ยวกับความพึงพอใจภายใต้ข้อจำกัด บน YouTube
• Manuel Bodirsky (2021). ความซับซ้อนของการแก้ปัญหาข้อจำกัดในโดเมนอนันต์สำนักพิมพ์มหาวิทยาลัยเคมบริดจ์https://doi.org/10.1017/9781107337534
• Steven Minton; Andy Philips; Mark D. Johnston; Philip Laird (1993). "การลดความขัดแย้งให้น้อยที่สุด: วิธีการซ่อมแซมแบบฮิวริสติกสำหรับปัญหาการตอบสนองต่อข้อจำกัดและการจัดตารางเวลา" วารสารการวิจัยปัญญาประดิษฐ์58 ( 1– 3): 161– 205. CiteSeerX  10.1.1.308.6637 . doi : 10.1016/0004-3702(92)90007-k . S2CID  14830518 .
• Tsang, Edward (1993). พื้นฐานของการแก้ปัญหาข้อจำกัด . สำนักพิมพ์ Academic Press.ISBN 0-12-701610-4
• Chen, Hubie (ธันวาคม 2009). "การนัดพบของตรรกศาสตร์ ความซับซ้อน และพีชคณิต". ACM Computing Surveys . 42 (1): 1– 32. arXiv : cs/0611018 . doi : 10.1145/1592451.1592453 . S2CID  11975818 .
• Dechter, Rina (2003). การประมวลผลข้อจำกัด . Morgan Kaufmann.ISBN 1-55860-890-7
• Apt, Krzysztof (2003). หลักการของการเขียนโปรแกรมแบบมีข้อจำกัด . สำนักพิมพ์มหาวิทยาลัยเคมบริดจ์. ISBN 9780521825832.ISBN 0-521-82583-0
• เลอคูเตอร์, คริสตอฟ (2009) เครือข่ายจำกัด: เทคนิคและอัลกอริทึม ไอสเต/ไวลีย์ISBN 978-1-84821-106-3
• Tomás Feder, ความพึงพอใจภายใต้ข้อจำกัด: มุมมองส่วนตัว , ต้นฉบับ.
• คลังเก็บข้อจำกัด
• เกณฑ์มาตรฐาน CSP ที่บังคับให้พึงพอใจของโมเดล RB เก็บถาวรเมื่อวันที่ 25 มกราคม 2021 ที่Wayback Machine
• เกณฑ์มาตรฐาน – การแสดงผลอินสแตนซ์ CSP ในรูปแบบ XML
• XCSP3 – รูปแบบ XML ที่ออกแบบมาเพื่อแสดงอินสแตนซ์ CSP
• การแพร่กระจายข้อจำกัด – วิทยานิพนธ์ของ Guido Tack ที่ให้ภาพรวมที่ดีเกี่ยวกับทฤษฎีและประเด็นการนำไปใช้