# Sliding puzzle disjoint sets proof

Prove that the states of the 8-puzzle are divided into two disjoint sets such that any state in one of the sets is reachable from any other state in that set, but not from any state in the other set. To do so, you can use the following fact: think of the board as a one-dimensional array, arranged in row-major order. Define an inversion as any pair of contiguous tiles (other than the blank tile) in this arrangement such that the higher numbered tile precedes the lower numbered tile. Let N be the sum of the total number of inversions plus the number of the row in which the blank tile appears. Then (N mod 2) is invariant under any legal move in the puzzle.

I know how to show that any state in one set is not reachable from another set, due to the invariant, but I'm trying to show that the union of the two disjoint sets encompass the entire state space. One thing I've tried is calculating the total possible arrangements (9!), and then the number of possible arrangements in each of the disjoint sets, but I haven't thought of a good way to calculate the latter.

-

You’re working too hard: every state has an associated value of $N$, and that value is either even or odd.