Contents

Foreword

Introduction

I Constraint satisfaction problems

1 What are constraint satisfaction problems?

2 Two examples

II Methods for solving constraint satisfaction problems

3 Solving steps and solving strategies

4 Problems over finite domains

4.1 Reduction algorithms

4.1.1 Consistency algorithms

4.1.1.1 Degree of consistency

4.1.1.2 Directed consistency

4.1.2 Substitution algorithms

4.2 Search algorithms

4.2.1 Backtracking

4.2.2 Algorithms with memory

4.2.3 Variable and domain ordering

4.2.3.1 Variable ordering

4.2.3.2 Domain ordering

4.3 Combined algorithms

4.3.1 Checking future variables against actual

4.3.2 Mutual checking of future variables

4.4 Transformation algorithms

III Constraint logic programming

5 Basic principles

5.1 Constraint domains of CLP languages

5.2 Syntax and semantics

5.3 Basic technologies for CLP implementation

6 ECLiPSe language

6.1 Finite domains

6.1.1 Schema for solving problems over finite domains

6.1.2 Optimisation

6.2 Infinite domains

6.2.1 Schema for solving problems over infinite domains

IV Solved examples of constraint satisfaction problems

7 Problems over finite domains

7.1 A few simple problems

7.2 Investment problem

7.3 Planning

7.4 Warehouse location problem

8 Problems over infinite domains

8.1 Blending problem

8.2 Financial planning

Appendixes

Mathematical symbols

Slovak-English dictionary

List of algorithms

Built-in constraints in ECLiPSe

References

Index