From Backtracking To Deep Learning: A Survey On Methods For Solving Constraint Satisfaction Problems

Abstract

Constraint Satisfaction Problems (CSP) are a fundamental mechanism in artificial intelligence, but finding a solution is an NP-complete problem, requiring the exploration of a vast number of combinations to satisfy all constraints. To address this, extensive research has been conducted, leading to the development of effective techniques and algorithms for different types of CSPs, ranging from exhaustive search methods, which explore the entire search space, to modern techniques that use deep learning to learn how to solve CSPs. This paper represents a descriptive and synthetic overview of various CSPs solving methods, organized by approach: systematic search methods, inference and filtering methods, structural decomposition methods, local search-based methods, and deep learning-based methods. By offering this structured classification, it presents a clear view of resolution strategies, from the oldest to the most recent, highlighting current trends and future challenges, there by facilitating the understanding and application of available approaches in the field.