Domain generating functions for solving constraint satisfaction problems

Abstract

This paper presents an application of functional programming: searching a domain for elements which satisfy certain constraints. We give a very general formulation of the problem and describe ‘generate and test’, ‘backtracking’ and ‘forward checking’ algorithms. We then introduce the concept of domain generating functions to capture a common optimization during the search process: using partial solutions to reduce the size of the search space. We compare the efficiency of the original algorithms and those using domain generating functions first with the ‘classical’ n-queens example, and then with a problem having larger domains to search which was inspired by an application in macromolecular structure determination. Using algorithms coded in Miranda, Haskell and Common Lisp, we show that a high order (lazy) functional language is a useful and efficient tool for prototyping search methods in large complex domains.