The underlying graph remains fixed, but the distribution of the animals, or the placement of the number squares in the 15 puzzle, changes move by move. Each such distribution is called a state. One cage, or one square, is always empty, so for an underlying graph with n vertices we have n-1 labels---animal names, or numbers--- which are placed at all vertices but one. Examples are shown below.
You see the starting state, a state we can derive from that in one move (by moving the donkey), and the target state we want to obtain.
And here is a state, and the target state for the 15-puzzle.