How to find all possible states of 8-puzzle?

I know that there are 9! possible states and 9!/2 solvable states but I want to be able to write an algorithm using depth-first search to find what all the possible states are and record them in an array. I will be using Java but it's more the theory that I am after if anyone can help?

You can use an iterative algorithm, like the iterative form of Heap's algorithm for iterating all permutations of an array through swaps.

A swap will toggle the parity when the "gap" is not involved in the swap. In other words, if you would solve the puzzle and then take out two pieces and put them back in eachother's place, the puzzle would not be solvable any more. Repeat that with any two pieces, and the puzzle becomes solvable again.

A swap of a piece with the "gap" will only toggle the parity when the taxicab distance between these two positions is even.

So if you implement Heap's algorithm and keep the parity updated with the above two rules, then you can decide for each permutation whether to include it or not:

int[] a = {1,2,3,4,5,6,7,8,0}; // 0 represents "gap"
int[] stack = {0,0,0,0,0,0,0,0,0};

System.out.println(Arrays.toString(a));

boolean parity = true;
int i = 0;
int n = a.length;
while (i < n) {
    if (stack[i] < i) {
        int j = i % 2 > 0 ? stack[i] : 0;
        // SWAP a[i], a[j] 
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
        // Toggle parity when "gap" is not moved
        // or it is moved with even taxicab distance
        if (a[i] > 0 && a[j] > 0 || ((i^j)&1) == 0) parity = !parity;
        if (parity) System.out.println(Arrays.toString(a));
        stack[i]++;
        i = 0;
    } else {
        stack[i++] = 0;
    }
}