How to enumerate all states in the 8-puzzle?

Question

I am solving the 8-puzzle. It is a problem which looks like this:

Image courtesy of: https://ece.uwaterloo.ca/~dwharder/aads/Algorithms/N_puzzles/ (you can also see there for a more detailed description of the 8-puzzle). The user can move a square adjacent to the blank into the blank. The task is to restore the arrangement as shown in the picture, starting from some arbitrary arrangement.

Now, of course the state can be described as a permutation of 9 digits. In case of the picture shown, the permutation is:

1 2 3 4 5 6 7 8 0

However, not all permutations are reachable from the shown configuration. Therefore, I have the following questions.

1. What is the number of permutations obtainable from the shown initial configuration by sliding tiles into the blank?

2. Call the answer to the above N. Now, I want a 1-1 mapping from integers from 1 to N to permutations. That is, I want to have a function that takes a permutation and returns an appropriate integer as well as a function that takes an integer and returns the permutation. The mapping has to be a bijection (i.e. an imperfect hash is not enough).

Answer 1

1. 181440.
2. Stick them in an array and sort it, e.g. lexicographically. Then converting integers to permutations is O(1), and going the other way is O(log n).

Answer 2

Well if you just want to enumerate the different possible states that can be reached, you can just depth first search from your initial state. It's very possible to generate the valid next states given a current state, for example: moving a tile down into the empty space is the same as swapping the 0 tile with the tile 3 before it in the permutation if there is one. So you just do a dfs and keep a hashset of all the permutations as your visited array which could be stored as ints or strings. there are only 9! possible states which is only 362880. If you need a 1-1 mapping from the set of integers just make the hashset a hashtable and everytime you find a new state just add it to the hash table at the next index. You could also find the shortest solution by doing a breadth first first instead and just breaking when you find the solved state.