Wednesday, June 27, 2012

Solution of eight queens problem in Prolog

Eight queens problem is a constraint satisfaction problem. The task is to place eight queens in the 64 available squares in such a way that no queen attacks each other. So the problem can be formulated with variables x1,x2,x3,x4,x5,x6,x7,x8 and y1,y2,y3,y4,y5,y6, y7,y8; the xs represent the rows and ys the column. Now a solution for this problem is to assign values for x and for y such that the constraint is satisfied.
The problem can be formulated as
P={(x1,y1),(x2,y2),……………………..(x8,y8)} 
where (x1,y1) gives the position of the first queen and so on. So it can be clearly seen that the domains for xi and yi are  
Dx = {1,2,3,4,5,6,7,8}and Dy ={1,2,3,4,5,6,7,8} respectively. 
The constraints are
i. No two queens should be in the same row,
   i.e yi≠yj for i=1 to 8;j=1 to 8;i≠j
ii. No two queens should be in the same column,
  i.e xi≠xj for i=1 to 8;j=1 to 8;i≠j
iii. There should not be two queens placed on the same   diagonal line
  i.e (yi-yj) ≠ ±(xi-xj).
Now a solution to this problem is an instance of P wherein the above mentioned constraints are satisfied.

Friday, June 22, 2012

Simulation of Non-deterministic finite state automata using backtracking feature of prolog.

Let us now see how the features of prolog can be used to simulate a non-deterministic automata which would have been a cumbersome task using other programming languages.
A nondeterministic finite automaton is an abstract machine that reads a string of symbols as input and decides whether to accept or to reject the input string. An automaton has a number of states and it is always in one of the states. The automata can change from one state to another upon encountering some input symbols. In a non deterministic automata the transitions can be non deterministic meaning that the transition may take place with a NULL character or the same character may result in different transitions
A non deterministic automaton decides which of the possible moves to execute, and it chooses a move that leads to the acceptance of the string if such a move is available.
Let us simulate the given automata.

Thursday, June 21, 2012

Visual Prolog Program to delete a given element from the list.

To delete a element from a list the position and the element list is passed to the predicate delete. Then the delete predicate continuously breaks the list into head (H) and Tail (T) to find that the correct position is reached. On reaching the appropriate position to delete the element the predicate slices the head off the list and finally merges the remaining art with the rest. The prolog code is given as below:

DOMAINS
int_list = integer*

PREDICATES
del(integer, int_list, int_list)

CLAUSES
del(0,[H|T], T).
del(P,[H|T], [H|Z]):-
P1 = P - 1, del(P1,T,Z).

GOAL
del(2, [0,1,2,3,4,5],X).

Visual Prolog Program to append two list.

Here the two list are taken by the predicate “append” and returns the appended list. To append two list a list is broken continuously until the last empty list is encountered and finally the other list is appended or joined at the end of first recursively. The code to append is given as follows:

DOMAiNS
int_list = integer*

PREDICATES
append(int_list, int_list, int_list)

CLAUSES
append([],L,L).
append([H|L1], L2, [H|L3]):-append(L1,L2,L3).

GOAL
append([1,2,3,4],[5,6,7,8],Z).

Visual Prolog Program to find length of a list.

In this program the predicate length takes integer list and output a integer which is the length of list. Here the predicate length is called repeatedly or recursively until a last empty list is encountered and the 0 value is returned which is then continuously incremented to find the length.

Source Code

DOMAINS
int_list = integer*

PREDICATES
length(int_list, integer)

CLAUSES
length([],0).
length([H|T],L):-length(T,L1), L=L1+1.

GOAL
length([1,2,3,4,5],Z).

Visual Prolog Program to add the contents of an integer list.

Here in this program, the sum function is made that adds the contents of list. The first segment ( i.e the Domains section ) defines or declares the space dynamically for integer list. Then the predicate sum is defined that takes integer list and a Integer as arguments. The next clause section provides the necessary reasoning and facts to find the solution to the problem. Here the predicate sum is called recursively until it gets the last element of the list which is the empty list itself and returns 0 if empty list is encountered. The add predicate else adds the first element to the solution repeatedly to find the solution.

Source Code

DOMAINS
int_list = integer*

PREDICATES
sum(int_list, integer)

CLAUSES
sum([],0).
sum([H|T], X):-
sum(T,Y), X=H+Y.

GOAL
sum([1,8],Z).

List Manipulation in Prolog

List is one of the most important data structure in Prolog. Lists are contained in square brackets with the element being separated by commas. Here’s is an example.

[Nepal, India, Bhutan, Sri Lanka, Maldives, Pakistan, Bangladesh]

This is the list of seven atoms Nepal, India, Bhutan, Sri Lanka, Maldives, Pakistan, Bangladesh. Element of lists could be any valid Prolog terms, i.e. atoms, numbers, variables or compound terms. This includes other lists too. The empty list is written as []. The following is another example of list.

[Mango, X, [], son (Dasarath, X), [x, y, z], func(5)]

Head and Tail in List

The first element of a list is called its head and the remaining list is called the tail. An empty list doesn’t have a head. A list just containing a single element has a head (namely that particular single element) and its tail is the empty list. In above example of lists of countries in SAARC, Nepal is head and remaining countries constitute tail and this is represented as

[Nepal | [India, Bhutan, Sri Lanka, Maldives, Pakistan, Bangladesh]]

A list containing exactly one element has one head and empty tail. We will see some operations on List in Next Tutorial.

Prolog program to find Factorial of an Integer

PREDICATES
factorial(integer, integer)

CLAUSES
factorial(0,1).
factorial(X,Y):-
X<>0, S=X-1, factorial(S,Y1), Y=X*Y1.

GOAL
write("The value of Z is "),
factorial(5,Z).