$(5+2+2pts)$ Consider the word ladder puzzle $($conceived by Lewis Carroll$).$ You are given a $k-$

character word that you must transform into another $k-$character word in a series of steps in each of

which you can only change one character while only producing valid words $($based on a given

dictionary$).$ E$.$g$.,$ to transform APE to MAN, the following gives a shortest series of valid moves:

APE $$ APT $$ OPT $$ OAT $$ MAT $$ MAN.

a$)$ Formulate this problem as a search problem, i$.$e$.,$ specify the state data structure, initial state,

actions$/$successor function, goal test, and path cost.

b$)$ What is the maximum branching factor in this search space?

c$)$ Construct an admissible heuristic for this problem.