Constraint Satisfaction

Ask about this topic

Overview

Constraint satisfaction models problems with variables, possible values, and rules that determine which combinations are allowed, helping solve tasks such as scheduling, graph coloring, and Sudoku. Classical approaches include constraint propagation and backtracking, often combined with SAT, SMT, constraint programming, or integer programming solvers. Recent work also uses graph neural networks, diffusion models, and language models to propose assignments or guide search, frequently pairing them with symbolic verification and repair. A central challenge is making learned methods reliable on genuinely hard instances and robust to changes in problem size, representation, or wording, while matching the efficiency and guarantees of classical solvers.

Latest papers

CardsList

86 papers10 papers in the last four weeks, up 43% on the four weeks before. 0.1% of all new papers.

  1. Tiny Recursive Message Passing

    Oct 13, 2026Tommaso Salvatori, Matteo Forasassi, Alexis Toumi +1Neural Algorithmic ReasoningMessage Passing Neural Networks

    Relational Intelligence, Inc · Vienna University of Technology

  2. Dynamic Conflict Clustering with Lightweight Learning and Strategic Repair for Distributed Constraint Satisfaction

    Oct 11, 2026Raziyeh Moghaddas, Fabio CaraffiniConstraint SatisfactionCombinatorial Optimization

    Department of Science and Engineering, Swansea University, Swansea, UK

  3. Knowledge transfer between simple discrete worlds

    Oct 10, 2026Silvère Gangloff, Jan HulaLogical ReasoningCompositional Generalization

    University of Ostrava

  4. Learning Size Independent Constraint Models from Input Data and Positive and Negative Example Solutions

    Oct 9, 2026Helmut SimonisConstraint ProgrammingConstraint Satisfaction

    School of Computer Science and Information Technology, University College Cork, Ireland

  5. AdaC-GRPO: Towards Mastering Long-Horizon Visual Sudoku Puzzles via Adaptive Curriculum Learning

    Oct 9, 2026Sida Li, Yuanxin Liu, Linli Yao +4VLM ReasoningRL for VLMs

    National Key Laboratory for Multimedia Information Processing, Peking University · Huawei Technologies Co., Ltd.

  6. VIGOR: Verifiable Industrial Geometry Optimization and Repair in Scene Programs

    Oct 9, 2026Fuqiang Wang, Zheng Guo, Xiaoming Wu +53D Scene Layout GenerationLLM-Based Program Synthesis

    Qilu University of Technology, Jinan, China · Tianjin University, Tianjin, China · Shandong University, Jinan, China +3

  7. GAGR-Lab: Evaluating Joint Spatial-Geometric and Analytic Function Reasoning

    Oct 7, 2026Jingyao Zhang, Yun Li, Lu HanSpatial Reasoning BenchmarksMathematical Reasoning

  8. When Verifiable Counts Depend on Wording: Auditing Wording Robustness in Instruction Following

    Oct 4, 2026Qishi Zhan, Seoyeon Jang, Zihan Dong +3LLM EvaluationInstruction Following

    Marquette University · University of California, San Diego · Georgia Tech +3

  9. Only Project Once: Projection-Adaptive Loss for Exact Constraint Satisfaction

    Oct 3, 2026Tim Aebersold, Soheyl Massoudi, Mark FugeConstraint SatisfactionConstrained Optimization

    ETH Zürich

  10. Blackboard Intelligence Can Surpass Autoregressive on Globally Constrained Problems

    Sep 30, 2026Woosang Jeon, Jaeyeon Kim, Sham Kakade +6Inference-Time SearchCombinatorial Optimization

    Seoul National University · Harvard University · University of Central Florida

  11. Not Too Hard, Not Too Easy: Learning from Intermediate States for LLM Structured Reasoning

    Sep 27, 2026Hongbo Chen, Guohua Lu, Ting Dang +1Structured Reasoning in Language ModelsSelf-Training for Language Models

    University of Auckland, Auckland, New Zealand · University of Melbourne, Melbourne, Australia

  12. Ontology-Mediated Neurosymbolic Constraint Acquisition from Multiple Stakeholders

    Sep 24, 2026Stefan Bischof, Juliana Kainz, Danilo ValerioOntology-Based ReasoningNeuro-Symbolic Reasoning

    Siemens AG Österreich, Vienna, Austria

  13. A State-Space Model of Figured-Bass Realization: Local Constraints, Coupled Voices, and Polynomial-Time Solvability

    Sep 16, 2026Evan Unit LimSymbolic Music GenerationConstrained Optimization

    National Taiwan Normal University

  14. A property-registry contract for retrieve-or-refuse thermal-mechanical lattice search

    Sep 13, 2026Shaoliang Yang, Henry Chu, Zu Yashengjiang +1Constraint SatisfactionComputational Materials Science

    Department of Mechanical Engineering, Santa Clara University, Santa Clara, CA 95053, USA. · Santa Clara University, Santa Clara, CA 95053, USA.

  15. Signed p-adic Residual Encodings of Finite-Domain All-Different Systems with a Sudoku Case Study

    Sep 13, 2026Greg BakerConstraint SatisfactionSign-Based Optimization

    School of Computing, Australian National University Canberra, Australia

  16. Graph-Based Inference for Feedback-Driven Word Deduction: A Scalable Framework for the Jotto Problem

    Sep 8, 2026Dakshi Arora, Prakhar Kumar Srivastava, Ranjib BanerjeeConstraint PropagationConstraint Satisfaction

  17. Diffusion as a Training Curriculum for Timestep-Free Iterative Reasoning

    Sep 1, 2026Mariia Drozdova, Aidan Sirbu, Pietro Miotti +4Constraint SatisfactionAlgorithmic Reasoning

    Google, Paradigms of Intelligence Team · University of Geneva · School of Computer Science, McGill University +4

  18. Class-Based Heuristic Selection for Solving the Flying Block Puzzle

    Aug 20, 2026Sanyar Ahmadi, Pedram Asadzadeh, Amanj KhorramianTree SearchConstraint Satisfaction

    Faculty of Computer Engineering University of Tehran Tehran, Iran · Faculty of Computer Engineering K. N. Toosi University of Technology Tehran, Iran · Department of Electrical and Computer Engineering University of Kurdistan Sanandaj, Iran

  19. Formal Verification of Romanov's Triplet Logic: A Verified Filter for Sliding-window 3-CNF with Application to Structured Formulas

    Aug 19, 2026Dmitry V. AlexandrovConstraint SatisfactionBoolean Satisfiability

    HSE University, Moscow, Russia.

  20. Synthesizing Feature Extractors: An Agentic Approach for Algorithm Selection

    Aug 17, 2026Hai Xia, Carlos Ansótegui, Stefan SzeiderAlgorithm SelectionAutomated Feature Engineering

    Algorithms and Complexity Group, TU Wien, Vienna, Austria · Logic & Optimization Group, University of Lleida, Lleida, Spain

  21. Translating finite-domain integer constraint models to CP/SMT/ILP/PB/SAT solvers with CPMpy

    Aug 15, 2026Tias Guns, Ignace Bleukx, Hendrik Bierlee +8Constraint ProgrammingConstraint Satisfaction

    KU Leuven, Belgium · Nonfiction Software, Belgium · Flanders Make, Belgium +2

  22. From Errors to Proofs: Minimal-Core-Guided Repair for Neuro-Symbolic Constraint Solving

    Aug 14, 2026Dipankar SarkarNeuro-Symbolic ReasoningLLM-Based Program Synthesis

    Independent Researcher

  23. Large Language Models Can Follow Instructions, But Not Many at Once: Phase Transitions in Compositional Constraint Satisfaction

    Aug 12, 2026Mariya I. VasilevaLLM EvaluationInstruction Following

    Work done while at Meta Superintelligence Labs.

  24. Enhanced Filtering Algorithms for the Euclidean Traveling Salesperson Problem and its variants in Constraint Logic Programming

    Aug 11, 2026Alessandro Bertagnon, Marco GavanelliTraveling Salesperson ProblemConstraint Propagation

    Department of Environmental and Prevention Sciences, University of Ferrara, Italy · Department of Engineering, University of Ferrara, Italy

  25. UNSPECIFIC: General Constraint Synthesis for Breaking Copy-and-Paste Shortcut in LLM Instruction Following

    Aug 10, 2026Jeet Sharma, Balpreet Kaur, Jeremiah Hong +2Instruction FollowingConstraint Satisfaction

    University of Massachusetts, Amherst, USA

  26. ComplexityWorld: Benchmarking Vision-Language Models on Verifiable Visual Decision Making

    Aug 5, 2026Ningxin Pan, Hanyu Li, Yehui TangVLM EvaluationVisually Grounded Reasoning

    Peking University, Beijing, China.

  27. SCHEDBench: A Benchmark for Evaluating LLM Constraint Faithfulness in Natural-Language Combinatorial Scheduling

    Aug 2, 2026Shrenil Shaun Sharma, Avi SharmaCombinatorial OptimizationLLM Reliability

    Department of Electrical Engineering and Computer Sciences University of California, Berkeley

  28. When Do Learned Diffusion Proposals Help Constraint Solving? A Controlled Study on Continuous Algebraic Systems

    Jul 29, 2026Quang Bui, Sparsh Roy, Akash Gundimeda +1Graph Neural NetworksDiffusion Sampling

    1SAID Lab · 2American International School Vienna · 3Hopewell Valley Central High School +2

  29. Maximum Satisfiability of Simple Temporal Problems

    Jul 26, 2026Johannes K. Fichte, Johanna Groven, Peter Jonsson +2Temporal ReasoningParameterized Complexity

    Department of Computer and Information Science (IDA) Linköping University

  30. SymStep: Symbolic Step Verification for Logical Reasoning

    Jul 25, 2026Aida Usmanova, Rui Gao, Dilshod Azizov +2Constraint PropagationSymbolic Reasoning

    Leuphana University of Lüneburg · Mohamed bin Zayed University of Artificial Intelligence