**NPTEL AI:Constraint Satisfaction Assignment Answer**

## NPTEL AI:Constraint Satisfaction Assignment Answer (week 1) 2023

**1. Select the true statements.**

- A constraint in a CSP is a restriction on the values a variable or a combination of variables can take.
- A solution to a CSP is the set of values assigned to all the variables, such that they satisfy all the constraints.
- A solution to a CSP is the set of values, assigned to some variables, that satisfy some of the constraints.
- In a Binary CSP, each constraint is between two variables.
- In a Binary CSP, the domain of each variable contains exactly two values.

**Answer :- **A constraint in a CSP is a restriction on the values a variable or a combination of variables can take,
A solution to a CSP is the set of values assigned to all the variables, such that they satisfy all the constraints,
In a Binary CSP, each constraint is between two variables,

**2. Two constraint networks over the same set of variables are equivalent IF AND ONLY IF __________ .**

- the constraints in the two networks are the same
- the constraint graphs of the two networks are the same
- the matching diagrams of the two networks are the same
- the solutions expressed by the two networks are the same

**Answer :- **the solutions expressed by the two networks are the same

**3. Select the true statements.**

- Every constraint network has a dual binary constraint network.
- Every constraint network can be converted to an equivalent binary constraint network over the same set of variables.

**Answer :- **Every constraint network has a dual binary constraint network.

**4. Consider the constraint network R = ( {x1, x2, x3}, {D1, D2, D3}, {R12, R23} ) where D1=D2=D3={t,h,e,b,a,n,d} and R12 = { (b,a), (b,e), (h,a), (h,e) } and R23 = { (a,t), (e,n) }. How many solutions does this network have? Enter a number.**

**Answer :- **(Type: Numeric) 4

**5. R123 = { (b,a,n), (b,a,t), (b,e,t), (h,a,t), (h,e,n) } is a relation whose scope is (x1, x2, x3), let R12, R23 and R13 be the projections of R123. Select the true statements.**

- The composition of R12, R23, R13 is a equal to R123
- The composition of R12, R23, R13 is a subset of R123
- The composition of R12, R23, R13 is a superset of R123
- None of the above

**Answer :- **The composition of R12, R23, R13 is a superset of R123

**6. An L-shaped solid block is shown in the figure. The view is from a camera located above the block, that is looking down at the roof and walls of the block, the bottom side is hidden from the camera.**

Determine the edge labels (convex, concave, arrow) and junction labels in the 2D line drawing. What is the label of the edge AD?

- Convex
- Concave
- Arrow from A to D
- Arrow from D to A

**Answer :- **Arrow from A to B

**8. What is the label of the edge BC?**

- Convex
- Concave
- Arrow from B to C
- Arrow from C to B

**Answer :- **Convex

**9. Determine the labels of the junctions A, B, C, D and E? Enter the junction labels of A, B, C, D and E, in that order, as a comma separated list.**

Answer format: L2,T4,W1,L3,T2

**Answer :- **(Type: String) Y1,W1,Y3,W3,L1

**10. Solve the 2D line drawing by assigning edge labels and junction labels from the catalog. Enumerate all the solutions. How many solutions exist for this line drawing?**

Enter the number of solutions in the textbox.

**Answer :- **(Type: Numeric) 2

**11. Solve the 2D line drawing by assigning edge labels and junction labels from the catalog. Enumerate all the solutions. How many solutions exist for this line drawing?**

Enter the number of solutions in the textbox.

**Answer :- **(Type: Numeric) 0

## NPTEL AI:Constraint Satisfaction Assignment Answer (week 2) 2023

**1. An assignment to a subset of variables of a network is consistent if __________ .**

- every variable gets a value only from its domain.
- every constraint whose scope is contained in the subset is satisfied.
- if at least one constraint is satisfied by the assignment.
- if it can be extended to every other variable.

**Answer :- **every constraint whose scope is contained in the subset is satisfied.

**2. Which of the following statements are true for a CSP having N variables each of which has a domain of size K?**

- The number of different relations is
_{2}k^{2}n^{2}, while the number of different binary constraint networks is_{2}k^{n} - The number of different relations is
_{2}k^{n}, while the number of different binary constraint networks is_{2}k^{2}n^{2} - The number of different relations is k
^{2}n^{2}, while the number of different binary constraint networks is k^n - The number of different relations is k
^{n}, while the number of different binary constraint networks is k^{2}n^{2}

**Answer :- **The number of different relations is _{2}k^{n}, while the number of different binary constraint networks is _{2}k^{2}n^{2}

**3. An edge in a matching diagram __________ .**

- exists between variables that are related
- exists between consistent values of two variables
- matches the variables with the same arity
- identifies two variables that have same number of values

**Answer :- **exists between consistent values of two variables

**4. A composition of two relations RXY and RYZ identifies __________ .**

- paths of length 2 from values in X to values in Y in the matching diagram
- paths of length 2 from values in X to values in X in the matching diagram
- paths of length 2 from values in X to values in Z in the matching diagram
- paths of length 2 from values in Y to values in Z in the matching diagram

**Answer :- **paths of length 2 from values in X to values in Z in the matching diagram

**5. Projecting a relation ρ onto each pair of its variables will give the _________ of relation ρ.**

- Equivalent network
- Primal constraint
- Dual constraint
- Minimal network
- None of the above

**Answer :- **None of the above

**6. Given a constraint network with four variables x1, x2, x3 and x4 having domains D _{1}={a,b,c}, D_{2}={1,2,3}, D_{3}={4,5,6}, and D_{4}={A,B,C}, and one constraint ρ1234 ={(a,2,5,A), (b,1,5,B), (a,1,4,A)}.**

**The number of constraints in the projection network P(ρ) for the above network is __________ .**

**Answer :- **(Type: Numeric) 6

**7. Given the above network with constraint ρ1234, which of the following tuple(s) will be present in the solution of projection network P(ρ) of ρ:**

- (a,1,4,A)
- (a,1,5,A)
- (a,2,4,A)
- (b,1,4,B)

**Answer :- **(a,1,4,A)
(a,1,5,A)

**8. Given a constraint network with three variables x1, x2 and x3 all defined on the same domain values {red,blue}, the constraints in the network are R _{12}=R_{23}={(red,blue), (blue,red)}. If you construct a minimal network for the given CSP, the number of edges in the matching diagram of the minimal network will be __________ .**

**Answer :- **6

**9. If a CSP is arc consistent then __________ .**

- it always has a solution
- it always has a unique solution
- it may not have a solution
- none of the above

**Answer :- **it may not have a solution

**10. What are the colours in the domain of region A after arc consistency has been achieved on the corresponding CSP? Mark all colours in the domain of A.**

- red
- blue
- green
- none of the above

**Answer :- **blue
green