Metraipolis › archive › dc_26c58ea53120

Constraint satisfaction — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/Constraint_satisfaction
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-07T16:30:40.397Z
SHA-256 of the archived text
daf7b85fbf50c2ff8e6a9320c95e007354a6a6c3934c3765bf19f007ab719669
Stable URL of this page
https://metraipolis.com/documento/dc_26c58ea53120

How to cite

Constraint satisfaction — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Constraint_satisfaction (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_26c58ea53120 (Metraipolis archive dc_26c58ea53120, sha256 daf7b85fbf50c2ff8e6a9320c95e007354a6a6c3934c3765bf19f007ab719669)
BibTeX
@misc{dc26c58ea53120,
  title = {Constraint satisfaction — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Constraint_satisfaction},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_26c58ea53120; sha256 daf7b85fbf50c2ff8e6a9320c95e007354a6a6c3934c3765bf19f007ab719669},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Constraint_satisfaction. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In artificial intelligence and operations research, constraint satisfaction is the process of finding a solution through a set of constraints that impose conditions that the variables must satisfy. A solution is therefore an assignment of values to the variables that satisfies all constraints—that is, a point in the feasible region. The techniques used in constraint satisfaction depend on the kind of constraints being considered. Often used are constraints on a finite domain, to the point that constraint satisfaction problems are typically identified with problems based on constraints on a finite domain. Such problems are usually solved via search, in particular a form of backtracking or local search. Constraint propagation is another family of methods used on such problems; most of them are incomplete in general, that is, they may solve the problem or prove it unsatisfiable, but not always. Constraint propagation methods are also used in conjunction with search to make a given problem simpler to solve. Other considered kinds of constraints are on real or rational numbers; solving problems on these constraints is done via variable elimination or the simplex algorithm. Constraint satisfaction as a general problem originated in the field of artificial intelligence in the 1970s (see for example (Laurière 1978)). However, when the constraints are expressed as multivariate linear equations defining (in)equalities, the field goes back to Joseph Fourier in the 19th century: George Dantzig's invention of the simplex algorithm for linear programming (a special case of mathematical optimization) in 1946 has allowed determining feasible solutions to problems containing hundreds of variables. During the 1980s and 1990s, embedding of constraints into a programming language was developed. The first language devised expressly with intrinsic support for constraint programming was Prolog. Since then, constraint-programming libraries have become available in other languages, such as C++ or Java (e.g., Choco for Java).

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «mathematical optimization»).
Fonte: Wikipedia in inglese, voce «Constraint satisfaction» — https://en.wikipedia.org/wiki/Constraint_satisfaction
Wikidata Q30158686 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q30158686
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Constraint_satisfaction?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1312249316, consultata il 2026-10-07T15:59:12.195Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 4c83d06cfdafc14511fd829d6823a75cd9a0a1e9d3b21f6562b023701b7bf242