$2.[10$ points$]$

In the cryptarithmetic problem below, the aim is to find a substitution of digits for

the letters

T$,$ W$,$ O$,$ F$,$ U

and

R

such that each letter stands for a different digit, and the resulting

sum is arithmetically correct. The leading letters

T

and

F

cannot be $0.$

Auxiliary variables

x$1,$ x$2$

and

x$3$

are introduced for representing carry overs.

The domains for the variables and the constraints

for the problem are specified below.

Assume that we use the Backtracking algorithm in the Appendix to find a solution for this problem.

Since

x$3$

and

F

only have one value in their domain, they will be chosen by the Backtracking

algorithm first and assigned the value $1.$ In the search tree generated, assume that level $0$ is for

empty assignment, level $1$ is for assigning $1$ to variable F and level $2$ is for assigning $1$ to variable

x$3.$ Determine the total number of nodes that will be generated by the Backtracking algorithm in

the

worst case

$.$

Show all work to get full credits.

$($You do not have to actually generate a search

tree. Just provide an upper bound on the total number of nodes generated based on the information given. Here, the question asks for an upper bound, not time complexity in terms of the big

$$

$($

$$

$)$

notation.$)-$ Backtracking search algorithm for CSP:

$```$

function BACKTRACKING$-$SEARCH$($CSp$)$ returns solution or failure

return BACKTRACK$(\{\},$ CSP$)$

function BACKTRACK$($assignment$,$ csp$)$ returns a solution or failure

if assignment is complete then return assignment

var $\}\backslash$leftarrow$\backslash$mathrm$\{$ SELECT$-$UNASSIGNED$-$VARIABLE$($csp$)$

for each value in ORDER$-$DOMAIN$-$VALUES$($var$,$ assignment, csp$)$ do

if value is consistent with assignment then

add $\{$var $=$ value$\}$ to assignment

inferences $\backslash$leftarrow INFERENCE$($csp$,$ var, value$)$

if inferences $!=$ failure then

add inferences to assignment

result $\backslash$leftarrowBACKTRACK$($assignment$,$ csp$)$

if result $/=$ failure then

return result

remove $\{$var$=$value$\}$ and inferences from assignment

return failure

$```$