Constraint satisfaction problems In AI part 03

Introduction

            Constraint programming is a useful tool in formulating and solving problems that can be defined in terms of constraint among a set of variables. In fact real world problems are constraint satisfaction problems defined in terms of some variables that bear some constraints. Finding a set of variables, that are within the constraints given(or observed) is a solution to that problem.

            Let us consider a problem, that can be represented by some relations of the variables x, y and z. We have a domain Dx, Dy, Dz from where the variables can take a value. The constraint is given by a set C and may have a number of constraints C₁,C₂,C₃,etc each relating some or all of the variables x,y and z. Now a solution (or solutions) to the problem is a set dx,dy,dz such that dx   Dx,  dy   Dy and dz   Dz and all the constraints of the set C are satisfied.

Eight queens problem

            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 eachother. So the problem can be formulated with variables x₁,x₂,x₃,x₄,x₅,x₆,x₇,x₈ and y₁,y₂,y₃,y₄,y₅,y_6, y₇,y₈; 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={(x₁,y₁),(x₂,y₂),……………………..(x₈,y₈)}

where (x₁,y₁) gives the position of the first queen and so on.

            So it can be clearly seen that the domains for x_i and y_i 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  y_i≠y_j for i=1 to 8;j=1 to 8;i≠j

        ii.            No two queens should be in the same column,

i.e  x_i≠x_j 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  (y_i-y_j) ≠ ±(x_i-x_j).

Now a solution to this problem is an instance of P wherein the above mentioned constraints are satisfied.

PREDICATES

DOMAINS

cell=c(integer,integer)

list=cell*

int_list=integer*

PREDICATES

solution(list)

member(integer,int_list)

nonattack(cell,list)

CLAUSES

solution([]).

solution([c(X,Y)|Others]):-

                solution(Others),

                member(Y,[1,2,3,4,5,6,7,8]),

                nonattack(c(X,Y),Others).

               

nonattack(_,[]).

nonattack(c(X,Y),[c(X1,Y1)|Others]):-

                Y<>Y1,

                Y1-Y<>X1-X,

                Y1-Y<>X-X1,

                nonattack(c(X,Y),Others).

                               

member(X,[X|_]).

member(X,[_|Z]):-

                member(X,Z).

               

               

GOAL

solution([c(1,A),c(2,B),c(3,C),c(4,D),c(5,E),c(6,F),c(7,G),c(8,H)]).

Assignment 1). Observe the result of the above program and discuss on the result. Test the goal by placing a few queens explicitly.

(Try goals like solution ([c(1,1),c(2,B),c(3,C),c(4,8),c(5,E),c(6,F),c(7,G),c(8,H)] etc).

Increase the dimension of the chess board and observe the result.

Assignment 2). Try to solve the above problem using C or C++.

Assignment 3). Create a DLL file using prolog and use it in any of the available languages java or .NET to depict the solution. Make it interactive. (You may want to set a queen in the fifth row of the first column).

You can refer to the examples at in \\vip\foreign\examples

Crypto arithmetic problem

            Crypto arithmetic problem is yet another constraint satisfaction problem. We have to assign numeric values(0 through 9) to the alphabets in the given words in such a way that the sum of the two words equals the third.

            For example: SEND+MORE=MONEY

We have to assign values to the individual alphabets in such a manner that the arithmetic rules are followed, a trivial solution will be to assign 0s to all, but we have a constraint, no two alphabets should be assigned with the same number.

            C₄        C₃        C₂        C₁

                        S          E          N         D

            +          M         O         R         E

 

            M         O         N         E          Y

So, by now we have the problem in hand. The domain for the alphabets is

S,E,N,D,M,O,R,Y€ {0,1,2,3,4,5,6,7,8,9}.

The constraints are

D+E=Y+10C₁

N+R+C₁=E+10C₂

E+O+C₂=N+10C₃

S+M+C₃=O+10C₄

M=C₄

C₁,C₂,C₃,C₄€{0,1}

And we have the constraint that no two alphabets should be assigned with the same number. Moreover some AI scientists insist that M should be 1 seeking that the third row will reduce just to four literals else wise. This might be an extra constraint.

Assignment 4) Find out the solution to the above problem without considering the constraint M=1. Modify your program adding this as a constraint. Can you imagine solving this in C? Its just a question. You don’t have to really try it? But we won’t stop you either.

Assignment 5) Write a module to solve the classical missionaries and cannibals problems in prolog.

source:IOE pulchowk campus