Chapter 5 - Satisfying constraints

Question 1

Generate and test

Answer 1

a value is generated for a variable and then tested to see if the value is the desired one.
“Root” of constraint satisfaction problems.

Question 2

Constraint satisfaction problems are made up of 3 elements:

Answer 2

1. number of variables for which value are to be found
2. each variable gets a value from some finite domain
3. there are constraints to be satisfied among subsets of variables

Question 3

A “solution” is…

Answer 3

an assignment of a value to each variable such that all the constraints are satisfied

Question 4

Steps to solve a constraint satisfaction problem…

Answer 4

1. generate values
2. test to see if all constraints are satisfied
3. backtrack as necessary

Question 5

Example of constraint satisfaction problem:

solution(Variable1,Variable2,. . .,VariableN):-

domain1(Variable1),…domainN(VariableN),

constraint1(Variable,…,Variable),…
constraintM(Variable,…,Variable).

Answer 5

Map coloring:

solution(A,B,C,D,E) :-

color(A), color(B), color(C), color(D), color(E),

+ A=B, + A=C, + A=D, + A=E, + B=C, + C=D, + D=E.

color(red).
color(white).
color(blue).

Question 6

What does the predicate write(argument) do?

Answer 6

It is used in KB to personalize the output.
When a query will be called (the head of the if-statement in the KB), the output will be given according to what was specified in the write() predicate in the body of the if-statement. (see page 90 of the Lbook for example)

Question 7

nl

Answer 7

new line

Question 8

Anonymus variable

Answer 8

used in problems where the goal is not finding the value, but ensuring there is one.

Example:

child(_, Sue) –> does Sue have a child?
Not important WHICH child, important is she has a child.

Question 9

uniq() predicate

Answer 9

takes n arguments and ensures that they are all different from each other.

Question 10

num() predicate

Answer 10

can test or generate the numbers from X to Y that are unique

Question 11

Try to explain what happens in figure 5.5 at page 93 of the book - Sudoku problem-

Answer 11

How does this solution predicate work? It needs to generate sixteen values. It starts by using uniq(R11,R12,R13,R14) to generate four distinct values for the variables of row 1. Then it does the same for rows 2, 3, and 4. At this point, all sixteen variables have values. It then tests uniq(R11,R21,R31,R41), which is for the variables of column 1. If these four values are distinct, it continues and tests the distinctness of columns 2, 3, and 4; if they are not distinct, the test fails, and it backtracks to generate new values for the variables in row 4 or 3 or 2 or perhaps all the way back to row 1, as necessary. Once all the column tests succeed, the solution predicate tests uniq(R11,R12,R21,R22), which is for the variables of the NW quadrant. If these four values are distinct, it tests the quadrants NE, SW, and SE in turn; if they are not distinct, it again backtracks all the way to the rows and tries to generate new values.If all the column and quadrant tests are successful, a solution has been found, and the program is done.

Question 12

Number in Prolog

Answer 12

sequence of one or more digits: they can appear anywhere a constant can appear.

Question 13

Arithmetic realtions in Prolog:

Answer 13

less than: <
greater than: >
less than or equal to: <=
greater than or equal to >=
equal =:=
equal : Variable is E

Question 14

Must variables in arithmetic relations be already instantiated?

Answer 14

Yes, unless we are using the “is” operation: in that case, we have to make sure that the query is in the following format:
- LHS: variables with a term such as X = 4 and the variable we want to calculate, say Y, WITH NO VALUE IN THE LHS: additionally, the “Y is..”
RHS; arithmetic expression, that defines Y, such as X + 4

Example:
(Y=2, X is) (Y+4.)
X=6, Y=2
Yes

NB: the parentheses are not part of the code, they were put there by me to highlight the LHS and RHS.

Question 15

Is

q(Y), p(Y+4, Z) a legal query?

Answer 15

No, because Y+4 is not a legal term

Question 16

Is

q(Y), X is Y+4, p(X, Z) a legal query?

Answer 16

Yes, because all predicates have legal terms as arguments.

Question 17

How can we minimize the guesswork in constraint satisfaction problems?

Answer 17

1. if a value is fully determined by other values, then avoid guessing the value and later testing if it is correct.
2. avoid placing independent guesses between the generation and the testing of other values

Question 18

Example of point 1 of how to minimize constraint satisfaction problems:

Answer 18

Suppose there are two predicates uniq2 and uniq3 that can test or generate two or three distinct values, respectively. Then instead of writing this:

uniq3(A,B,C), % Guess at A,B,C.
B is (A+C) mod 10 % Then test if B is ok.

write this:

uniq2(A,C), % Guess at A and C.
B is (A+C) mod 10, % Calculate B once.
uniq3(A,B,C) % Test that all values are unique.

Question 19

Example of point 2 of how to minimize constraint satisfaction problems:

Answer 19

dig(A), dig(B), % Guess at A and B.
dig(C), dig(D), % Guess at C and D.
A>B % Test for A and B.

write this:
dig(A), dig(B), % Guess at A and B.
A>B, % Test for A and B.
dig(C), dig(D) % Guess at C and D.

This minimization applies to the map coloring problem.

Question 20

Challenge in satisfaction constraint problems: how can we express the constraint?

Answer 20

One way to go about this is to imagine that there are hidden variables that are not mentioned, but whose values need to be taken into account.