The Towers of Hanoi puzzle in computer science, it consists of three pegs and n disks, from largest to smallest on one of the pegs. It consists of three rods and a number of disks of different sizes, which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.

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.

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).