For each of the following, explain how to formulate the problem as a state space search problem. Identify the states, rules, and successor function as well as the initial and goal state(s).

1. The Towers of Hanoi puzzle consists of three pegs and n disks, initially stacked from largest to smallest on one of the pegs. The goal is to end up with the disks stacked from largest to smallest on a different peg. Only one disk can be moved at a time, disks can only be placed on pegs, and a larger disk can never be stacked on top of smaller disks.

2. Solve a Rubik's cube by making each face a single color.