For easy reference, here are the links to
My Picat page and to my GitHub repo
/picat.
Picat is a new programming language created by NengFa Zhou and Jonathan Fruhman. The specification was published in December 2012. The first official (beta) release was in May 2013. Right from the beginning I liked this language and in this blog post I hope to show why. I should also say that the code shown here are not just for Constraint Programming, but also traditional backtracking (a la Prolog), tabling (memoization), imperative constructs etc, i.e. what makes Picat Picat.
The name
Picat is an acronym and is explained in the quote below, borrowed from the
Picat site:
Picat is a generalpurpose language that incorporates features from logic programming, functional programming, and scripting languages. The letters in the name summarize Picat's features:
 Patternmatching: A predicate defines a relation, and can have zero, one, or multiple answers. A function is a special kind of a predicate that always succeeds with one answer. Picat is a rulebased language. Predicates and functions are defined with patternmatching rules.
 Imperative: Picat provides assignment and loop statements for programming everyday things. An assignable variable mimics multiple logic variables, each of which holds a value at a different stage of computation. Assignments are useful for computing aggregates and are used with the foreach loop for implementing list comprehensions.
 Constraints: Picat supports constraint programming. Given a set of variables, each of which has a domain of possible values, and a set of constraints that limit the acceptable set of assignments of values to variables, the goal is to find an assignment of values to the variables that satisfies all of the constraints. The Picat system provides modules for different solvers with the same interface.
 Actors: Actors are eventdriven calls. Picat provides action rules for describing eventdriven behaviors of actors. Events are posted through channels. An actor can be attached to a channel in order to watch and to process its events. In the future, Picat will treat threads as channels, and allow the use of action rules to program concurrent threads.
 Tabling: Tabling can be used to store the results of certain calculations in memory, allowing the program to do a quick table lookup instead of repeatedly calculating a value. As computer memory grows, tabling is becoming increasingly important for offering dynamic programming solutions for many problems such as planning problems.
Of these general features, I have mostly tested patternmatching, imperative programming constructs, constraints (of course!) and tabling, but have not played much with actors directly and will not mention them much here.
Some general Picat links:
Let's start with some simple examples to show these features.
Constraints
First we show how to use
constraints with
send_more_money.pi, and we clearly see the influences of Prolog:
import cp.
sendmore(Digits) =>
Digits = [S,E,N,D,M,O,R,Y],
Digits in 0..9,
all_different(Digits),
S #> 0,
M #> 0,
1000*S + 100*E + 10*N + D
+ 1000*M + 100*O + 10*R + E
#= 10000*M + 1000*O + 100*N + 10*E + Y,
solve(Digits).
Except for the
=>
it looks very much like Prolog, right? I explain the
=>
and how it's different from Prolog's
:
later on and will also mention some other similarities/differences from/with Prolog.
Another mandatory example is
sudoku.pi where we see more differences between traditional Prolog, i.e. the
foreach
loop:
import cp.
import util.
go =>
time2(sudoku(1)).
sudoku(ProblemName) =>
problem(ProblemName, Board),
print_board(Board),
sudoku(3, Board),
print_board(Board).
sudoku(N, Board) =>
N2 = N*N,
Vars = array_matrix_to_list(Board),
Vars in 1..N2,
foreach(Row in Board) all_different(Row) end,
foreach(Column in transpose(Board)) all_different(Column) end.
foreach(I in 1..N..N2, J in 1..N..N2)
all_different([Board[I+K,J+L] : K in 0..N1, L in 0..N1])
end,
solve([ff,down], Vars).
print_board(Board) =>
N = Board.length,
foreach(I in 1..N)
foreach(J in 1..N)
X = Board[I,J],
if var(X) then printf(" _") else printf(" %w", X) end
end,
nl
end,
nl.
problem(1, Data) =>
Data = [
[_, _, 2, _, _, 5, _, 7, 9],
[1, _, 5, _, _, 3, _, _, _],
[_, _, _, _, _, _, 6, _, _],
[_, 1, _, 4, _, _, 9, _, _],
[_, 9, _, _, _, _, _, 8, _],
[_, _, 4, _, _, 9, _, 1, _],
[_, _, 9, _, _, _, _, _, _],
[_, _, _, 1, _, _, 3, _, 6],
[6, 8, _, 3, _, _, 4, _, _]].
What I have
understood, these loops constructs was one of the reasons that NengFa Zhou wanted to created a new language, since he wasn't satisfied with the
foreach
loops he implemented in
BProlog. [You can compare many of my Picat models/programs with the one I implemented in BProlog earlier this year. See my
BProlog page, e.g.
sudoku.pl.] One thing that differs between Picat's
foreach loops compared to BProlog's (as well as ECLiPSe's and SICStus Prolog's) is that the user don't have to explicitly declare the local (or global) variables which makes it simpler to use and read.
I will describe more CP in Picat below, but first I will describe some other Picat features.
Tabling
Tabling here refers to
memoization ("caching the results"). A simple example of tabling is to start with this the standard recursive definition of a Fibonacci number:
table
fibt(0)=1.
fibt(1)=1.
fibt(N)=F,N>1 => F=fibt(N1)+fibt(N2).
This is normally very slow for larger numbers because of the massive number of recursive steps needed. Using the
table
declaration before the predicate will automatically
cache the calculated values and is used in subsequent calls.
An example of it's use is in
euler2.pi (Project Euler #2), where the object is to find the sum of all evenvalued terms in the sequence which do not exceed four million. Here is one way of implementing this, using
list comprehension:q
euler2 =>
writeln(sum([F : N in 1..100, F = fibt(N), F < 4000000, F mod 2 =:= 0])).
Finding this sum takes 0.015s (with the overload of starting Picat etc). If we don't table the values then it's much (much!) slower:
fibt(100)
is 573147844013817084101 (~5.73e+20), which is about the number of recursions steps needed. By the way, here we see that Picat supports
big integers as well.
Please note that tabling might in some cases be slower because of the memory overhead involved, so you have to be careful and test it.
Another example of tabling is for
dynamic programming, for example calculating the edit distance. This example is from Picat's
picatlang.org/download/exs.pi:
% computing the minimal editing distance
% of two given lists
table(+,+,min)
edit([],[],D) => D=0.
edit([XXs],[XYs],D) => % copy
edit(Xs,Ys,D).
edit(Xs,[_YYs],D) ?=> % insert
edit(Xs,Ys,D1),
D=D1+1.
edit([_XXs],Ys,D) => % delete
edit(Xs,Ys,D1),
D=D1+1.
Another example is shortest distance (also from
exs.pi):
% modedirected tabling
% finding shortest paths on a graph given by the relation edge/3.
table(+,+,,min)
sp(X,Y,Path,W) ?=>
Path=[(X,Y)],
edge(X,Y,W).
sp(X,Y,Path,W) =>
Path=[(X,Z)PathR],
edge(X,Z,W1),
sp(Z,Y,PathR,W2),
W=W1+W2.
index(+,,) (+,+,)
edge(1,2,1).
edge(1,3,2).
edge(2,3,3).
edge(3,2,4).
Imperative programming
Regarding loops, we have already seen the
foreach
loop in the Sudoku example. Picat has more imperative programming constructs:
while
loops and assignments.
The Fibonacci example shown above (Project Euler #2, using the list comprehension) has the drawback of a hard coded limit that checks all
N
in the range 1..100; this range was found by some experimentation and it's not the smallest range. In Picat it's also possible to use a
while
loop for this (though not as nice looking as the list comprehension version). This is traditional
imperative programming. It also shows an example of
(re)assignments using the
:=
operator:
euler2b =>
I = 1,
Sum = I,
F = fibt(I),
while (F < 4000000)
if F mod 2 == 0 then
Sum := Sum + F
end,
I := I + 1,
F := fibt(I)
end,
writeln(Sum).
This version also calculates the solution in 0.015s.
More Constraint Programming
Here are some more examples of CP in Picat.
Element constraint
In Picat, as in BProlog (and in many other CP systems), the
element
constraint (
List[Ith]=Value
) has to be written explicitly using the predicate
element(Ith, List, Value)
when
Ith
is a
decision variables. However, if
Ith
is a plain integer, in Picat it can be stated more naturally as
List[Ith] = Value
or
List[Ith] #= Value
if
List
is a list of decision variables.
Older readers of this blog might remember that I sometimes whine how hard it is to write
matrix element in different CP systems, and this applies to Picat as well. For example, in
circuit.pi I would like to use this construct but it's
not allowed:
foreach(I in 2..N)
% this is not allowed
Z[I] = X[Z[I1]]
end
Instead, one have to rewrite it. Here's my version:
import cp.
% ...
foreach(I in 2..N)
Z1 #= Z[I1],
element(Z1,X,X2),
Z[I] #= X2
end,
In
stable_marriage.pi a more general version,
matrix_element
, is used:
matrix_element(X, I, J, Val) =>
element(I, X, Row),
element(J, Row, Val).
This version (using two
element
) can be very good sometimes, but depending on the type of the variables some of these variants might be used; sometimes I have to test them all. Also, they are never active at the same time, but deactivated by comments (as shown in the example):
import cp.
% ...
matrix_element(X, I, J, Val) =>
element(I, X, Row),
element(J, Row, Val).
% matrix_element(X, I, J, Val) =>
% nth(I, X, Row),
% element(J, Row, Val).
% matrix_element(X, I, J, Val) =>
% freeze(I, (nth(I, X, Row),freeze(J,nth(J,Row,Val)))).
% matrix_element(X, I, J, Val) =>
% freeze(I, (element(I, X, Row),freeze(J,element(J,Row,Val)))).
The
freeze(X, Call)
predicate delays the call to
Call
until
X
becomes a nonvariable term.
alldifferent_except_0
Picat supports reifications with the nice syntax I expect from a high level CP system. Note that
#/\
is "and" for FD variables. Here is the
alldifferent_except_0
constraint (see
alldifferent_except_0.pi for the full model):
import cp.
alldifferent_except_0(Xs) =>
foreach(I in 1..Xs.length, J in 1..I1)
(Xs[I] #!= 0 #/\ Xs[J] #!= 0) #=> (Xs[I] #!= Xs[J])
end.
Nqueens
Below are some different implementations of Nqueens, taken from
nqueens.pi.
import cp.
queens3(N, Q) =>
Q=new_list(N),
Q in 1..N,
all_different(Q),
all_different([$Q[I]I : I in 1..N]),
all_different([$Q[I]+I : I in 1..N]),
solve([ff],Q).
% Using all_distinct instead
queens3b(N, Q) =>
Q=new_list(N),
Q in 1..N,
all_distinct(Q),
all_distinct([$Q[I]I : I in 1..N]),
all_distinct([$Q[I]+I : I in 1..N]),
solve([ff],Q).
queens4(N, Q) =>
Q = new_list(N),
Q in 1..N,
foreach(A in [1,0,1])
all_different([$Q[I]+I*A : I in 1..N])
end,
solve([ff],Q).
Note that in
queens3
we have to use
$Q[I]I
(i.e. prepended with a
$
) since since it's an expression that should be evaluated ("escaped").
Now we can do some benchmark on different variants (the model
nqueens.pi also includes some variants not shown here) with different
N
for some of the variants. This is merely to show a use of the meta predicates (
time2
,
once
, and
call
).
go3 =>
Ps = [queens3=1000, queens3b=1000, queens4=100,queens5=100, queens6=13],
foreach(P=N in Ps)
printf("%w(%d)\n", P, N),
time2(once(call(P,N,Q))),
writeln(Q),
nl
end.
queens3(1000)
takes 4s and 2 backtracks,
queens3b
takes 9.9s and 0 backtracks. Not extremely fast, but quite good.
While we're at it, here is one way of benchmarking the time and number of backtracks for one of the methods (predicate
queen3_all
in
nqueens.pi) for getting
all the solutions for N from 2 to 14.
statistics/2
is used to get the number of backtracks and run time for each run:
go2 =>
foreach(N in 2..14)
statistics(backtracks, Backtracks),
statistics(runtime, [_, _Runtime1]),
queens3_all(N, Solutions),
Len=Solutions.length,
statistics(backtracks, Backtracks2),
B = Backtracks2  Backtracks,
Backtracks := Backtracks2,
statistics(runtime, [_, Runtime2]),
writef("N:%3d %10d solutions (%d backtracks, %d millis)\n", N, Len, B, Runtime2)
end.
The result:
N: 2 0 solutions (1 backtracks, 0 millis)
N: 3 0 solutions (2 backtracks,k 0 millis)
N: 4 2 solutions (5 backtracks, 0 millis)
N: 5 10 solutions (13 backtracks, 0 millis)
N: 6 4 solutions (39 backtracks, 0 millis)
N: 7 40 solutions (107 backtracks, 0 millis)
N: 8 92 solutions (383 backtracks, 0 millis)
N: 9 352 solutions (1477 backtracks, 4 millis)
N: 10 724 solutions (5715 backtracks, 4 millis)
N: 11 2680 solutions (24475 backtracks, 48 millis)
N: 12 14200 solutions (116081 backtracks, 232 millis)
N: 13 73712 solutions (588949 backtracks, 1340 millis)
N: 14 365596 solutions (3195965 backtracks, 7472 millis)
Magic square
This is a magic squares implementation in Picat, taken from
magic_square.pi. One thing to notice is the use of
rows()
,
columns()
,
diagonal1()
, and
diagonal2()
from the
util
module.
import cp.
import utils.
magic2(N,Square) =>
writef("\n\nN: %d\n", N),
NN = N*N,
Sum = N*(NN+1)//2,% magical sum
writef("Sum = %d\n", Sum),
Square = new_array(N,N),
Square in 1..NN,
all_different(Square),
foreach(Row in Square.rows()) Sum #= sum(Rows) end,
foreach(Column in Square.columns()) Sum #= sum(Column) end,
% diagonal sums
Sum #= sum(Square.diagonal1()),
Sum #= sum(Square.diagonal2()),
% Symmetry breaking
Square[1,1] #< Square[1,N],
Square[1,1] #< Square[N,N],
Square[1,1] #< Square[N,1],
Square[1,N] #< Square[N,1],
solve([ffd,updown],Square),
print_square(Square).
Magic sequence
Another standard CP problem is
magic_sequence.pi:
import cp.
magic_sequence(N, Sequence) =>
writef("\n%d: ",N),
Sequence = new_list(N),
Sequence in 0..N1,
foreach(I in 0..N1) count(I,Sequence,#=,Sequence[I+1]) end,
N #= sum(Sequence),
Integers = [ I : I in 0..N1],
N = scalar_product(Integers, Sequence),
solve([ff], Sequence).
scalar_product(A, X) = Product =>
Product #= sum([S : I in 1..A.length, S #= A[I]*X[I]]).
Note that I tend to use
count(Var, Vars, Relation, N)
instead of the builtin
global_cardinality(List, Pairs)
since it's more natural for me.
Least diff problem, optimization
The Least diff problem is a simple optimization problem in Picat: Minimize the difference between
ABCDEFGHIJ
where the letters A..J are distinct integers (in the domain 0..9).
import cp.
least_diff(L,Diff) =>
L = [A,B,C,D,E, F,G,H,I,J],
L in 0..9,
all_different(L),
X #= 10000*A + 1000*B + 100*C + 10*D + E,
Y #= 10000*F + 1000*G + 100*H + 10*I + J,
Diff #= X  Y,
Diff #> 0,
solve([$min(Diff)], L).
The interesting part is the objective
$min(Diff)
(note the "$") which defines the objective value.
For more advanced models one can use the
$report(Goal)
to show the progress of the objective. Here is an example from
einav_puzzle.pi:
solve($[min(TotalSum), report(printf("Found %d\n", TotalSum)), ffd],Vars),
Without
report(Goal)
the solution is only shown after the solver has finished the search which may take considerable time.
Global constraint table
Picat has a
table
constraint: the
in
construct (
in
is also used to define the domain of a decision variables). Here is a simple example using table constraint:
traffic_lights.pi (CSPLib #16) which use the list
Allowed
to state which combinations are allowed.
import cp.
traffic_lights_table(V, P) =>
N = 4,
% allowed/1 as a table (translated)
Allowed = [(1,1,3,3),
(2,1,4,1),
(3,3,1,1),
(4,1,2,1)],
V = new_list(N),
V in 1..N,
P = new_list(N),
P in 1..N,
foreach(I in 1..N, J in 1..N)
JJ = (1+I) mod N,
if J #= JJ then
VI = V[I], PI = P[I],
VJ = V[J], PJ = P[J],
% Table constraint
(VI, PI, VJ, PJ) in Allowed
end
end,
Vars = V ++ P,
solve(Vars).
The use of
in
 as a
table
constraint  requires that the values are integers so we have to translate to/from integers in this version. The model (
traffic_lights.pi) also contain some other approaches of this problem that don't use the table constraint.
Another example of table constraint is
hidato.pi (though it's not very efficient).
Global constraints
Picat supports the most common global constraints as shown in the list below. See
Picat Guide, section 11.5 for details.

all_different(List)

all_distinct(List)

assignment(List)
(a.k.a. inverse
)

circuit(List)

count(Value,List,Rel,N)

cumulative(Starts,Durations,Resources, Limit)

diffn(RectangleList)

disjunctive_tasks(Tasks)

element(I,List, V)

global_cardinality(List, Pairs)
(I tend to use this not so much since it's not as natural as using count/4)

neqs(NegList)

serialized(Starts,Durations)

subcircuit(List)

in
used as the global constraint table
(not to be confused with tabling=
In the module
cp_utils.pi, I have also defined some other useful decompositions of global constraints:

matrix_element
(some different versions)

to_num

latin_square

increasing

decreasing

scalar_product
(with a relation)

alldifferent_except_0

nvalue

nvalues

global_cardinality(Array, GccList)

lex2
, lex2eq
, lex_less
, lex_lesseq
, lex_greater
, lex_greatereq
, lex_less2
(alternative hack)
Labeling: Most of the standard variable and value heuristics are supported, though I miss random variants. Some of the examples above show how to label the variables in the
solve
predicate. Here the
ff
is firstfail variable labeling, and
down
means that a variable is labeled from the largest value to the smallest.
solve([ff,down], Vars)
See the Picat Guide documentation for more description of the options to
solve
and other solver options.
Pattern matching
Pattern matching is Picat is more influenced by the pattern matching in functional programming than by Prolog's unification. This may confuse some programmers with a Prolog background.
Here is a definition of
quick sort which shows some of the pattern matching constructs of Picat, and also shows how to define functions, i.e. predicates with return value.
qsort([]) = L => L = [].
qsort([HT]) = L => L = qsort([E : E in T, E =< H]) ++ [H] ++
qsort([E : E in T, E > H]).
The two functions
drop
and
take
(standard in functional programming) can be defined as:
drop(Xs,0) = Xs.
drop([],_N) = [].
drop([_XXs],N) = drop(Xs,N1).
take(_Xs,0) = [].
take([],_N) = [].
take([XXs],N) = [X] ++ take(Xs,N1).
Reverse can be defined as:
reverse(L1,L2) => my_rev(L1,L2,[]).
my_rev([],L2,L3) => L2 = L3.
my_rev([XXs],L2,Acc) => my_rev(Xs,L2,[XAcc]).
As will be mentioned again below, the matching between different variables  or part of variables  is often done in the body and not in the rule part. Here is an example from
99_problems.pi showing that (the problem is "% P09 (**): Pack consecutive duplicates of list elements into sublists.")
% pack(L1,L2) : the list L2 is obtained from the list L1 by packing
% repeated occurrences of elements into separate sublists.
% (list,list) (+,?)
pack([],Y) => Y = [].
pack([XXs],[ZZs]) => transfer(X,Xs,Ys,Z), pack(Ys,Zs).
pack(X1,Z1) => X1=[XXs],Z1=[ZZs],transfer(X,Xs,Ys,Z), pack(Ys,Zs).
There are more comments about pattern matching below.
Nondeterminism and other Prolog influences (and differences)
Some of the examples above show clear influences from Prolog. Here we list some more influences (and differences).
Picat has  as Prolog has  support for nondeterminism using a
backtracking mechanisn to test different predicates as will be seen below. This is a really great feature in Picat and is one of the reason I like Picat so much. Or rather: it is the
combination of the backtracking possibility together with the imperative features, support for constraint programming etc that I really like in Picat.
member
The nondeterministic
member
predicate in Picat works as in Prolog, i.e. can be used both as a test for membership and also for generating all the elements:
Picat> member(2, [1,2,3])
yes
Picat> member(4, [1,2,3])
no
Picat> member(X, [1,2,3])
X=1;
X=2;
X=3;
no
As in Prolog we can get the next solution with a
;
(semicolon) in the Picat shell.
This double nature version of
member
can be defined in Picat as:
member(X,[Y_]) ?=> X=Y.
member(X,[_L]) => member(X,L)
In this definition we see two features of Picat:
 pattern matching: the pattern
[Y_]
matches any list and "extracts" the first elements Y
to be matched against X
in the first clause.
 backtracking: The first rule is defined as a backtrackable rule using
?=>
(the prepending "?" is the marker for backtrackable rules) and makes the call nondeterministic. The last rule in a definition should be stated as nonbacktrackable, i.e. =>
(without the ?
).
This predicate now works in the same way as the builtin
member/2
.
Predicate facts
Predicate facts are bodyless definitions akin to Prolog's "data definition" (but be careful to take this too literary).
Predicate facts are prepended by
index declararion to make them accessible as data (and this is one difference from Prolog). For example, here is a stripped down version of the transitive closure example
transitive_closure.pi (ported from BProlog program
transitiveRight.pl):
top ?=>
reach(X,Y),
writeln([X,Y]),
fail.
top => true.
% Transitive closure right
table
reach(X,Y) ?=> edge(X,Y).
reach(X,Y) => edge(X,Z),reach(Z,Y).
% the graph
index(,)
edge(1,2).
edge(1,3).
edge(2,4).
edge(2,5).
edge(3,6).
% ....
Note the use
table
to cache the
reach
predicate. In this simple example it is not needed, but for other applications it might be a great advantage.
append
append
in Picat is also nondeterministic as in Prolog. Here is an example where we get the different
X
and
Y
that makes up the list
[1,2,3,4]
. Collecting all the results is done with
findall
which will be discussed a little more below:
Picat> Z=findall([X,Y], append(X, Y, [1,2,3,4]))
Z = [[[],[1,2,3,4]],[[1],[2,3,4]],[[1,2],[3,4]],[[1,2,3],[4]],[[1,2,3,4],[]]]
As with
member
, we can define it on our own:
append(Xs,Ys,Zs) ?=> Xs=[], Ys=Zs.
append(Xs,Ys,Zs) => Xs=[XXsR], append(XsR,Ys,Zs).
findall
As we saw an example above
findall
in Picat works much as in Prolog. One difference is that
findall
in Picat is a
function, i.e. returns a value and that is why it was assigned to the
Z
variable above.
Other nondeterministics predicates
Here are the builtin nondeterministic predicates in Picat. They are mostly wrappers to the underlying BProlog predicates.

between(From, To, X)

append(X,Y,Z)

append(W,X,Y,Z)

member(Term, List)

select(X, List, ResList)

find(String, Substring, From, To)

find_ignore_case(String, Substring, From, To)

repeat

permutation(List, Perm)

nth(I, List, Val)

indomain(Var)
(CP)

indomain_down(Var)
(CP)

solve(Vars)
(CP)

solve(Options, Vars)
(CP)

statistics(Name,Value)
One can also note that  in contrast to Prolog 
length
is a "plain" predicate and do not creates a list. It just returns the length of the list (array, structure). (For defining av new list one have to use
new_list(Length)
instead.)
The nondeterministic predicates are great when they are needed, but don't overuse them. The Picat documentation generally recommend to write functions rather than predicates since functions are easier to debug since they return exactly one value.
An advince to Prolog addicts
In general, Prolog addicts should be a little careful when trying to direct write Prolog code in Picat. Sometimes it work very well to write it as in Prolog (with some minor modifications) but sometimes it don't work. The biggest gotcha is probably pattern matching  as mentioned above  which look much like Prolog's unification but is more like the pattern matching used in functional languages such as Haskell.
SATsolver
Picat also support solving problems using a SAT solver using almost exactly the same code as using the CP solver. The only thing one might need to change is
import cp.
to
import sat.
However, the SAT solver don't support all the global constraints from the CP solver, but it might be worth testing sometimes, since it can be very fast compared to a CP approach. [Still, I tend to rely on CP since then I can get
all the solutions  or two  which is not possible with the SAT solver used in Picat.]
Also, I haven't use the SAT solver very much. See NengFa's (and others) use at
Projects sections, e.g.
numberlink_b.pi and
mqueens.pi (it is one of the problems from the CP2013
Model and Solve Competition).
Planning
One of the things I really like in Picat is that it is now easy to implement certain planning problems. I first wrote a small planning module (
bplan.pi, inspired by Hector J. Levesque's version "Thinking as Computation", a rather new Prolog AI book). NengFa later build a much richer module
planner with a lot of different variants both optimality versions (
best_plan*
) and nonoptimality versions, both bounded and unbounded, and both with and without costs.
The
planning
module is quite simple to use:
 Define the action predicates (the legal moves):
action(FromState, ToState, Move, Cost)
 Define the initialization state (the first
FromState
)
 Define the goal state(s)/definition:
final(State)
that check if the goal state has been reached.
 call the
plan*
predicate with the appropriate arguments
A simple example is the M12 problem (
test_planner_M12.pi) which has
 two actions: merge (perfect shuffle) and reverse
 initial state (the problem instance), e.g.
[8,11,6,1,10,9,4,3,12,7,2,5]
 the goal state:
[1,2,3,4,5,6,7,8,9,10,11,12]
Here is the code for the planner part. Using the
table
directive is often a booster in these kind of planning problems, but not always:
go =>
Init = [8,11,6,1,10,9,4,3,12,7,2,5],
time(best_plan_downward(Init, Plan)),
writeln(Plan),
writeln(len=Plan.length),
nl.
final(Goal) => Goal=[1,2,3,4,5,6,7,8,9,10,11,12].
table
% merge move
action([M1,M12,M2,M11,M3,M10,M4,M9,M5,M8,M6,M7], To, M, Cost) ?=>
Cost=1, M=m,To=[M1,M2,M3,M4,M5,M6,M7,M8,M9,M10,M11,M12],Cost=1.
% reverse move
action([M12,M11,M10,M9,M8,M7,M6,M5,M4,M3,M2,M1], To,M, Cost) =>
Cost=1, M=r,To=[M1,M2,M3,M4,M5,M6,M7,M8,M9,M10,M11,M12],Cost=1.
As mentioned above, it's important to declare the first
action
with
?=>
so it is
backtrackable, i.e. that if that clause fails it will backtrack and test the next rule.
Picat finds the shortest solution (27 steps) in 1.8s:
[m,m,m,r,m,m,m,r,m,m,m,m,r,m,r,m,r,m,m,r,m,m,r,m,m,m,r]
where "m" refers to the merge action/move, and "r" to the reverse action/move.
For a
maze problem, the action (move) is simply defined as
action(From,To,Move,Cost) =>
maze(From,To),
Move = [From,To],
Cost = 1.
where
maze(From,To)
defines which nodes that are connected. And that is about as simple as it could be.
For these kind of "straight" planning problems it's  IMHO  much easier to use this approach in Picat that using Constraint Programming. However, if the problem has a lot of extra constraints then CP might be both easier to write and faster.
My other planning models are
here, mostly quite simple standard problems. NengFa has written more advanced programs, shown at the
Projects page. One neat example is his solution of the Doubleclock problem from the CP2013 competition:
doubleclock.pi which solves each of the five problem instances in about 0.1s (except for #4 which takes 0.6s).
File handling
Here is an example that use file handling (and some string handling) in Picat. It's the Project Euler problem #96 where the object is to sum the 3digit number found in the top left corners of
fifty Sudoku problems. See
euler96.pi for the full encoding.
import util.
import cp.
% ...
euler96 =>
Sudokus = read_file("sudoku.txt"),
Total = 0,
foreach(S in Sudokus)
Solved = sudoku(3, S),
Total := Total + [Solved[1,J].to_string() :
J in 1..3].flatten().parse_term()
end,
println(Total),
nl.
convert(Sudoku) = [[ R.to_integer() : R in Row] : Row in Sudoku].
sudoku(N, Board) = Board2 =>
% see above
read_file(File) = Sudokus =>
FD = open(File),
Sudokus = [],
Sudoku = [],
C = 0,
while (not at_end_of_stream(FD))
Line = read_line(FD),
if once(find(Line, "Grid",1,_To)) then
if C > 0 then Sudokus := Sudokus ++ [Sudoku.convert()] end,
Sudoku := [],
C := C + 1
else
Sudoku := Sudoku ++ [Line]
end
end,
% the last
Sudokus := Sudokus ++ [Sudoku.convert()],
close(FD).
It solves the problem in 0.03s.
This way of handling files is much easier than in standard Prolog, but perhaps not as easy as in more agile programming languages. However, Picat also have some "slurp" variants that reads the complete file into a variable:
read_file_bytes
,
read_file_lines
, and
read_file_terms
.
Structure and Map (hash table)
Picat has a construct for creating a structure 
new_struct
(a kind of poor mans OOP "object"), though I don't use this much. Here is a small example:
Picat> S = new_struct(point,3), Name = S.name, Len = S.length
S = point(_3b0,_3b4,_3b8)
Name = point
Len = 3
A data structure that I use much more is the inevitable
map
(hash table):
Picat> M = new_map([one=1,two=2]), M.put(three,3), One = M.get(one)
Here is a longer example (from
one_dimensional_cellular_automata.pi) which use a map (
Seen
) to detect fixpoint and cycles in the evolution of the patterns, i.e. if we seen the pattern before. It use
new_map()
for creating the map,
has_key(S)
for checking if pattern
S
already exists in the map, and
put(S,1)
to add the pattern S to the map. Also note the definition of the rules as predicate facts.
go =>
% _ # # # _ # # _ # _ # _ # _ # _ _ # _ _
S = [0,1,1,1,0,1,1,0,1,0,1,0,1,0,1,0,0,1,0,0],
All = ca(S),
foreach(A in All) println(A.convert()) end,
writeln(len=All.length),
nl.
convert(L) = Res =>
B = "_#",
Res = [B[L[I]+1] : I in 1..L.length].
ca(S) = All =>
Len = S.length,
All := [S],
Seen = new_map(), % detect fixpoint and cycle
while (not Seen.has_key(S))
Seen.put(S,1),
T = [S[1]] ++ [rule(sublist(S,I1,I+1)) : I in 2..Len1] ++ [S[Len]],
All := All ++ [T],
S := T
end.
% the rules
index(+)
rule([0,0,0]) = 0. %
rule([0,0,1]) = 0. %
rule([0,1,0]) = 0. % Dies without enough neighbours
rule([0,1,1]) = 1. % Needs one neighbour to survive
rule([1,0,0]) = 0. %
rule([1,0,1]) = 1. % Two neighbours giving birth
rule([1,1,0]) = 1. % Needs one neighbour to survive
rule([1,1,1]) = 0. % Starved to death.
Strings
There are some support for strings in Picat, such as

++
(for list/string concatenation)

atom_chars(Atom)

find(String, Substring,From,To)
(nondet)

find_ignore_case(String, Substring,From,To)

join(Tokens)

join(Tokens,Separator)

number_chars(Num)

parse_term(String)

split(String)

split(String, Separators)

to_atom(String)

to_binary_string(Int)

to_lowercase(String)

to_uppercase(String)

to_string(Term)
Unfortunately there is not yet any support for regular expressions (I use regexps quite much in other programming languages for my "daily programming") and I hope that will come soon enough. However, since a string is (just) an array of characters much of the general list handling can be used for manipulating strings.
Other features in Picat
Picat has many other features not much mentioned in this blog post, for example:
 debugging and trace, akin to Prolog's debug facilities

os
module for handling files and directories (see above for some file reading)

math
module for standard math functions. I tend to use only primes(Int)
, prime(Int)
and the random*
predicates from this module.
There are also many other useful predicates that is not mentioned here. See the Picat User's Guide for more about these.
Missing in Picat
Since Picat is such a new programming language there are some missing features that will  hopefully  come later, though I don't know the exact time lines.
MIP solver
A forthcoming project is to add a MIP solver to Picat.
C/Java interface
Another planned project is to add C and/or Java interface to Picat. Then it will probably be easier to add features such as regular expressions, http/tcpip access etc.
Some other utilities
Here are some few utilities that I tend to use.
Get N solutions, given a goal Goal
Sometimes one just want to find some specificed number of solutions, for example for debugging purposes. There is not builtin support for this in Picat, so I've written this following simple ersatz predicate. It use the
global get_global_map
for putting and checking the number of solutions so far; if the number of solutions are not yet reached it
fail
s which give a new solution.
get_n_solutions(Goal, N) =>
printf("Get %d solutions:\n", N),
get_global_map().put(solcount,1),
time2(Goal), % run the Goal
C = get_global_map().get(solcount),
if C < N then get_global_map().put(solcount,C+1), fail end.
Running Picat, start parameters
When running Picat programs/models, I often want to test with different predicates. Picat just support one start parameter,
main
, which is called by the picat executable. Let's call the program
program1.pi
to the discussion more concrete.
main => go.
go =>
println("This is a Picat program.").
go2 =>
println("This is another predicate.").
When running the Picat program like this:
$ picat program1.pi
Picat checks if the predicate
main
is defined and if so calls it, which in this case calls the
go
predicate.
However, there is no current support of calling the
go2
predicate (i.e. predicates not defined in the
main
predicate) via the command line. Therefore I've done this Linux shell script (
picat_run) for that. Note: you should to change the path in
PICAT_ME
.
#!/bin/sh
#
# This is just a wrapper for running the
# picat run_program.pi picat_program arg1 [arg2]
#
PICAT_ME=/home/hakank/picat/me
RUN_PROGRAM=${PICAT_ME}/run_program.pi
if [ "$#" eq 1 ]; then
picat $RUN_PROGRAM $@ go
else
picat $RUN_PROGRAM $@
fi
If running without a parameter it runs with the
go
predicate (which is my default predicate name).
The shell program runs the Picat program
run_program.pi, simply defined as:
main([ProgramGoals]) =>
println(program=Program),
% compile and load the program
cl(Program),
foreach(Goal in Goals)
nl,
% convert the goal string to an atom
G = parse_term(Goal),
println(goal=Goal),
G.call()
end.
Using this we can now run the
go2
predicate:
$ picat_run program1.pi go2
The magic is done with
cl(Program)
(which compiles and loads the program) and
parse_term(Goal)
which converts the
Goal
(the parameter string from the command line) to an atom
G
which is then called via
call
.
Right now this can use only handle simple predicates (with constants as arguments), but cannot execute code that involves variables etc. I hope that later version of Picat will have this as a builtin parameter.
Project Euler benchmark
Whenever a new version of Picat is out, I test and benchmark it with my
50 Euler programs. Here is one way of testing this (
test_euler.pi)
go =>
Skip1 = ["euler67.pi","euler.pi","euler_utils.pi","test_euler.pi",
"euler51.pi","euler66.pi","euler96.pi"],
Skip = new_map([(S=1) : S in Skip1]),
Timeout = 10000, % 10s timeout
Programs = [PP : PP in listdir("."),
match(PP, "euler"),
match(PP, ".pi")].sort(),
Fails = [],
foreach(P in Programs)
if not Skip.has_key(P) then
printf("Testing %w\n", P),
cl(P),
time_out(time(go), Timeout, Status),
println(status=Status),
if status==Timeout then
Fails := Fails ++ [P]
end,
nl
end
end,
println(fails=Fails),
nl.
match(String, Substring) => once(find(String,Substring,_,_)).
The interesting part is in bold, i.e. the loading and testing the program as well as the
timeout
check.
To be honest, I often do these tests with another program instead, which also checks that the the correct answers are shown and also reports different other things. Since I don't want to display the solutions to the Project Euler problems this program is not public. Sorry about that.
FlatZinc solver
NengFa started to write a FlatZinc solver (originally a translation of his FlatZinc solver i BProlog) some weeks before the
MiniZinc Challenge and I helped a bit with testing and added some functionality. Interestingly, Picat was the only logic programming based submission this year. However, it didn't go very well: in fact we
came last in all the different categories. Well, it was fun doint this and to be in the challenge. The FlatZinc solver can be downloaded from the
Projects page.
My contributions to Picat
Picat was originally created by NengFa Zhou and Jonathan Fruhman. After the release in May this year, I have done some contributions to the code as well as bug reports, suggestions etc, and are now sometimes mentioned as one of the Picat developers/collaborators. Note that I just develop things in Picat, not in the C or BProlog level. Some of the modules I've contributed that are in the Picat distribution are:
 util.pi: One of the utilities modules
 picat_lib_aux.pi: Utilities used by other modules
 apl_util.pi: Utilities inspired by the languages APL and K. Most of this is as a proofofconcept.
 set_util.pi: Set utilities (ported from NengFa's set utilities in BProlog)
Also, many of the Project Euler programs above #20 at the
Project page are mine. See also my
own collection where I have different variants for the problems below #20.
And see below for a list of the almost 400 public Picat programs/models I've done so far.
Models
Here are all my current public Picat models/programs. They are also available from my
Picat page and my
GitHub repo. I have categorized them in different groups since I guess that Picat might attract different target groups.
Constraint Programming
Here are models that mainly use Constraint Programming (
import cp.
).
 3_jugs.pi: 3 jugs problem (as a shortest path problem)
 a_puzzle.pi: "A Puzzle", 8809=6,... (from God Plays Dice "A Puzzle")
 a_round_of_golf.pi: A Round of Golf (Dell Logic Puzzles)
 abbots_puzzle.pi: Abbot's puzzle (Dudeney)
 abbott.pi: Abbott's window puzzle (Dudeney, via Martin Chlond)
 abc_endview.pi: ABC Endview (a.k.a. Easy as ABC and Last Man Standing)
 added_corner.pi: Added corner puzzle
 all_differ_from_at_least_k_pos.pi: Decomposition of the global constraint
all_differ_from_at_leat_k_pos
 all_equal.pi: Decomposition of the global constraint
all_equal
 all_interval.pi: All interval problem (CSPLib #7)
 alldifferent_cst.pi: Decomposition of the global constraint
alldifferent_cst
 alldifferent_except_0.pi: Decomposition of the global constraint
alldifferent_except_0
 alldifferent_modulo.pi: Decomposition of the global constraint
alldifferent_modulo
 alldifferent_on_intersection.pi: Decomposition of the global constraint
alldifferent_on_intersection
 alphametic.pi: A fairly general alphametic solver (e.g. SEND+MORE=MONEY)
 among.pi: Decomposition of the global constraint
among
 among_seq.pi: Decomposition of the global constraint
among_seq
 appointment_scheduling.pi: Appointment scheduling (StackOverflow)
 arch_friends.pi: Arch friends puzzle (Dell Logic Puzzles)
 assign.pi: Assignment problem from comp.lang.prolog (ported from BProlog model)
 assignment.pi: Some different assignment problems
 autoref.pi: Auto reference problem (from Global Constraints Catalog)
 averbach_1_2.pi: Seating problem (Averbach & Chein "Problem Solving Through Recreational Mathematics")
 averbach_1_3.pi: Logic puzzle (Averbach & Chein "Problem Solving Through Recreational Mathematics")
 bananas.pi: Bananas problem
 babysitting.pi: Babysitting puzzle (Dell Logic Puzzles)
 bales_of_hay.pi: Bales of hay problem
 best_host.pi: Best host (PuzzlOr)
 bin_packing.pi: Bin packing problem
 bin_packing2.pi: Decomposition of the global constraint
bin_packing
 birthdays_coins.pi: Birthdays coin puzzle (Clarke, via Martin Chlond)
 book_buy.pi: Book buy puzzle (Kraitchik, via Martin Chlond)
 breaking_news.pi: Breaking news (Dell Logic Puzzles)
 broken_weights.pi: Broken weights (yet another weighing problem)
 build_a_house.pi: Build a house (simple scheduling problem)
 bus_schedule.pi: Bus scheduling problem (from Taha "Introduction to Operations Research")
 calculs_d_enfer.pi: Calculs d'enfer alphametic puzzle
 candies.pi: Candies problem (HackerRank)
 car.pi: Car sequencing problem (Van Hentenryck, OPL)
 changes.pi: Coins application
 chicken.pi: Chicken problem (ported from BProlog's entry to 2011 Prolog Programming Contest)
 circling_squares.pi: Circling squares puzzle (Dudeney)
 circuit.pi: Decomposition of the global constraint
circuit
 clique.pi: Decomposition of the global constraint
clique
 clock_triplet.pi: Clock triplet (Dean Clark via Martin Gardner)
 color.pi: Map coloring (ported from BProlog)
 coins3.pi: Coins problem
 coins_grid.pi: Coins grid problem (Tony Hurlimann)
 coins_sum.pi: Yet another coins problem (Richard Wiseman)
 combinatorial_auction.pi: Combinatorial auction
 contracting_costs.pi: Contracting costs (Sam Loyd)
 costas_array.pi: Costas array
 covering_opl.pi: Set covering problem (from OPL)
 crew.pi: Crew allocation problem (Gecode)
 crossbar.pi: Crossbar (standard Prolog benchmark)
 crossfigure.pi: Crossfigure (CSPLib #21)
 crossword2.pi: Simple crossword problem (standard CLP example)
 crowd.pi: The crowded board (Martin Chlond)
 crypta.pi: Cryptarithmetic puzzle
 crypto.pi: Cryptarithmetic puzzle
 crypto.pi: Cryptarithmetic puzzle
 cumulative_test.pi: Test of cumulative constraint
 cur_num.pi: Curious numbers (Dudeney)
 curious_set_of_integers.pi: Curious set of integers (Martin Gardner)
 de_bruijn.pi: de Bruijn Sequences (both traditional and "arbitrary")
 devils_word.pi: Devil's word (sum ASCII representation of a word to a specific sum, e.g. 666)
 diet.pi: Simple diet (optimization) problem
 digit8.pi: Digit 8 problem (Prolog benchmark)
 dinner.pi: Dinner problem
 discrete_tomography.pi: Discrete tomography
 distribute.pi: Decomposition of global constraint
distribute
 divisible_by_9_through_1.pi: Divisible by 9 through 1
 dominopuzzle.pi: Domino puzzle (ported from BProlog)
 donald_gerald.pi: DONALD + ROBERT = GERALD (alphametic problem)
 dqueens.pi: Dudeney's queen placement problem (Martin Chlond)
 ddrive_ya_nuts.pi: Drive Ya Nuts puzzle
 dudeney_bishop_placement1.pi: Dudeney's Bishop placement problem I (Martin Chlond)
 dudeney_bishop_placement2.pi: Dudeney's Bishop placement problem II (Martin Chlond)
 dudeney_numbers.pi: Dudeney numbers
 egg_basket.pi: Egg Basket problem (Kordemsky, via Martin Chlond)
 einav_puzzle.pi: Einav's puzzle
 einstein_hurlimann.pi: Einstein's logic puzzle (Who keep the fish?, from Tony Hurlimann)
 einstein_opl.pi: Einstein's logic puzzle (Who keep the fish?)
 eq10.pi: Eq 10 benchmark
 eq20.pi: Eq 20 benchmark
 equation.pi: Solve the equation: 11x11=4, 22x22=16, 33x33=? (different interpretations)
 evens.pi: Evens puzzle (Kordemsky, via Martin Chlond)
 eyedrop_optimize2.pi: Eyedrop optimization, optimize the time (hour) a number of different eye drops should be taken on a day (disperse each type as much as possible).
 exactly.pi: Decomposition of global constraint
exactly
 exodus.pi: Exodus puzzle (Dell Logic Puzzles)
 fancy.pi: Mr Greenguest's fancy dress puzzle
 five.pi: 5x5 puzzle (Martin Chlond)
 five_brigands.pi: Five Brigands problem (Dudeney)
 five_elements.pi: Five Elements (Charles W. Trigg)
 fixed_charge.pi: Fixed charge problem (ported from BProlog(
 fill_a_pix.pi: Fillapix problem
 fill_in_the_squares.pi: Fill in the squares (Brainjammer)
 finding_celebrities.pi: Finding celebrities at a party
 four_islands.pi: Four Islands Puzzle (Dell Logic Puzzles)
 four_numbers.pi: Four Numbers problem (Stack overflow)
 fractions.pi: Fractions problem (Prolog benchmark)
 furniture_moving.pi: Furniture moving (simple scheduling problem, from Marriott and Stuckey: "Programming with Constraints")
 futoshiki.pi: Futoshiki grid puzzle
 general_store.pi: General Store alphametic puzzle
 global_cardinality.pi: Decomposition of global constraint
global_cardinality
 global_contiguity.pi: Decomposition of global constraint
global contiguity
 golomb_ruler.pi: Golomb Ruler
 hamming_distance.pi: Hamming distance
 handshaking.pi: Halmo's handshaking problem
 hanging_weights.pi: Hanging weights problem
 harshad_numbers.pi: Harshad numbers
 heterosquare.pi: Heterosquare
 hidato.pi: Hidato
 hitchcock_transportation_problem.pi: (HitchcockKoopmans) Transportation problem
 honey_division.pi: Honey division puzzle (Dudeney, via Martin Chlond)
 huey_dewey_louie.pi: Huey, Dewey, and Louie logical puzzle
 isbn.pi: Some explorations of ISBN13
 jive_turkeys.pi: Jive turkes puzzle (Martin Chlond)
 jobs_puzzle.pi: Jobs puzzle
 just_forgotten.pi: Just forgotten puzzle (Enigma 1517)
 K4P2GracefulGraph2.pi: K4P2 Graceful Graph
 kakuro.pi: Kakuro grid puzzle
 kakuro2.pi: Kakuro grid puzzle written by Lorenz Schiffmann (with some small additions by hakank)
 kenken2.pi: KenKen grid puzzle
 killer_sudoku.pi: Killer Sudoku
 knapsack_investments.pi: Investments problem (knapsack)
 krypto.pi: Krypto puzzle (combine given numbers to an objective using the four basic arithmetic operations)
 labeled_dice.pi: General solver for Labeled dice and Building Blocks problems
 langford.pi: Langford's number problem (CSPLib #24)
 latin_squares.pi: Latin squares
 least_diff.pi: Minimize the difference of ABCDEFGHIJ where A..J is distinct integers
 lecture_series.pi: Lecture Series problem (Dell Logic Puzzles)
 lectures.pi: Lectures problem (simple scheduling of lectures, from Biggs "Discrete Mathematics")
 lex.pi: Decompositions of global constraints
lex_less, lex_lesseq, lex_greater, lex_greateeq, lex2, lex2eq
 lichtenstein_coloring.pi: Lichtenstein coloring
 local_art_theft.pi: Local art theft (logic puzzle)
 M12.pi: M12 permutation puzzle (both CP and nonCP approach)
 magic_hexagon.pi: Magic hexagon (CSPList #23)
 magic_sequence.pi: Magic sequence (CSPLib #19)
 magic_square.pi: Magic squares
 magic_square_and_cards.pi: Magic squares and cards (Martin Gardner)
 map_coloring.pi: Simple map coloring problem
 marathon2.pi: Marathon logic puzzle
 max_flow.pi: Max flow problem (ported from BProlog)
 max_flow_taha.pi: Max flow problem (Taha)
 max_flow_winston1.pi: Max flow problem (Winston)
 maximum_still_life.pi: Maximum density still life (CSPLib #32)
 minesweeper.pi: Minesweeper solver
 money_change.pi: Money change
 monks_and_doors.pi: Monks and doors problem
 mr_smith.pi: Mr Smith logic problem (IF Prolog)
 multiplicative_sequence.pi: Multiplicative sequence (from "Mind Your Decisions")
 music_men.pi: Music Men Puzzle (Dell Logic Puzzles)
 nadel.pi: Nadel's construction problem (Rina Dechter "Constraint Processing")
 nontransitive_dice.pi: Nontransitive dice
 number_of_days.pi: Number of days (knapsack) problem
 nvalue.pi: Decomposition of global constraint
nvalue
 nvalues.pi: Decomposition of global constraint
nvalues
 olympic.pi: Olympic logic puzzle (Prolog benchmark)
 organize_day.pi: Organizing a day (very simple scheduling problem)
 ormat_game.pi: Ormat game grid puzzle
 p_median.pi: Pmedian problem (OPL)
 pandigital_numbers.pi: Pandigital numbers
 pair_divides_the_sum.pi: Pair divides the sum
 partition_into_subsets_of_equal_values.pi: Partition into subset of equal sums
 perfect_square_sequence.pi: Perfect square sequence
 pert.pi: Simple PERT problem (Pascal Van Hentenryck)
 photo_problem.pi: Photo problem (from Mozart/Oz)
 picking_teams.pi: Picking teams
 pigeon_hole.pi: Pigeon hole problem
 place_number_puzzle.pi: Place number puzzle
 post_office_problem2.pi: Employment scheduling (from Wayne Winston "Operations Research")
 primes_in_a_circle.pi: Primes in a circle
 pythagoras.pi: Pythagoras problem
 quasigroup_completion.pi: Quasigroup completions
 queens.pi: NQueens model
 rabbits.pi: Rabbits problem (Van Hentenryck, OPL book)
 remainders.pi: Remainders puzzle (Kordemsky)
 remarkable_sequence.pi: Remarkable sequence (Alma0)
 reverse_multiples.pi: Reverse multiples problem
 rotation.pi: Rotation (permutation) puzzle (the nonCP approach uses bplan.pi
 safe_cracking.pi: Safe cracking (from Mozart/Oz)
 schedule1.pi: Simple scheduling problem (SICStus Prolog)
 schedule2.pi: Simple scheduling problem
 scheduling_speakers.pi: Scheduling speakers (Rina Dechter "Constraint Processing")
 schur_numbers.pi: Schur numbers
 secret_santa.pi: Secret Santa problem
 secret_santa2.pi: Secret Santa problem II (optimize "Santa distance")
 send_more_money.pi: SEND+MORE=MONEY, different approaches
 send_most_money.pi: SEND+MOST=MONEY: generate all solutions with the maximum value of MONEY
 sequence.pi: Decomposition of global constraint
sequence
 seseman.pi: Seseman's Convent problem
 set_covering.pi: Set covering problem (placing firestations, from Wayne Winston)
 set_covering2.pi: Set covering problem (placing security telephone at campus, from Taha)
 set_covering3.pi: Set covering problem (minimize the number of senators for a committee, from Katta G. Murty)
 set_covering4.pi: Set covering and set partition problem
 set_covering5.pi: Set covering and scheduling (from Lundgren, Ronnqvist, Varbrand "Optimeringslara" ["Optimization theory"])
 set_covering_deployment.pi: Set covering deployment
 set_covering_skiena.pi: Set covering (Steven Skiena)
 sicherman_dice.pi: Sicherman dice
 ski_assignment.pi: Ski assignments
 sliding_sum.pi: Decomposition of global constraint
sliding sum
 social_golfers1.pi: Social Golfers (CSPLib #10)
 social_golfers2.pi: Social Golfers (CSPLib #10)
 sonet.pi: SONET problem
 stable_marriage.pi: Stable marriage
 steiner.pi: Steiner triplets
 strimko2.pi: Strimko Grid Puzzle
 stuckey_seesaw.pi: Balancing on a seesaw
 student_and_languages.pi: Students and Languages problems (Antoni Niederlinski)
 subset_sum.pi: Subset sum problem (from Katta G Murty)
 sudoku.pi: Sudoku solver
 survo_puzzle.pi: Survo puzzle
 table.pi: Decomposition of global constraint
table
 talisman_square.pi: Talisman square
 temporal_reasoning.pi: Temporal reasoning (Krzysztof R. Apt)
 the_family_puzzle.pi: The Family Puzzle
 timpkin.pi: Mrs Timpin's Age (Dudeney)
 to_num.pi:
to_num
Convert a number to/from a list of digits (e.g. for alphametic problems)
 torn_numbers.pi: Torn numbers (Dudeney)
 tourist_site_competition.pi: Tourist Site Competition
 traffic_lights.pi: Traffic lights problem (CSPLib #16)
 trains.pi: Trains problem (using
table
constraint, from SWI Prolog manual)
 tsp.pi: Traveling Salesperson problem (with some different problem instances)
 tunapalooza.pi: Tunapalooza (Dell Logic Puzzles)
 twin_letters.pi: Twin letters
 volsay1.pi: Volsay problem
 volsay2.pi: Volsay problem
 volsay3.pi: Volsay problem
 warehouse.pi: Warehouse location (OPL)
 wedding_optimal_chart.pi: Finding an optimal wedding seating chart
 who_killed_agatha.pi: Who killed Agatha? (The Dreadsbury Mansion Murder Mystery)
 xkcd.pi: Solving the xkcd "knapsack" (or subsetsum) problem from http://xkcd.com/287/
 young_tableaux.pi: Young tableaux and partitions
 zebra.pi: Zebra puzzle ("Who owns a Zebra, and who drinks water?")
Project Euler problem
Here are some solutions for the
Project Euler problems:
Total time for running all problems #1..#50 is < 14 seconds (on my Linux Ubuntu 12.04, 8 core Intel i7 CPU 930@2.80GHz). Some programs contains several alternative solutions.
test_euler.pi: Simple Picat program for testing all the Project Euler programs (#1..#50).
Rosetta Code problem
Picat solutions for some
Rosetta Code problems.
Miscellaneous problem
Here are some other programs, modules, utilities, e.g. standard Prolog/GOFAI examples etc.
 Prolog benchmark (selected)
Here are some translations of standard Prolog benchmark programs.
bench.pi: The main program to run these programs.
 1d_rubiks_cube.pi: 1D Rubik's cube (permutation puzzle). Uses the bplan.pi
 allpartitions.pi: Generate all partitions of a number
 analogy.pi: Evan's Analogy program (ported from Sterling "The Art of Prolog")
 apl_utils.pi: APL utils. Some utilities inspired by APL and/or K. (Is now a module in Picat distribution.)
 bplan.pi: BPlan module, simple but fairly general planner. It consist of one "traditional" breathfirst planner (
bplan/3
), and one using Picat's table features (plan2/4
). Note: Nowadays one should problably use the builtin planner
module instead.
It is used by these programs:
Also, see the newer test_planning_*.pi below for these planning problems using the builtin planner
module.
 catalan_numbers.pi: Catalan numbers
 coins_planning.pi: Coins planning puzzle. Uses the bplan.pi module
 dcg_test.pi: "DCG" in Picat, i.e. checking or generating sentences from a grammar
 eliza.pi: Simple Eliza program (ported from Sterling "The Art of Prolog")
 farmer_planning.pi: Farmer planning problem. Uses the bplan.pi module.
 first_100_pi_digits.pi: Primes in first 100 Pi digits
 flag.pi: Flag problem (ported from BProlog's entry to 2010 Prolog Programming Contest)
 knapsack_tabling.pi: Knapsack problem, using tabling (port from BProlog)
 lace.pi: Lace problem (ported from BProlog's entry to 2012 Prolog Programming Contest)
 lcs_tabling.pi: Longest Common Subsequence using tabling (ported from BProlog)
 M12.pi: M12 permutation puzzle (both CP and nonCP approach) (also use bplan.pi for nonCP planning)
 mankell.pi: Generate all possible (right and wrong) spellings of ('Henning Mankell') and 'Kjellerstrand' (using a "grammar" etc)
 matrix_slice.pi: Some list/array/matrix extraction functions. E.g.
M.slice(1..3, 2..4)
for extracting a sub square
 mcsam.pi: MicroSAM program (ported from Sterling "The Art of Prolog")
 missionaries_and_cannibals.pi: Missionaries and cannibals problem. Uses the bplan.pi module
 monkey_banana.pi: Monkey and banana puzzle. Uses the bplan.pi module
 mu.pi: Douglas Hoftstadter's MU problem (Prolog benchmark)
 obst.pi: Optimal Binary Search Tree, using tabling (port from BProlog)
 omelet.pi: Omelet problem (ported from BProlog's entry to 2012 Prolog Programming Contest)
 panoz.pi: Panoz problem (ported from BProlog's entry to 2010 Prolog Programming Contest)
 pattern_matching.pi: (Experimental) Functions inspired by Haskell's Prelude.
 picat_run: A Unix shell program which wrap run_program.pi so it's easier to run Picat with a program and a goal
 read_test.pi: Read a word list and test each words against a pattern of consecutive characters, e.g. ".*a.*.b.*c.*". (Word list used: words_lower.txt which contains about 410000 English words, abbreviations etc.)
 pattern_matching.pi: (Experimental) Functions inspired by Haskell's prelude.
 puzzle2x3_plan.pi: Stripped down version of 8puzzle. Uses the bplan.pi module.
 railroad_switching.pi: Railroad switching. Uses the bplan.pi module. (From Edelkamp and Schrodl: "Heuristic Search: Theory and Applications")
 run_program.pi: Run a Picat program without
main
predicat from command line. Example: picat run_program.pi queens "time(go)"
. Note: Right now it just can handle simple goals. Also, see picat_run (a Unix shell program for simplifying running Picat with a program + goal)
 set_util.pi: Set utils (from NengFa's BProlog code) (Is now a module in Picat distribution.)
 staircase.pi: Draw a stair case (ported from BProlog)
 test_planner_1d_rubiks_cube.pi: 1D Rubik's cube planning problem. Using the
planner
module.
 test_planner_coins_planning.pi: Coins planning. Using the
planner
module.
 test_planner_farmer.pi: Farmer problem. Using the
planner
module.
 test_planner_M12.pi: M12 problem. Using the
planner
module.
 test_planner_maze.pi: Maze problem. Using the
planner
module.
 test_planner_missionaries_and_cannibals.pi: Missionaries and cannibals problem. Using the
planner
module.
 test_planner_monkey_banana.pi: Monkey and Banana problem. Using the
planner
module.
 test_planner_puzzle2x3.pi: Stripped down version of 8puzzle. Using the
planner
module.
 test_planner_railroad_switching.pi: Railroad switching problem. Using the
planner
module.
 test_planner_rotation.pi: Rotation permutation puzzle. Using the
planner
module.
 test_planner_water_jugs.pi: Water jugs planning problem. Using the
planner
module.
 transitive_closure.pi: Transitive closure (right and left) using tabling (port of BProlog program)
 util_me.pi: Misc utilities
 water_jugs.pi: Water jugs problem (planning). Uses the bplan.pi module,
bplan/3
 water_jugs2.pi: Water jugs problem (planning), much faster version. Uses the bplan.pi module,
plan2/4
.