Solvability: Half of the initial states for the N-Puzzle are impossible to resolve. This can be proved by an invariant of the board: The parity of permutations of all squares + the parity of the Manhattan distance of all squares. This is an invariant because each legal move changes both the parity of the permutation and the parity of the Manhattan distance. This invariant split the space of all possible states into two equivalence classes of solvable and unsolvable states.