Question

We are given the following CSP problem.

The variables and domains are as follows.
A: {4, 5, 6, 7, 8}
B: {10, 20, 30, 40}
C: {2, 3, 4}
D: {28, 43, 56, 77, 94, 114}


The constraints are:
A + C is odd.
A + D is a square of an integer.
B + D < 60.


Solve this problem using the following heuristics and algorithms.
• Use backtracking search.
• For variable ordering, use MRV. If there are ties, use degree to break
them. If there are still ties,
break them in alphabetical order.
• For value ordering, order values from smallest to largest.
• For inference, use forward checking.


Please show the search tree and the stack of the domains (see the
lectures for examples). When the
search backtracks due to an empty domain, show it clearly on your search
tree. Write down the final
solution, if there is any.

(Languge use By Hand)

Answer 1

Given that,

The variables and domains are as follows.
A: {4, 5, 6, 7, 8}
B: {10, 20, 30, 40}
C: {2, 3, 4}
D: {28, 43, 56, 77, 94, 114}

The constraints are:
A + C is odd.
A + D is a square of an integer.
B + D < 60.

Consider below image which shows the required solution paths: