Problema de satisfacción de restricciones

Problemas de satisfacción de restricciones (CSP) por sus siglas en inglés, son problemas matemáticos definido como un conjunto de objetos tal que su estado debe satisfacer un número de restricciones o limitaciones. Los CSP representa las entidades de un problema como una colección homogénea finita de restricciones sobre variables, las que son resueltas por métodos de satisfacción de restricciones. Los CSP son el tema de una intensa investigación en Inteligencia Artificial e Investigación de operaciones, dado que la generalidad en su formulación provee un principio básico para analizar y resolver problemas de distintos tipos. Los CSP a menudo muestran gran complejidad, requiriendo una combinación de métodos heurísticos y búsqueda combinatoria para ser resueltos en un tiempo razonable. El Problema de satisfacibilidad booleana (SAT), el Satisfiability Modulo Theories (SMT) y answer set programming (ASP) pueden ser a grandes rasgos modelados como una forma de problema de satisfacción de restricciones.Ejemplos de problemas sencillos que pueden ser modelados como problema de satisfacción de restricciones. Problema de las ocho reinas Teorema de los cuatro colores Problema de coloración de mapas Sudoku, Futoshiki, Kakuro (Cross Sums), Numbrix, Hidato y muchos otros puzzlesDe forma general, problemas de restricciones pueden ser más difíciles, y pueden no ser expresables en alguno de estos sistemas simples.Ejemplos de la vida real son Planeamiento y Asignación de recursos.