Skip to content

Latest commit

 

History

History
95 lines (64 loc) · 2.49 KB

1.2-lists-in-prolog.md

File metadata and controls

95 lines (64 loc) · 2.49 KB
Raw

Lists in Prolog

List is a simple data structure widely used in non-numeric programming. It is a collection of items in a particular order. The items in a list are called elements or sometimes items.

In Prolog, a list can be represented as:

[a, b, c]

All structures in Prolog are trees, and so is a list. A list can be either empty ([]) or non-empty.

A non-empty list is a structure with a head and a tail. The head is the first element of the list, and the tail is the rest of the list. The tail is either empty or another list:

[Head | Tail]

or, in older versions of Prolog:

.(Head, Tail)

Membership

To check if an element is a member of a list, we can use the built-in predicate member/2:

?- member(a, [a, b, c]).
true.

X is a member of a list if:

  • X is the head of the list;
  • X is a member of the tail of the list:
member(X, [X | _]).
member(X, [_ | Tail]) :- member(X, Tail).

Programming Example: Eight Queens

The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other. Thus, a solution requires that no two queens share the same row, column, or diagonal.

Representation

One possible representation is by using a list of eight items, where each item represents the position of each queen. The position can be represented by a pair as X/Y, where X and Y are integers between 1 and 8, and represent the column and row, respectively.

Example:

[1/4, 2/2, 3/7, 4/3, 5/6, 6/8, 7/5, 8/1]

Solution

  • The problem is then to find such a list of the form:
[1/Y1, 2/Y2, 3/Y3, 4/Y4, 5/Y5, 6/Y6, 7/Y7, 8/Y8]
  • where Y1, Y2, ..., Y8 are integers between 1 and 8, and represent the rows of the queens.
  • the X coordinates are fixed, since each queen is in a different column.

The solution predicate can be formulated by two cases:

  • The empty list is a solution, or;
  • The list [X/Y | Others] is a solution if Others is a solution and X/Y is a valid position for a queen.
solution([]).
solution([X/Y | Others]) :- 
    solution(Others), 
    member(Y, [1, 2, 3, 4, 5, 6, 7, 8]),
    noattack(X/Y, Others).

In case 2, the predicate noattack/2 checks if the queen at position X/Y does not attack any other queen in the list Others.

noattack(_, []).
noattack(X/Y, [X1/Y1 | Others]) :- 
    Y =\= Y1, 
    Y1 - Y =\= X1 - X, 
    Y1 - Y =\= X - X1, 
    noattack(X/Y, Others).