Page No.

Turbo Prolog Editor

Practical No:_____________ Date:__________
Aim: To study the turbo prolog editor and implement basic facts.

Theory:
Prolog, which stands for PROgramming in LOGic, is the most widely available language in the logic
programming paradigm. Logic and therefore Prolog is based the mathematical notions of relations
and logical inference. Prolog is a declarative language meaning that rather than describing how to
compute a solution, a program consists of a data base of facts and logical relationships (rules) which
describe the relationships which hold for the given application. Rather than running a program to
obtain a solution, the user asks a question. When asked a question, the run time system searches
through the data base of facts and rules to determine (by logical deduction) the answer.

Among the features of Prolog are `logical variables' meaning that they behave like mathematical
variables, a powerful pattern-matching facility (unification), a backtracking strategy to search for
proofs, uniform data structures, and input and output are interchangeable.

Prolog is used in artificial intelligence applications such as natural language interfaces, automated
reasoning systems and expert systems. Expert systems usually consist of a data base of facts and rules
and an inference engine, the run time system of Prolog provides much of the services of an inference
engine.

Structure of Prolog Program

1. A Prolog program consists of a database of facts and rules, and queries (questions).
a. Fact
b. Rule
c. Query
d. Variables
e. Constants
2. Prolog is used for solving problems that involve objects and the relationships between objects.
3. A program consists of a database containing one or more facts and zero or more rules.
4. A fact is a relationship among a collection of objects.
5. Relationships can have any number of objects.

Gandhinagar Institute of Technology 3161608 AI

 Page No.

Example of fact

dog(fido). >> Fido is a dog or It is true that fido is a dog

sister(mary, joe). >> Mary is Joe’s sister.

play(mary, joe, tennis). >> It is true that Mary and Joe play tennis.

A Turbo Prolog program consists of two or more sections.

Clauses Section

1. This section is the main body of the prolog program

2. It contains the clauses that define the program – facts and rules.

Predicates Section

1. Predicates (relations) used in the clauses section are defined.

2. Each relation used in the clauses of the clauses section must have a corresponding predicate
definition in the predicates section. Except for the built in predicates of Turbo Prolog.
3. A Turbo Prolog may also have a domains section. In this section the programmer can define
the type of each object.
4. Example: Clauses Section – likes(tom, anna).
5. Predicates Section – likes(boy, girl)
6. Domains Section – boy, girl = symbol
7. It is possible to omit the domains section by entering the data types of objects in the
predicates section. likes(symbol,symbol)

Designing Solutions

Define the contents of three sections of prolog program as follows-

1. Define Domain:- Define various variables and symbols needed for problem.(Similar to
definition part of conventional programming )
2. Define Predicates:- Different relation between symbols and variables are to be declared.
(Similar to defining function prototype in conventional programming)
3. Define Clauses:- Various facts and rules supporting the predicates declared are to be
defined.

Implementing, compiling and executing the program

1. Start Turbo Prolog

2. Select the Edit mode
3. Type in the program
4. Exit the Editor using Esc.
Gandhinagar Institute of Technology 3161608 AI
 Page No.

5. Save the program

6. Select Run (which compiles the program for you in memory)
a. Once you have followed these steps you will see the following prompt in the Dialog
Panel:
Goal:
b. Using a Prolog program is essentially about asking questions. To ask th e executing
Prolog program a question you specify the Goal.

Testing the program

Turbo Prolog will respond with True if the goal matches with facts stored in the clauses section and
prompt for another goal.

Possible outcomes of specifying a goal:

1. The goal will succeed; that is, it will be proven true.

2. The goal will fail; Turbo Prolog will not be able to match the goal with any facts in the
program.
3. The execution will fail because of an error in the program.

Exercise:

1. Write a Prolog program that demonstrates the below given facts:

a. Ram likes mango.
b. Seems is a girl.
c. Bill likes Cindy.
d. Rose is red.
e. John owns gold.

Review Questions:

1. What is the use of Prolog?

2. Which are the different sections of a prolog program?
3. Convert below statements to prolog facts
i. The cakes are delicious.
ii. The pickles are spicy.
iii. Priya relishes coffee.

Gandhinagar Institute of Technology 3161608 AI

 Page No.

Study of family relationship tree

Practical No:_____________ Date:__________

Aim: To study about family relationship tree in Prolog.

Theory:
Prolog predicates correspond to predicate symbols in logic, terms inside the predicates correspond
to functional terms appearing as arguments of logic predicates. These terms are made up of
constants, variables, and function symbols. Prolog can be used to find relationship between the
objects.
Example database:
Facts
John is the father of Jim.
Jane is the mother of Jim.
Jack is the father of John.
Facts corresponding to each statement are as below:
father(john,jim).
mother(jane,jim).
father(jack,john).
Rules
Person 1 is a parent of Person 2 if
Person 1 is the father of Person 2 or Person 1 is the mother of Person 2.
Person 1 is a grandparent of Person 2 if
some Person 3 is a parent of Person 2 and Person 1 is a parent of Person 3.
Rules corresponding to the above statements are as below:
parent(Person1,Person2):-
father(Person1,Person2).
parent(Person1,Person2):-
mother(Person1,Person2).
grandparent(Person1,Person2):-
parent(Person3,Person2),
parent(Person1,Person2).
Example questions:
Who is Jim's father?
?-father(Who,jim).
Is Jane the mother of Fred?
?-mother(jane,fred).
Does Jack have a grandchild?
?-grandparent(jack, _).

Gandhinagar Institute of Technology 3161608 AI

 Page No.

Exercise:
1. Write a prolog program for family relationship tree.

Review Questions:
1. What do you mean by predicates?
2. How to write a fact in prolog?
3. What is the advantage of relationship tree in AI?

Gandhinagar Institute of Technology 3161608 AI

 Page No.

Study of rules in prolog

Practical No:_____________ Date:__________

Aim: To study the rules implemented in prolog.

Theory:
Prolog programs describe relations, defined by means of clauses. There are two types of clauses:
facts and rules. A rule is of the form
Head :- Body.
and is read as "Head is true if Body is true". A rule's body consists of calls to predicates, which
are called the rule's goals.

Clause Syntax
 ":-" means "if" or "is implied by". Also called the neck symbol. The syntax of if statement
o If (condition) then (conclusion)  Rule: [conclusion :- condition].
 The left hand side of the neck is called the head.
 The right hand side of the neck is called the body.
 The comma, ",", separating the goals, stands for and.
 Clauses with bodies are called rules. An example of a rule is:

animal(X) :- cat(X).
 Another rule, using the predefined predicate ">".

more_advanced(S1, S2) :-
year(S1, Year1),
year(S2, Year2),
Year1 > Year2.

Mathematical and Logical Operation

Mathematical Operations:
Operation Symbol
Addition +
Subtraction -
Multiplication *
Integer part of division div
Remainder part of division mod

Logical Operations:
Operation Symbol
Greater >

Gandhinagar Institute of Technology 3161608 AI

 Page No.

Less than <

Equal =
Not equal <>
Greater or equal >=
Less than or equal <=
Other mathematical function
Function Name Operation
Cos(X) Return the cosine of its argument
Sin(X) Return the sine of its argument
Tan(X) Return the tangent of its argument
Exp(X) Return e raised to the value to which X is bound
Ln(X) Return the natural logarithm of X (base e)
Log(X) Return the base 10 logarithm of log 10x
Sqrt(X) Return the positive square of X
Round(X) Return the rounded value of X. Rounds X up or
down to the nearest integer
Trunc(X) Truncates X to the right of the decimal point
Abs(X) Return the absolute value of X
Example: A prolog program that takes two numbers as integer and prints the greater.
Domains
I = integer

Predicates
greater(i,i)

Clauses
greater(X,Y):- X>Y,write(“the greater is”,X).
greater(X,Y):- write (“ the greater is “,Y).

Goal: greater(4,3).
Output: The greater is 4

Exercise:
1. Write a prolog program to create simple calculator using prolog.
2. Write a prolog program take as input 2 integers values and finds out the greater number.

Review Questions:

1. Which are the different operations in prolog?

2. What is the general syntax for defining a rule in prolog?
3. Which symbol is used to represent “if” in a rule?
4. Which symbol is used to end a fact?
Gandhinagar Institute of Technology 3161608 AI
 Page No.

Study of recursion in prolog

Practical No:_____________ Date:__________

Aim: To study how to implement recursion in Prolog.

Theory:
The recursion in any language is a function that can call itself until the goal has been succeed. In
Prolog, recursion appears when a predicate contain a goal that refers to itself. There are two types of
recursion:

1. Tail Recursion: is recursion in which the recursive call is always made just in the last step before
the procedure exits.
Example: Program to find factorial of 5.
Domains
I = integer

Predicates
fact(i,i)

Clauses
fact(1,F,F):- !.
fact(N,F,R):- F1=F*N,
N1=N-1,
fact(N1,F1,R).

Goal: fact(5,1,F).
Output: F=120

2. Non Tail Recursion: is recursion in which the recursive call is not the last step in the
procedure.
Example: Program to find factorial of 5.

Gandhinagar Institute of Technology 3161608 AI

 Page No.

Domains
I = integer

Predicates
fact(i,i)

Clauses
fact(1,F,F):- !.
fact(N,F,R):- N1=N-1,
fact(N1,F1),
F=N*F1.

Goal: fact(5,F).
Output: F=120

Tower of Hanoi

Figure 1 Tower of Hanoi

This object of this famous puzzle is to move N disks from the left peg to the right peg using
the center peg as an auxiliary holding peg. At no time can a larger disk be placed upon a
smaller disk. The above diagram depicts the starting setup for N=3 disks.

Here is a high-level outline of how to move a tower from the starting pole, to the goal pole,
using an intermediate pole:

1. Move a tower of height-1 to an intermediate pole, using the final pole.

2. Move the remaining disk to the final pole.
3. Move the tower of height-1 from the intermediate pole to the final pole using the original
pole.
Exercise:
1. Write a prolog program to print factorial of a number.
2. Write a prolog program to implement tower of hanoi.

Gandhinagar Institute of Technology 3161608 AI

 Page No.

Review Questions:
1. What is recursion?
2. Which are the types of recursion?
3. What is the role of recursion in Tower of Hanoi problem?

Gandhinagar Institute of Technology 3161608 AI

 Page No.

Study of GCD in prolog

Practical No:_____________ Date:__________

Aim: To study the use of GCD in Prolog.

Theory: The greatest common divisor (GCD) refers to the greatest positive integer that is a
common divisor for a given set of positive integers. It is also termed as the highest common factor
(HCF) or the greatest common factor (GCF).

For a set of positive integers (a, b), the greatest common divisor is defined as the greatest
positive number which is a common factor of both the positive integers (a, b). GCD of any two
numbers is never negative or 0 as the least positive integer common to any two numbers is always

1. There are two ways to determine the greatest common divisor of two numbers:
By finding the common divisors
By Euclid's algorithm

For a set of two positive integers (a, b) we use the below-given steps to find the greatest common
divisor:
Step 1: Write the divisors of positive integer "a".
Step 2: Write the divisors of positive integer "b".
Step 3: Enlist the common divisors of "a" and "b".
Step 4: Now find the divisor which is the highest of both "a" and "b"

Example: Find the greatest common divisor of 13 and 48.

Solution: We will use the below steps to determine the greatest common divisor of (13, 48).

Divisors of 13 are 1, and 13.

Divisors of 48 are 1, 2, 3, 4, 6, 8, 12, 16, 24 and 48.

The common divisor of 13 and 48 is 1.

The greatest common divisor of 13 and 48 is 1.

Thus, GCD (13, 48) = 1.

Exercise:

1. Write a prolog program to find GCD number.

Gandhinagar Institute of Technology 3161608 AI

 Page No.

Study of lists in prolog

Practical No:_____________ Date:__________

Aim: To study the use of list in Prolog.

Theory:

Notation
Lists are contained in square brackets with the elements being separated by commas.
Here's an example:
[elephant, horse, donkey, dog]

This is the list of the four atoms elephant, horse, donkey, and dog. Elements of lists could be any
valid Prolog terms, i.e., atoms, numbers, variables, or compound terms. This includes also other
lists. The empty list is written as []. The following is another example for a (slightly more
complex) list
[elephant, [], X, parent(X, tom), [a, b, c], f(22)]

Head and Tail

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.
A variant of the list notation allows for convenient addressing of both head and tail of a list. This
is done by using the separator (bar). If it is put just before the last term inside a list, it means that
that last term denotes another list. The entire list is then constructed by appending this sub-list to
the list represented by the sequence of elements before the bar. If there is exactly one element
before the bar, it is the head and the term after the bar is the list's tail.
In the next example, 1 is the head of the list and [2,3,4,5] is the tail, which has been computed by
Prolog simply by matching the list of numbers with the head/tail-pattern.
?- [1, 2, 3, 4, 5] = [Head | Tail].
Head = 1
Tail = [2, 3, 4, 5]
Yes
Note that Head and Tail are just names for variables. We could have used X and Y or whatever
instead with the same result. Note also that the tail of a list (more generally speaking: the thing
after) is always a list itself. Possibly the empty list, but denitely a list. The head, however, is an
element of a list. The same applies to all other elements listed before the bar in a list. This notation
also allows us to retrieve the, say, second element of a given list. In the following example we use
the anonymous variable for the head and also for the list after the bar, because we are only
interested in the second element.

Gandhinagar Institute of Technology 3161608 AI

 Page No.

?- [quod, licet, jovi, non, licet, bovi] = [_, X | _].

X = licet
Yes

Some Built-in Predicates for List Manipulation

Prolog comes with a range of predefined predicates for manipulating lists. Some of the most
important ones are presented here. Note that they could all easily be implemented by exploiting the
head/tail-pattern.
1. length:
Example:
?- length(List, 3).
List = [_G248, _G251, _G254]
Yes
2. member:
The goal member(Elem, List) will succeed, if the term Elem can be matched with one of the members
of the list List.
Example:
?- member(dog, [elephant, horse, donkey, dog, monkey]).
Yes
3. Concatenate:
Concatenate two lists.
Example:
?- concat_lists([1, 2, 3], [d, e, f, g], X).
X = [1, 2, 3, d, e, f, g]
Yes
4. reverse:
This predicate can be used to reverse the order of elements in a list. The first argument has to be a
(fully instantiated) list and the second one will be matched with the reversed list.
Example:
?- reverse([1, 2, 3, 4, 5], X).
X = [5, 4, 3, 2, 1]
Yes
5. select:
Given a list in the second argument and an element of that list in the first, this predicate will match
the third argument with the remainder of that list.
Example:
?- select(bird, [mouse, bird, jellyfish, zebra], X).
X = [mouse, jellyfish, zebra]
Yes
6. analyse:
?- analyse_list([dog, cat, horse, cow]).
This is the head of your list: dog
Gandhinagar Institute of Technology 3161608 AI
 Page No.

This is the tail of your list: [cat, horse, cow]

Yes
?- analyse_list([]).
This is an empty list.
Yes
?- analyse_list(sigmund_freud).
No
7. remove duplicates:
?- remove_duplicates([a, b, a, c, d, d], List).
List = [b, a, c, d]
Yes
8. replace:
?- replace([1, 2, 3, 4, 3, 5, 6, 3], 3, x, List).
List = [1, 2, x, 4, x, 5, 6, x]
Yes

Exercise:
1. Write a prolog program to print the contents of a list.
2. Write a prolog program to input integer numbers in the list.
3. Write a prolog program to find the sum of integer list.

Review Questions:
1. How many components are present in a list?
2. Which method is used to append two lists?
3. Which method is used to print the contents of list in opposite direction?

Gandhinagar Institute of Technology 3161608 AI

 Page No.

Study of water jug problem in prolog

Practical No:_____________ Date:__________

Aim: To study how to implement water jug problem in Prolog using BFS.

Theory:
Statement :- We are given 2 jugs, a 4 liter one and a 3- liter one. Neither has any measuring
markers on it. There is a pump that can be used to fill the jugs with water. How can we get exactly
2 liters of water in to the 4-liter jugs?

Solution:-

The state space for this problem can be defined as

{ ( i ,j ) i = 0,1,2,3,4 j = 0,1,2,3}

‘i’ represents the number of liters of water in the 4-liter jug and ‘j’ represents the number of liters
of water in the 3-liter jug. The initial state is ( 0,0) that is no water on each jug. The goal state is
to get ( 2,n) for any value of ‘n’.

To solve this we have to make some assumptions not mentioned in the problem. They are

1. We can fill a jug from the pump.

2. We can pour water out of a jug to the ground.
3. We can pour water from one jug to another.
4. There is no measuring device available.
The various operators (Production Rules) that are available to solve this problem may be
stated as given in the below figure.

Gandhinagar Institute of Technology 3161608 AI

 Page No.

Figure1. Production rules for water jug problem

There are several sequence of operators that will solve the problem.

Figure2. Solution 1 for water jug problem

Gandhinagar Institute of Technology 3161608 AI

 Page No.

Figure3. Solution 2 and 3 for water jug problem

When no limit for water prevails then solution-1 is most efficient. When water is limited then
solution-2 is the best suited. In no way, solution-3 is good because it requires 8 steps and wastes
5 liters of water.

Exercise:
1. Write a program to implement BFS for Water Jug Problem
Review Questions:
1. What is the importance of BFS?
2. Which solution is most efficient for solving water jug problem? Why?
3. What is state space?

Gandhinagar Institute of Technology 3161608 AI

 Page No.

Study of N-queens problem in prolog

Practical No:_____________ Date:__________

Aim: To study how to implement N-Queens problem in Prolog.

Theory:
We shall consider the example of 8-queens problem. The objective is to place eight queens on a
chessboard such that no queen threatens another. A queen threatens another queen in the same row,
column or diagonal.

Figure1. 8-queens problem

In this example, the two queens on the corners are the only queens threatening each other.
The states and operators for this problem could be:

 States: any arrangement of 0 to 8 queens on the board.

 Operators: add a queen to any square.
This is a bad choice because there are 64^8 possible sequences to investigate.
A better formulation would be to choose a smarter operator: that

 States: any arrangement of 0 to 8 queens on the board.

 Operators: place a queen in the left-most empty column such that it is not attacked by any
other queen.
Now there are only 2057 possible sequences to investigate.
Algorithm:

Gandhinagar Institute of Technology 3161608 AI

 Page No.

STEP 1 : Represent the board positions as 8*8 vector , i.e., [1,2,3,4,5,6,7,8]. Store the set of
queens in the list ‘Q’.
STEP 2 : Calculate the permutation of the above eight numbers stored in set P.
STEP 3 : Let the position where the first queen to be placed be (1,Y), for second be (2,Y1) and
so on and store the positions in Q.
STEP 4 : Check for the safety of the queens through the predicate , ‘noattack ()’.
STEP 5 : Calculate Y1-Y and Y-Y1. If both are not equal to Xdist , which is the X – distance
between the first queen and others, then go to Step 6 else go to Step 7.
STEP 6 : Increment Xdist by 1.
STEP 7 : Repeat above for the rest of the queens , until the end of the list is reached.
STEP 8 : Print Q as answer.
STEP 9 : Exit.

Exercise:
1. Write a program to solve 8-Queens problem using Prolog.

Review Questions:
1. What is backtracking and why it is required?
2. What is state?
3. What is operator?

Gandhinagar Institute of Technology 3161608 AI

 Page No.

Study of 8 puzzle problem in prolog

Practical No:_____________ Date:__________

Aim: To study how to implement 8 puzzle problem in Prolog.

Theory:
The 8-puzzle is a smaller version of the slightly better known 15-puzzle. The puzzle consists of an
area divided into a grid, 3 by 3 for the 8-puzzle, 4 by 4 for the 15-puzzle. On each grid square is a
tile, expect for one square which remains empty. Thus, there are eight tiles in the 8-puzzle and 15
tiles in the 15-puzzle. A tile that is next to the empty grid square can be moved into the empty space,
leaving its previous position empty in turn. Tiles are numbered, 1 thru 8 for the 8-puzzle, so that each
tile can be uniquely identified.

The aim of the puzzle is to achieve a given configuration of tiles from a given (different) configuration
by sliding the individual tiles around the grid.

Figure1. 8 puzzle problem

Searching for a Solution

This problem can be solved by searching for a solution, which is a sequence of actions (tile
moves) that leads from the initial state to the goal state. Two possible states of the 8-puzzle are
shown in Figure1. The state on the right is a typical goal state. The state on the left is a
configuration that represents a worst case: transforming this state into the goal state requires at

Gandhinagar Institute of Technology 3161608 AI

 Page No.

least 31 actions, which is the diameter of the search space. For search algorithms the problem is
often to find the shortest solution, that is, one which consists of the least number of tile moves.

The problem is how do you make the computer order the moves intelligently to find the shortest
path to the winning game state? Solving a problem such as this can be done two ways:

 Guess through every possible state by doing a blind search of the state space.
 Implement a search operation that is guaranteed to find the shortest solution using
"informed methods" (How?).

Exercise:
1. Solve the program for the sequence (8,7,6,5,4,1,2,3,0)
Review Questions:
1. What is 8 puzzle problem?
2. What can be the next states if the board is in following position?
1 2 3

8 4

7 6 5

Gandhinagar Institute of Technology 3161608 AI

 Page No.

Study of travelling salesman problem using Prolog

Practical No:_____________ Date:__________

Aim: To study how to implement travelling salesman problem using Prolog.

Theory:
The travelling salesman problem (TSP) asks the following question: "Given a list of cities and the
distances between each pair of cities, what is the shortest possible route that visits each city exactly
once and returns to the origin city?"

The following is the simplified map used for the prototype:

Figure1. Simplified map

Even though the problem is computationally difficult, a large number of heuristics and exact
algorithms are known, so that some instances with tens of thousands of cities can be solved completely
and even problems with millions of cities can be approximated within a small fraction of 1%.

The TSP has several applications even in its purest formulation, such as planning, logistics, and the
manufacture of microchips. Slightly modified, it appears as a sub-problem in many areas, such
as DNA sequencing. In these applications, the concept city represents, for example, customers,
soldering points, or DNA fragments, and the concept distance represents travelling times or cost, or
a similarity measure between DNA fragments. The TSP also appears in astronomy, as astronomers
observing many sources will want to minimize the time spent moving the telescope between the
sources. In many applications, additional constraints such as limited resources or time windows may
be imposed.

Gandhinagar Institute of Technology 3161608 AI

 Page No.

TSP can be modeled as an undirected weighted graph, such that cities are the graph's vertices, paths
are the graph's edges, and a path's distance is the edge's weight. It is a minimization problem starting
and finishing at a specified vertex after having visited each other vertex exactly once. Often, the model
is a complete graph (i.e. each pair of vertices is connected by an edge). If no path exists between two
cities, adding an arbitrarily long edge will complete the graph without affecting the optimal tour.

Exercise:
1. Write a prolog program for solving travelling sales problem consisting of 4 cities.

Review Questions:

1. What do you mean by Traveling Salesman problem?2.

2. Why you use domain?
3. What is the output of following:
route(kansascity, gordon, X)).

Gandhinagar Institute of Technology 3161608 AI