1. A basic wooden railway set contains a set of N pieces, each with one or more holes and pegs. For example a straight or curved track has a hole on one side and a peg on the other. A fork track has either two pegs and one hole, or two holes and one peg. The task is to connect these pieces into a railway that has no overlapping tracks and no loose ends where a train could run off onto the floor (assume that this is possible by design). Assume you place the first piece with its notch/hole at (0,0), and that for any piece, there is a known offset so that, given the location of where you place its hole (by snapping it onto an open peg), you can calculate where the pieces peg fall in the 2D space. So your open list in the search really is just a list of open peg locationsthat you could snap new pieces onto.
   1. (a) Give a precise formulation of the task as a search problem (initial state, successor function, goal test, step cost).
   2. (b) Identify a suitable uninformed search algorithm for this task and explain your choice.
   3. (c) Explain why removing any one of the fork pieces makes the problem unsolvable.
   4. (d) EXTRA CREDIT: Give an upper bound on the total size of the state space defined by your formulation. (Hint: think about the maximum branching factor for the construction process and the maximum depth, ignoring the problem of overlapping pieces and loose ends. Begin by pretending that every piece is unique.)