Show that the 8-puzzle states are divided into two disjoint sets, such that any state is reachable from any other state in the same set, while no state is reachable from any state in the other set. (Hint: See Berlekamp+al:1982) Devise a procedure to decide which set a given state is in, and explain why this is useful for generating random states.