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

-

## 1 Answer

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

-
But suppose there existed a state with value N that was even that couldn't reach another state where value N was even. The problem doesn't address that scenario. I guess I should just ignore it... –  user41500 Sep 17 '12 at 6:22
@user41500: Ah, now I see what was worrying you. Your question isn’t really whether the two sets exhaust the space: it’s whether each set is connected, in the sense that you can move from any state in it to any other. That actually does take some work; I’m not sure that I can come up with a reasonably compact argument. I’ll give it some thought, but don’t hold your breath. –  Brian M. Scott Sep 17 '12 at 6:28