The goal of the program is to place on a chessboard eight queens such that none of them attacks the other ones.
For representing the solution we use a list of eight positions, the n-th element indicating where we have to place the queen from the n-th column.
We use a strategy that tries to place one queen such that it is not in contradiction with the queens already placed. For this we use an auxiliary function that tests if the queen we want to place at the current step attacks one of the queens placed on the previous columns.
rules for bool p,d,diff : int; l : list[int]; global  ok(diff,d,nil) => true end  ok(diff,d,p.l) => false if d == p end  ok(diff,d,p.l) => false if d-p == diff end  ok(diff,d,p.l) => false if p-d == diff end  ok(diff,d,p.l) => ok(diff+1,d,l) end endThe argument diff represents the number of columns between the queen on the line d and the queen on the line p.
The rewrite rule queensrule tries to place the queens starting from the first column. For each column we try to place the queen on the line generated by the strategy try if this does not attack the previous positions.
rules for list[int] p1,p2,p3,p4,p5,p6,p7,p8 : int; pp1,pp2,pp3,pp4,pp5,pp6,pp7,pp8 : list[int]; local [queensrule] queens => p8.pp7 where p1:=(try) 0 where p2:=(try) 0 where pp1:=() p1.nil if ok(1,p2,pp1) where p3:=(try) 0 where pp2:=() p2.pp1 if ok(1,p3,pp2) where p4:=(try) 0 where pp3:=() p3.pp2 if ok(1,p4,pp3) where p5:=(try) 0 where pp4:=() p4.pp3 if ok(1,p5,pp4) where p6:=(try) 0 where pp5:=() p5.pp4 if ok(1,p6,pp5) where p7:=(try) 0 where pp6:=() p6.pp5 if ok(1,p7,pp6) where p8:=(try) 0 where pp7:=() p7.pp6 if ok(1,p8,pp7) end endThe strategy used to guide this rule is:
strategies for list[int] implicit  queens => dc one(queensrule) end endWe try to apply the rule queensrule until we get a valid placement or all the positions have been tried unsuccesfully. If at one stage of the algorithm none of the position is acceptable that we get back to the previous column(s) and we try the next possible position. Once all the eight queens have been placed we return the solution.
If we want to obtain all the solutions we use a slightly modified strategy:
strategies for list[int] implicit  queens => dk(queensrule) end endThis strategy returns not only the first valid result but finds all the possible solutions by backtracking on the previous columns after even if a solution has been found.