A basic wooden railway set contains the pieces shown in . 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.
-
Suppose that the pieces fit together exactly with no slack. Give a precise formulation of the task as a search problem.
-
Identify a suitable uninformed search algorithm for this task and explain your choice.
-
Explain why removing any one of the “fork” pieces makes the problem unsolvable.
-
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.)