the board is like this:
1 2 3 4
5 6 7 0
0 0 0 0
0 0 0 0
the '0' represents that is empty, we can move the non-zero number to the '0'. so how to get all of the state of the board using BFS?
for example, there are two state of the board:
1 2 3 4
0 0 0 0
5 6 7 0
0 0 0 0
1 2 3 0
4 0 0 0
5 0 0 0
6 7 0 0
The reason I ask this question is that I need to process all of the 15-puzzle state using Disjoint pattern database to solve the nearly most difficult state of 15-puzzle in 1 minutes.
15 14 13 12
11 10 9 8
7 6 5 4
3 1 2 0
Approach 1 - using a database and storing all states
For reasons given by Henry as well, and also supported by [1], solving this problem using a database would require generating the entire A_15 , storing all of it and then finding the shortest path, or some path between a given state and the solved state. This would require a lot of space and a lot of time. See this discussion for an outline of this approach.
Approach 2 - using a specialized depth-first search algorithm
Here is an implementation of this search strategy that uses the IDA algorithm.
Approach 3 - using computational group theory
Yet another way to handle this in a much shorter amount of time is to use GAP (which implements a variant of Schreier-Sims) in order to decompose a given word into a product of generators. There is an example in the docs that shows how to use it to solve the Rubik's cube, and it can be adapted to the 15-puzzle too [2].
[1] Permutation Puzzles - A Mathematical Perspective by Jamie Mulholland - see page 103 and 104 for solvability criteria, and the state space being
|A_15| ~ 653 billion[2] link2 - page 37