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