Show that the 8-puzzle states are divided into two disjoint sets, such that n'o state in one set can be transformed into a state in the other set by any number of moves. (~Yint: See Berlekamp et al. (1982).) Devise a procedure that will tell you which class a given state is in, and explain why this is a good thing to have for generating random states.