ELAN - Examples of programs written in ELAN

- Queens

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];
  [] 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
The 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];
   [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)
The strategy used to guide this rule is:
strategies for list[int]
  [] queens => dc one(queensrule) end
We 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]
  [] queens => dk(queensrule) end
This 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.