Principles Of Constraint Programming

Principles of Constraint Programming Krzysztof R. Apt CWI, Amsterdam, The Netherlands Cambridge, New York, Melbourne, Madrid, Cape Town, Singapore, São Paulo Cambridge University Press The Edinburgh Building, Cambridge , United Kingdom Published in the United States of America by Cambridge University Press, New York www.cambridge.org Information on this title: www.cambridge.org/9780521825832 © Cambridge University Press 2003 This book is in copyright. Subject to statutory exception and to the provision of relevant collective licensing agreements, no reproduction of any part may take place without the written permission of Cambridge University Press. First published in print format 2003 - isbn-13 978-0-511-06249-0 eBook (NetLibrary) - isbn-10 0-511-06249-4 eBook (NetLibrary) - isbn-13 978-0-521-82583-2 hardback - isbn-10 0-521-82583-0 hardback Cambridge University Press has no responsibility for the persistence or accuracy of s for external or third-party internet websites referred to in this book, and does not guarantee that any content on such websites is, or will remain, accurate or appropriate. To Alma and Daniel Contents Acknowledgements page xi 1 1.1 1.2 1.3 1.4 1.5 Introduction Basic characteristics of constraint programming Applications of constraint programming A very short history of the subject Our approach Organisation of the book 2 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 2.10 Constraint satisfaction problems: examples Basic concepts Constraint satisfaction problems on integers Constraint satisfaction problems on reals Boolean constraint satisfaction problems Symbolic constraint sa