Stai1t ú ucd to sove C

Sp
duliuis

Problem Solving Through AL

2.1 INTRODUCTION
: the science
that ArtificialIntelligenceis
Inthe last chapter, we have triedto explain intelligent. The ultimate aim of
and technology applied to make machines match the intelligence
to
researchers is to develop universal intelligent system has been made and!
capabilities of human beings. In this regard, lot of progress
achieved. although, universal intelligent
considerable amount of success has been AIina limited
have developed techniques to use
system is still adream. Scientists developed many Al systems, which work ina
have successfully
domain and
domain and show expertise not only matching those of human
problem specific many ways and in many
applications. It should
experts, but also exceeding those in the most important application
ofAI is to
mind that for the time being, otherwise take
be kept in solvereal world problems, which
develop intelligent systems to human efforts, and hence, become uneconomical
considerable amount of time and major area of
as inefficient at times. Hence, problem solving becomes solving
as well
involves methods and various techniques used in problem
study, which
using AI. methods of solving real world problem3
we will discuss the
In this chapter, In realI world, there are different types
Artificial Intelligence(AI)techniques.
various characteristics of problems and their
using A We will try to explain
of problems.
solution methodologies. through AI invo!ves the process of defining
method of solving problem goal states and
The start and then finding the path from
searçh space, deciding search space. The movement from start state to
the through
start state to
goal state specifically designedIfor that
particular problem
guidedby settofrules
state is production rules). The production rules are nothing but valid
goal called
(sometimes problems.
Letdescribed bythesometermsrelatedIwith Al problem solution mnethodology:
usfirst discuss
moves
question which is to be
It is the to precisely
problemitneeds bestart
solved. For solving
Aroblem defining,the state, defined.
goal
The definition
means,
states andtransitions. state, other valid
 Problem Solving Through AI 29

Seanhspace: It is the complete set of states including start and goal

states, where the answer of the problem is to be searched.
Sereh:
Itis the prÍcess of finding the solution in search space.
The input to scarch space algorithm is problem and
output is solution in form of action sequence.
problem description has three major components.
Hel definedproblem: A Initial state, final state, space includingtransition
function or path function. A path cost function assigns
some numericvalue to cach path that indicates the
g0odness of that path. Sometimes aproblem may have
additional component in form of heuristic information.
initial staté:
oution ofthe problem: A solution of the problem is a path from
goal state. The movement from start states to goal states
is guided by transition rules. Among all the solutions,
whichever solution has least path cost is called optimal
solution.

Hence,it is evident that the method of solvingproblem throughAl techniques

about start and goal
involves the process of defining the search space, decidingthrough search space.
state and then finding a path from start state to goal stato
guided' by transition rules or
The movement from start state to goal state is different start states,
production rules. After designing the search spce involvingsearched. The search
solution needs to be
goal states and transition arcs, the
way from start to goal state.
techniques are the mèthods which are used to find a
Thus, to buiid an Alcomputational system tosolve a particular problem the
föllowing activities are needed to be performed: must include precise
Define the problem precisely. This definition problem.
specifications of initial states and final states of thefeatures of the problem
abstracts the salient
2 Analyze the problem. This phase various possible
the appropriateness of
that can have an immense impact on
techniques used for solving the problem.
knowledge that is necessary to solve the
lsolate and represent the task
problem. and apply it to the particular
Choose the best problem solving technique
problem.

Now let us discuss these steps in detail.

Defining Problem as State Space Search

AI, the representatjon and definition of problem plays a key role. The and
selection about state representation,
Sentation of the problemn requires representation is guided by specific
eSponding knowledge representation. The from the computational viewpoint.
ventions, which also judge itssuitability
30 Artificial lntelligence
exposing description. Every
The good representations support explicit constraint
limitations. The representation should
practical problem has certain constraints or problems,oneshoula
clearly highlightthese constraints. For representation ofsome
Some features of go0d
irrelevant details.
look for desired data and should avoid
representation are given below:
and relations between
1. Good representation captures the important features
them completely. relations
It should be able to express the
L. They expose natural constraint.
between different objects.
3. They bring objects and relations together.
problem. The rarely used details
They suppress irrelevant details of the
kept out of sight, but one should be able to get them when necessary.
are features
one can understand the salient
S. They are [Link] is.
represented by them immediately.
able to represent all aspects 0> the
6. They are complete. They should be
problem.
efficiently and concretely should say
7. They are concise. That means, they
whateveris to be specified. allow
computational viewpoint. They should
8. They should be suitable frominformation.
fast storage and yetrieval of minimumn memory.
9. Their, storage should consume
should be able to create them with
10.: They should be computable, i.e: one
an éxisting procedure.

2.1.2 Analyzing the Problem salient

problemin detail and capturing, its
This activity requires analyzing the type of problems, the solution or the selection
features, e.g., in the game playingvisualizing the opponent'smove also; or in the
of winning move must include the cost of each path etc. Besides
this. the
path finding problems, it should see include the analysis of syntactic and
natural language processing
applications
analysis phase performs complete analvsie
semantic details of the input. Hence, the
of the problem.
Task Oriented Knowledge
2.1.3 Isolating the
earlier,thesolution oofa problemrequires the availability ofrelated
As is mentioned problem the knowledge related to problem field
Hence for solving a format.
knowledge. As the nature of AI
represented in asuitable applications
and knowledge and there
is isolated accordingly so, the types of representation
varies widely, queens problem willrequire storage of only position of queens
únderstanding
board,
a8
techniques, e.g.,whereas a natural language the words/
details of
application
/grammars
will require
etc. Further, the
onthe andsemantic require storageof large
syntactic
storingthe application will Various amount of medical
correspondingdiagnosis.
medical diagnosis knowledge representation (KR)
'syimptomsand
 Problem Solving Through A1 31
techniq1uCs arc deviscd for this phase. Thesc KR mcthodologies havc their
respectiveadvantages andIdisadvantages, and spccific techniques arc suitable for
Speclticapplications. Various KR (cchniqucs arc described in detail in following
chsplers.
214Finding the Solution
represcntation ofthe problem and related knowledge in the suitable format,
Atler methodology is chosen which uscs theknowlcdge andtrans forms
thegppropriate finding the solution are called search
he sart state to goalstate. The techniquesareofdevelopcd for this purpose. They are
tcchniqucs. VàVarious scarch tcchniques
sections and also in next chapter.
deal-witlhin detail in onc of the following
22REPRESENTATION OF AI PROBLEMS
representation
wc would learn the technical aspects of problem representation
In this scction, From this orientation,the
reauircd from computational perspective,
nfAIDroblems can be coveredin folloWing föur symbolsparts: eda, vaablay
are allowd in the
1.4 lexical part: that determincs which meaning of the lexicon,
representations of the problem. Like the normal problem.
features of the
this part abstracts all fundamental constraints on how the, symbols can be
2,.A structural part: that describes
out possibilities requircd for joining
aranged. This corrcsponds to finding structural unit.
thesc synnbols and generating higher procedures that enable to create
procedural part: that specifies access
3.4 questions using them.
descriptions, to modify them, and to answer associating meaning with the
4. 4 senantic part: that
establishes a way of
deseriptions.
ancxample presented below: problem, we
Let usunderstand thesc steps by "playing chess". To define the
givcn thc problem of legal
We arc
starting position of chess board, the rules that define theothers.
Should spccify the the
that represent a win for one side or
moves and the board positions
Here, the:
contains the board position, which may be an 8 x 8 array
1 Lexical part symbol indicating an appropriate
chess piece
where cach position contains a position. The goal is any board position in
in the oficial chess opening have a legal move and his king in under attack.
which opponcnt does not the
part describes the legal moves. The legal moves provide as
The structural They are described
getting from an initial statc to a goal state. to be
Way of
consisting of a left hand side that serves as a pattern
set of nules
current board position and a right hand side that
matched against the board position to reflect the
move.
changes to be made to
describes rule for
procedural part will be methods for applying appropriate moves"
The representing the "sct of winning
Winning the game. It will include
 Problem Solving Throngh A1 31
techniquCs arc deviscd for this phase. These KR ncthodologics havd thcir
espectivcadvantages and disadvantages, and spccific techniques arc suitable for
Speolic
capplications. Various KR tcchniques are describcd in detail in following
chaplers.
Solution
214 Findingthe
ARerreprescntation of thc problcm, and related knowlcdge in the suitable format,
tho appropriate methodology is choscn which uses the knowlcdge andtransforms
thesfart stateto gol state. The techniques of finding the solution are called scarch
techniqucs. Various scarch techniques are developed for this purpose. They are
deal-within detail in onc of the following scctions and also in next chapter.

22REPRESENTATION OF AI PROBLEMS
Innhis scction, we would learn the techrnical aspects of problem representation
reaured fromcomputational perspcctive. From thisorientation, the representation
ofAl problems can be covercd in following föur parts: od VaLa sulay
1lexical part: that determineswhich symbols are allowd in the lexicon,
Teprescntations of the problem. Like the normal meaning of the
this part abstracts all fundamental fcatures of the [Link] can be
how the,
2 4 structural part: that describesconstraints on joining
arranged. This corresponds to finding out possibilities required for
these symbols and generating higher structural unit.
procedural part: that specifies acccss procedures that enable to create
A
descriptions, to modify them, and to answer questions using [Link] the
4A senantic part: that establishes a way of associating meaning
descriptions.
below:
Letus understand these steps by an cxample presented
define the problem, we
We arc given the problem of "playing chess". Torules that define the legal
the
shöuld spccify the starting position of chess board,
a win for one side or the others.
moves arnd the board positions that represent
Here, the:
which may be an 8 x 8 array
US Lexical part contains the board position, appropriate chess piece
where cach position contains a symbol indicating an
goal is any board position in
in the ofilicial chess opcning position. The
move and his king in under attack.
Which opPponent does not have a legal
moves. The legal moves provide the
2 The structural part describes the legal
goal state. They are described as
Way of getting from an initial state to a
that serves as a pattern to be
set of nules consisting of a left hand side
and a right hand side that
matched against the current board position
the move.
describes changes to be made to board position to reflcct
applying appropriate rule for
Ihe procedural part will be methods for winning moves
Winning the [Link] include representing the "set of
32 Artificial Intelligence

of standard chess playing. Out of all legal moves, only those moves, whio
bring the board position to a winning position of respective playerad
captured and stored in proccdural part.
However, in chess the total 'legal moves' are of the order of 10
Such a large number of moves are difficult to be written, so only 'usef:
moves' are written. should be noted that there is a difference betwee
legal moves and useful moves. The legal moves are all those moves whic
are permissible according to game rules and useful moves will be those
legal moves which bring the game in a winning position. Hence the usefi
moves' will be a subset of legal moves'. The state space is total vald
states possible in a problem and finding a problem solution is "starting a
an initial state, using a set of rules to move from one state to another and
attempting to end up in one of a set of final states."
4. The semantic part is not required in "chess game" because, there is no
hidden meaning associated vwith any piece and all the move meanings are
explicit. However in natural language processing type of applications,where
there is meaning" .associated with words and "complete message
associated with sentence, the semantic part captures and stores, the meaning
of words and message conveyed by sentence.

Thus, in AI, to design a program for solution, the first step is the creation ofa
formal and manipulable description of problem itself. This includes performing
following activities:
A. Define a state space that contains all the possible configurations of the
relevant objects.
2. Specify one or more states within that space, which describe possible
situations from which problem solving process may start. These are called
initial states.
Specify one or more states that would be acceptable as solutions to the
problem. These are called goal states.
4. Specify a set of rules that describes the action (operators) available

PRODUCTION SYSTEM
Lo fhe above section, we have discussed basic aspects of Alproblem solution A
AI system developed for solution of any problem is called production system.
Once the problem is defined, analyzed and represented in a suitable formalism,
the production systemis usedfor application of rules and obtaining the solution.
of following componentg:
Aproductionsystem consists
rules, which are of the form
1. ofAset of production
a left hand side constituentthat P’Q.
represents the current Each rule state and
problem consists
aright hand side that represents a result or generated output state. Arule is
side matches with the current
applicable if its left hand
the left side of the rule determines the applicability problem state,andThus,
of the ule the
output, if rule is applied. It is
describes the
ight sidethat important to note
 Problem Solving Through A1 33

therc may be nultiple constitucnts on the left hand side of arule (i.e.
hat2....P). In this situation, all constituents of lcft hand side should
be satisficdfor applying
the rule. After applying the rule, the left hand side
nule becomes the current state.
o the
Qne or more knowledge/data bases, that contain all the appropriate
sformation for the particular task. Some parts of the database may be
pemancnt while some part of this may pertain only to the solution of
structured in
Cuent problem. The information in these databases, may be
an appropriate way.
2control strategythat specifies order in whjh the rules will be compared
the database of rules and a way of -résolving the conflicts that arise
when several rules match simultaneously.
current
Aruleapplier, which checks the applicability of rule by matching the
rule from
state with the left hand side of the rule and finds the appropriate
the database of rules.

2.3Salient Features of Production Rules

solution of a
ASmentioned above, a set of rules is applied for findingappropriate
system. Some of the main
[Link] rules are important part of production
follows:
feaures of production rules are described as situation is
world, many times a
1. Expressiveness and intuitiveness: In real will do this, if this is so - then
encountered, which"sáyshishappens -I
essentially tell us what to do in
this should happen. The production rules be coded in IF-THEN foYmt
situation can
agiven situation. This type of
rules in IF-THEN type of
of atructures. The representing and coding of
applications and the rules of almost all
structures is quite common in Al
systems are coded in this way.
types of expert systems and rule-based coding structure of
IF- THEN- ELSE'
2. Simplicity; The uniform structure of This
in knowledge representation.
rule based system provides simplicityproduction rules and communiation
feature inmproves the readability ofprogräm:
between various parts of a single
[Link],production ules code the
3 Modularity and modifiability: pieces. In real world, the knowledge is
knowledge available in discerete coding in modular form suits very
available in discrete pieces hence, their
collection of independent facts which
much. Informátion can be treated as a
added or .déleted from the system with essentially no deleterious
may be modifying the rule. The
facility of
side effects. Modifiability stands for thethe devèlöpment öf prödütion n1les
modular and modifiable features allow is "fine tuned" to suit a specific
then it
In a block or skeletal form first and systems having a large number of
application. In case of similar. expert
beborrowed or copied and
production rules, the basic production rules can suit to another application.
to
they can be molded in a tailo-made fashion required to develop a new
Hence, it will reduce the amount of efforts
database.
34 Artificial Intelligence

4. Knowledge intensive: The knowlcdge base of production system store

exlensive andpurc knowlcdge. This part contains no control or programmi
information. The problem of semantics is resolved by representing t
knowledge in propcr structure.
5. Opacity: Along with the advantages, there are certain disadvantages als
generated b
associatd with production systems. Opacity is the problem rul
combination of production rules. Though, the individual production
and effects of contro
may be models of clarity, the combined operation
generated because of les
program may be opaque. The opacity is
prioritization of rules.
O. Ineficiency: Sometimes, several of the rules become active during execution
As the rules o
A well devised control strategy reduces this problem.
written n
production system are large in number and they are hardly
hierarchical manner, it requires exhaustive search through all the proaucuon
rules for each cycle of control program. It makes the functioning inemclen
does no
7. Absence of learning: The simple rule based production systemdoes not exhibit
store the results of computations for later use. Hence, it
any type of learning capabilities.
haVe
8. Conflict Resolution: The rules in ideal production system should notshould
database
any type of conflict. The new rule whenever added in the Besides
ensure that it does not have any conflict with the existing rules.
applied
this, there may be more than one number of rules that can be
(typically called fired) in one situation. While choosing the rule also, the
conflict should not happen. If conflict is found, it should be resolved in
following ways:
() Assign priority to the rules and fire the rule with the highest priority:
This method is used in many expert systems. Its virtue lies in its
.. simplicity, and by ordering the rules in the approximate order of their
firing frequency. This can be made using arelatively efficient strategy.
(i) Use a longest matching strategy. This means that fire a rule having largest
number of matching constraints. Its advantage is that the discrimination
pOwer of a strict condition is greater than of amore general condition. A
rule with more constraints provides more knowledge.
) Choose most recently used rule tor firing. Its advantage is that i
represents adepth first search, which tollows the path of greatest activity
Production System
2.3.2 Characteristics of
some of the main characteristics of
Now. let us describe
storage in computer production system from
the aspect of their system. The production Systems can be of
various types, but the most popular production system is monotonic system. A
production
monotonic production system i_ a
one rule never prevents the later application ofsystem
in which the
another rule. application
The characteristics of
of
presented below:
production systems arc
 Problem Solving Through Al 35
Datastructure: Afler defining the problcm, it wil| be required to be
prescntedin asuitable data structure. The data structures best suited for
Latitional problems arc grapl1s and trees. Nodes in the graph correspond
problemstate and arcs betwccn nodes correspond to valid transitions,
Cg.,inan
8-puzzle problem, various different states derived from asingle
Sate will be put as children of that state. While searching for the solution,
thegraph somctimcs nceds to be converted into trce. The directed graph
converted into tree. There is a special type of tree
cannot always be
Teprescntation called AND Or graph which is used in Al problem. It will
be described in detail later on in this chapter.
the representation of
To apply the Al problem solving algorithms, application of operator
problem/data is done in problemrepresentation, and discusses
The following section
done using variOus control strategies.
these control strategies.
Control Strategies: These are also called search strategies. Controlstrategies
D
applying the rules and searching the problem solution in
are adopted for mentioned earlier that the' control strategy is
Search space. It is already
the problem. Hence, if the wrong
TeSponsible for obtaining the solutionbeof possible that a solution is never
may
Control strategy is applied, it salient characteristics of control strategies
obtained, even if it [Link]
are described below: should cause
requirement of good control strategy is thatmovement of the
The first whenever we apply a rule the solution. In real
motion. It means that
should be in the direction of obtaining the rule. In
problem associated with application ofa
effort
practice, there is a cost or does not cause motion, the efforts
will
the rule
case the application ofwhether the application of an operator moves the
go as waste. To check solution, it is checked that the operator
the
problem in the direction of state as any previously generated states.
output
should not generate the cyle, e.g. in a water-jug problen, if we
Otherwise, it will create a gallon jugand then emptying 4 gallon jug.
filling 4
choose operator forchoose create cycle
same sequence of operator, it will operator
Next time alsowe sequenceof
solution. Again,'some
and will never
generate the
jug first, and applying thè first applicable
4 gallon
always startwith fillingnever obtain the solution. systematic method
it, we will
operåtor on
systematic. That means there should be
(1) It shouldbe application.
to select a rule for
detail, in one of
strategies. These are described in
ontrol
Ihere are various "search strategies".
ecoming sections, known as
SOLVING
ALGORITHM OF PROBLEM
widely, and accordingly, their solution
varies
nough, the nature ofAl
problems
Hence, any onè algorithm for problem solution
methodologies are of varyingtypes.
 36 AFrificial Intelligence
S not applicable over all types of problems. However, in a very crude and
enentary
u
format, the algorithm for problem solving can be represented as tollo
Algorithm: "problem name"
noose data about start state, goal state and production rules from inteal
database.
Ontil the goal state is achieved (or solution can not be achieved and
operators are exhausted), do the following:
V3. Begin
. Select some rule from the set of mles that can be applied to data.
. Note new state generated after the application of the rule. Make this a
current state.
6. End.

2.5 EXAMPLES OF AI PROBLEMS

This section discusses some common AI problems. Though we
number of problems here, it present larg
should be noted that the applications of AI are not
limited to only these problems and there may be many other problems where Al
can be applied. Som of the popular problems are discussed in the following
subsections:

A51 Tic-Tac-Toe
Tic-Tac-Toe is a game involving two players. It is played by putting 'X' or 'O
alternately by two players, in any oneof the 9 board positions shown as follows
Playing means making the mark of X' or "0° in any one square. The player who
is able to make his marks in horizontal, vertical, or diagonal straight line first, is
declared [Link].
From AI viewpoint, the problem of playing Tic-Tac-Toe will be formulated as
follows:
The start state is all blank squares out of 9 squares. Player I can play in any
one square. As the game proceeds, blank squares remain the choice,which can
marked by the players. The data structure used to represent the board is a 9-elema
vector, with element positions shown in Fig 2.1:

2 3

4 5 6

7 8 9

Fig 2.1; Element positions of TIC-TAC-TOE

 Problem Solving Through Al 37
Boarddposition: -{1,2,3,4,5,6,7, 8,9}
clement contains the value 0, if the
iledwith"O" and 2, if it is filled with "X". corresponding square is blank; 1, if it
Hencestarting stateeis {0,0,0,0,0,0,0,0,0)
hegoal|statc or winning combination will be board position having "0" or
in
Xeparately the combination of ((1,2,3}, (4,5,6}, (7,8,9},(1,4,7),(2,5,8},
o09). {1.5,9}, { 3,5,7}) element values. Hence two goal states can be
1,2,0,0,0,2} and {2,2,2,0,1,0,1,0,0}. These values correspond to the goal
Sates shown in the figure.
The start and goal state are shown in Fig. 2.2.

X X X X

6 X

4 X

(a) Start State (b) Goal State-1 (c) Goal State-2

Fig 2.2: Start and goal states of TIC-TAC-TOE

Any board position satisfying this condition would be declared as win for
coesponding player. The valid transitions of this problem are simply putting 1
or2 in any of the element position containing 0.
In practice, all the valid moves are defined and stored. While selecting amove
itistaken from this store: In this game, valid transition table will be a vector
(haying 3° entries), having 9 elements in each.

252_Water-Jug Problem
This problem is defined as:
"We are given two water jugs' having no measuring marks on these.
The capacities of jugs are 3 liter and 4 liter: It is required to fill the
bigger jug with exactly 2 liter of water The water can be filled in
a jug from a tap".
In this problem, the start state is that both jugs are empty and the final staté is
tiat 4-liter jug has exactly 2 liters of water. The productionrules involve filing a
Ug with some amount of water, filing the water from one jug to other or emptying
lie jug. The search will be finding the sequence ofpróduction rules which transform
lie initial state to final state.
Part of search tree of water jug problem is shown in Fig. 2.3.
 38 Artificial Intelligence

0,0

4,0 0,3

1,3 4,3 3,0 4,3

0,3 1,0
Fig 2.3: Partial search tree of water jug problem

ordered pairs of
The state space for this problem can be described by set of
the 4-liter jug, andy
twovariables (x, y) where, variable x represents the water in
value 0, 1, 2, 3,4
represents the water in the 3-liter jug. Variable x can take the
and the goal
and variable y can take the value 0, 1, 2, 3. The start state is (0, 0)
follows:
state is (2, 0). The production rules are formulated as

(fill the 4-liter jug, applicable ifx<4)

Rule 1 : (x, y) ’ (4, y) (fill the 3-liter jug, applicable if y<3)
Rule 2 : (x;y) ’ (x, 3)
sone Rule 3 : (x, y) ’ (*-x1; y) (pour Some water out from 4-liter jug)
Rule 4 (x,y) ’ (x,y-x1) 9z (pour some water out from 3-liter jug)
Rule 5 : (x, y) ’ (0, y):no (empty the 4-liter jug )
ea-Rule 6: (x, y) ’ (x,0) 520 (empty the 3-liter jug)
KRule 7 (x. y) ’ (4, y-(4-x)) (ill the 4-liter jug by pouring some water
from 3liter jug)
Rule 8 : (x, y) ’ (x-(3-y), 3) (fill the 3-liter jug by pouring some water
from 4-liter jug)
Rule 9 : (x, y) ’ (x+ y, 0) (empty 3-liter jug by pouring all its water in
to4-liter jug)
(0,x+y) (empty 4-liter jug by pouring all its water in
Rule 10:(x,y) ’ to 3-liter jug)
(pour the2 liters from 3-liter jug into 4- liter
Rule 11: (0, 2)’ (2, 0) jug)
1?: (2, y) ’ (0, y)
(empty the 2 liters in the 4-liter jug on the
Rule ground)

These,are set of rules, which can be applied to solve water-jug problem.

Soluion ofthe problem will include applying appropriate rules in the specific
 Problem Solving Through Al 39
sCquenceto transform
the start state to goal
state. One solution is applying the
the sequence 2,9, 2, 7, 5, 9. The solution is presented in the following
Tble 2.1.

TAble 2.1: Production rules applied in Water-Jug problem

Rule applied Water In 4-liter Jug Water In 3-iter jug
Start state
2 3
3
N 3 3
7 4 2
5 2
2

2538-Puzzle Problem
The&-puzzle problem belongs to the category of"sliding-block puzzle" types of
problems. It is described as follows:
It has set of a 3x3 board having 9 block spaces out of which, 8
blocks are having tiles bearing number from I to 8. One space is
left blank. The tile ádjacent to blank space can move into it. We
have to arrange the tiles in asequence.
The start state is any situation of tiles, and goal state is tiles arranged in
specifi sequence. Solution of this problem isreporting of "moveiment of tiles"" in
order to reach the goal state. The transition function or legal move is any one tile
movement by one space in any direction (i.e. towards left or right or up or down)
ifthat space is blank. It is shown in following Fig: 2.4:

1 4 2 3

6 5 4 5 6

2 3 7 7 8

(a) Start state

(b) Goal state
Fig. 2.4: Start and Goal states of 8
puzzle problem
40. Artificial Intelligence
indicatino
Here the data structure torepresent the states can be 9-element vector
to above
the tiles in cach board position. Hence, a starting state corresponding fferent
configuration will be {1, blank, 4,6, 5, 8, 2, 3, 7} (therc can be various dipossible
Here, the
start positions). The goal state is {1, 2, 3, 4, 5,6, 7, 8, blank}. represented ag
movement outcomes after applying a move can be many. They arc
depend upon the
tree. This tree is called statespacc [Link] depth of thetree will
8-puzzle is shon
number of steps in the [Link] part of state space tree of
in Fig 2.5.

6 5 8

2 3 7

1 1 5 4 4

6 5 8 6 6 5

2 7 3 7 2 3 7

6 4 4 ’ Cycle.
5 6 5 8

2 3 7 2 3 7

Fig 2.5: Partjal search tree of 8-puzzle problem

2.5!4'8-Queens Problem
This problem is presented as follows:
"We have 8 queens and a 8'x 8chessboard having alternate black
and white squares. The queens are placed on the chessboard. Any
queen can attack any another queen pldçed on same rowy, or column.
of diagonal. We have tofind the proper placement of queens on the
chessboard in such a way that no queen attacks other queen",
The 8-queen problem is shown in following diagram:
 Problem Solving Through A1 41

Fig 2.6: Apossible board configuration of 8 queens

problem

2.55 Chess Problem

Itis a nomal chess game. In a chess game problem, the start state is the initial
configuration of chessboard. The final or goal state is any board configuration,
which is a winníng position for any player (clearly, there may be multiple final
Dositions and each board configuration can be thought of as representing astate of
the game). Whenever any player moves any piece, it leads to diferent state of game.
Ttis estimated that the chess game has more than 1020 possible states. The
game playingwoukd mean finding (or searching) asequence of valid moves which
bring the board from start state to any of the possible final states.
The start state of chess game is shown in Fig 2.7.

2,56 Missionaries and Cannibals Problem

The problemis stated as follows:
Black

7||t||
6

a b d
White
C 9 h
Flg 2.7: Start state of chess game
42 Artificial Intelligenece
"Thnee missionaries and three connibals are present at one side of
available.
ariver and need to crOSs the river: Ther is only one boat
not outnumber
Atany' point of time, the mmber of cannibals should
known that only
the mumber of missionaries at that bank. It is also
nvopersONS can ocCupy the boat available at a time.
from one
The objective of the solution is to find the scquence of their transter
these
bank of river to other using the boat sailing through the river satisfying
constraints.
We can fom various production rules as presented in water-jug problem. Le
Missionary is denoted by 'M' and Cannibal, by '[Link] rules are described
below:
bank-2
Rule I: (0, M) One missionary sailing the boat from bank-1 to
Rule 2: (M, 0) On missionary sailing the boat from bank-2 to bank-l
Rule 3: (M, M) Two missionaries sailing the boat from bank-1 to bank-2
Rule 4: (M, M) Two missionaries sailing the boat from bank-2 to bank-1
Rule 5: (M, C) One missionary and one Cannibalsailing the boat from
bank-l to bank-2
Rule 6: (C, M) One missionary, and one Cannibal sailing the boat from
bank-2 to bank-1.
Rule 7: (C, C) TwoCannibals sailing the boat from bank-1 to bank-2
Rule 8: (C, C) Two Cannibals sailing the boat from bank-2 to bank-1
Rule 9: (0, C) One Cannibal sailing the boat fom bank-1to bank-2
Rule 10: (C,0) One Cannibal sailing the boat from bank-2 to bank-1
All or some of these production rules will have to be used in a particular
sequence to find the solution of the problem. The rules applied and their sequence
ispresented in the following Table 2.2.

Table 2.2: Rules applied and their sequence in Missionaries and Cannibals problem
After application persons in the persons in the boat position
of rule river bank-1 river bank-2

Start state M, M, M, C,C, C

bank-1
5 M, M, C,C M,C
2 M, M, C, C, M C
bank-2
7 M, M, M C, C, C
bank-1
10 M, M, M, C C,C bank-2
M,C C,C, M, M bank-1
M, C, C, M C, M bank-2
C,C C, M, M, M bank-1
10 c,C, C M, M, M bank-2
C M, M, M, C,C bank-1
7
10 M, M, M, C bank-2
7 0. M, M, M, C, C, C bank-1
,
bank-2