Systems and methods for solving nogood databases involve generating a
representation comprising a plurality of contexted disjunctions,
conjoining all of the contented disjunctions to form a conjunction of
contexted disjunctions, and storing the representation as the conjunction
of contexted disjunctions. Nogoods are eliminated by refining the
representation until a result of the conjunction of contexted
disjunctions is backtrack-free or the result of the conjunction of
contexted disjunctions reduces to false. In various embodiments, the
refining is carried out without reordering the disjunctions and/or
without merging the disjunctions. In various embodiments, the systems and
methods are used for various constraint satisfaction problems, such as
syntactic processing of natural language sentences, map coloring,
understanding line drawings, electronic circuit analysis, and truth
maintenance systems.