---

Constraint Solving and Planning with Picat

1 An Overview of Picat . 1
1.1 Introduction . 1
1.1.1 Running Picat . 2
1.2 Data Types and Operators . 3
1.2.1 Terms, Variables, and Values . 4
1.2.2 Primitive Values . 5
1.2.3 Compound Terms . 5
1.2.4 Equality Testing and Unification . 9
1.2.5 I/O and Modules . 10
1.3 Control Flow and Goals . 10
1.3.1 Goals . 10
1.3.2 If-Then-Else . 11
1.3.3 The Assignment Operator . 12
1.3.4 Foreach Loops . 13
1.4 Predicates and Functions . 14
1.4.1 Predicates . 15
1.4.2 Predicate Facts . 17
1.4.3 Functions and Function Facts . 19
1.4.4 Introduction to Tabling . 20
1.5 Picat Compared to Other Languages . 20
1.5.1 Picat vs. Prolog . 20
1.5.2 Picat vs. Haskell . 22
1.5.3 Picat vs. Python . 24
1.6 Writing Efficient Programs in Picat . 25
1.6.1 Making Definitions and Calls Deterministic . 25
1.6.2 Making Definitions Tail-Recursive . 26
1.6.3 Incremental Instantiation and Difference Lists . 26
1.6.4 Writing Efficient Iterators . 27
1.7 Bibliographical Note . 28
1.8 Exercises . 29

2 Basic Constraint Modeling . 31
2.1 Introduction . 31
2.2 SEND+MORE=MONEY . 32
2.3 Sudoku— Constraint Propagation . 34
2.3.1 A Sudoku Program . 34
2.3.2 Constraint Propagation— Concepts . 34
2.3.3 Constraint Propagation— Example . 36
2.4 Minesweeper— Using SAT. 37
2.5 Diet— Mathematical Modeling with the mip Module . 39
2.6 The Coins Grid Problem: Comparing MIP with CP/SAT . 41
2.7 N-Queens— Different Modeling Approaches . 43
2.8 Bibliographical Note . 46
2.9 Exercises . 46

3 Advanced Constraint Modeling . 49
3.1 Advanced Constraint Modeling . 49
3.2 The element Constraint and Langford’s Number Problem . 50
3.2.1 Langford’s Number Problem . 51
3.3 Reification . 53
3.3.1 Example of Reification: all different except 0 . 54
3.3.2 Reification— Who Killed Agatha . 54
3.4 Domains: As Small as Possible (but Not Smaller) . 55
3.5 Search and Search Strategies (cp Module) . 58
3.5.1 Magic Squares— Systematically Testing All Labelings . 59
3.6 Scheduling— the cumulative Constraint . 61
3.7 Magic Sequence — global cardinality/2 and the Order of Constraints .  . 64
3.8 Circuit— Knight’s Tour Problem . 66
3.9 The regular Constraint—Global Contiguity and Nurse Rostering 69
3.9.1 global contiguity . 70
3.9.2 Nurse Rostering . 71
3.9.3 Alternative Approach for Valid Schedules: Table Constraint 72
3.10 Debugging Constraint Models . 73
3.11 Bibliographical Note . 76
3.12 Exercises . 76

4 Dynamic Programming with Tabling . 79
4.1 Introduction . 79
4.2 Tabling in Picat . 80
4.3 The Shortest Path Problem . 82
4.4 The Knapsack Problem . 83
4.5 The N-Eggs Problem . 84
4.6 Edit Distance . 85
4.7 The Longest Increasing Subsequence Problem . 86
4.8 Tower of Hanoi . 87
4.9 The Twelve-Coin Problem . 90
4.10 Bibliographical Note . 92
4.11 Exercises . 92

5 From Dynamic Programming to Planning . 95
5.1 Introduction . 95
5.2 The planner Module: Depth-Unbounded Search . 96
5.3 The Implementation of Depth-Unbounded Search . 98
5.4 Missionaries and Cannibals . 98
5.5 Klotski . 99
5.6 Sokoban . 102
5.7 Bibliographical Note . 106
5.8 Exercises . 106

6 Planning with Resource-Bounded Search . 109
6.1 Introduction . 109
6.2 The planner Module: Resource-Bounded Search . 110
6.3 The Implementation of Resource-Bounded Search . 111
6.4 The Deadfish Problem . 112
6.5 The 15-Puzzle . 113
6.6 Blocks World . 115
6.7 Logistics Planning . 117
6.8 Bibliographical Note . 119
6.9 Exercises . 120

7 Encodings for the Traveling Salesman Problem . 123
7.1 Introduction . 123
7.2 An Encoding for CP . 124
7.3 An Encoding for SAT . 126
7.4 An Encoding for MIP . 128
7.5 An Encoding for the Tabled Planner . 129
7.6 Experimental Results . 131
7.7 Bibliographical Note . 132

References . 133
Index . . 137

© www.picat-lang.org