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

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

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.