---
title: "Extracting Constraint Satisfaction Subproblems"
authors:
  - "Eugene C. Freuder"
  - "Paul D. Hubbe"
doi: ""
url: "https://ijcai.org/proceedings/1995/72"
pdf: "https://ijcai.org/proceedings/1995/0072.pdf"
venue: "Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence"
year: 1995
pages: "548-556"
track: "Constraint Satisfaction"
keywords:
---

# Extracting Constraint Satisfaction Subproblems

Eugene C. Freuder, Paul D. Hubbe

*Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence*, pages 548-556.

## Abstract

Given a subproblem, S, of a constraint satisfaction problem, we can decompose the problem into a set of disjoint subproblems one of which will be S. This decomposition permits exploitation of problem-specific metaknowledge, a priori or acquired knowledge, about S. If we know that S is unsolvable, for example, the decomposition permits us to extract and then discard S, restricting the search for a solution to the remaining subproblems. A variety of potential uses for the decomposition method are discussed. A specific method that dynamically discards failed subproblems during forward checking search is described, and its utility demonstrated experimentally.