---
title: "A New Method for Solving Constraint Satisfaction Problems"
authors:
  - "Raimund Seidel"
doi: ""
url: "https://ijcai.org/proceedings/1981/66"
pdf: "https://ijcai.org/proceedings/1981/0066.pdf"
venue: "Proceedings of the Seventh International Joint Conference on Artificial Intelligence"
year: 1981
pages: "338-341"
track: "INFERENCE and REASONING"
keywords:
---

# A New Method for Solving Constraint Satisfaction Problems

Raimund Seidel

*Proceedings of the Seventh International Joint Conference on Artificial Intelligence*, pages 338-341.

## Abstract

This paper deals with the combinatorial search problem of finding values for a set of variables subject to a set of constraints. This problem is referred to as a constraint satisfaction problem. We present an algorithm for finding all the solutions of a constraint satisfaction problem with worst case time bound O(m*kf+l) and space bound O(n*kf+1 ), where n is the number of variables in the problem, m the number of constraints, k the cardinality of the domain of the variables, and f <n an integer depending only on a graph which is associated with the problem. It will be shown that for planar graphs and graphs of fixed genus this f is O( / nJ.