How many possible combinations are there in Hua Rong Dao?
Hua Rong Dao is a Chinese sliding puzzle game, also called Daughter in a Box in Japan. You can see a picture here and an explanation here .
The puzzle is a $4 \times 5$ grid with these pieces
- $2 \times 2$ square ($1$ piece)
- $1\times 2$ vertical ($4$ pieces)
- $2 \times 1$ horizontal ($1$ piece)
- $1 \times 1$ square ($4$ pieces)
Though traditionally each type of piece will have different pictures, you can treat each of the $1\times 2$'s as identical and each of the $1\times 1$'s as identical.
The goal is to slide around the pieces (not removing them) until the $2 \times 2$ "general" goes from the middle top to the middle bottom (where it may slide out of the border).
I'm not concerned in this question with the solution, but more curious about the number of combinations. Naively, I can come up with an upper bound like this
Place each piece on the board, ignoring overlaps.
The $2\times2$ can go in any of $3 \cdot 4 = 12$ squares
The $2\times1$ can go in any of $4 \cdot 4 = 16$ squares
The $1\times2$ can go in any of $3 \cdot5 = 15$ squares
The $1 \times 1$ can go in any of $4\cdot 5 = 20$ squares
If you place the pieces one at a time, subtracting out the used squares
place the $2 \times 2 = 12$ options
place each of the $2 \times 1 = \dfrac{(16 – 4) (16 – 6) (16 – 8) (16 – 10)}{ 4!}$ options
place the $1 \times 2 = 15 – 6$ options
place the $1 \times 1 = { {20-14} \choose 4} = 15$ options
multiplied together this works out to $388,800$.
Is there any way I might be able to narrow this down further? The two obvious things not taken into account are blocked pieces (a $2 \times 1$ pieces will not fit into two separated squares) and the fact that not all possibilities might be accessible when sliding from the starting position.
Update:
I realized that the puzzle is bilaterally symmetrical, so if you just care about meaningful differences between positions, you can divide by two.
Best Answer
A straightforward search yields the figure of $4392$ for all but the $1 \times 1$ stones. The former fill $14$ out of $20$ squares, so there are $\binom{6}{4} = 15$ possibilities to place the latter. In total, we get $$4392 \times 15 = 65880.$$ These can all be generated, and one can in principle calculate the number of connected components in the resulting graph, where the edges correspond to movements of pieces.
Edit: There are 898 different connected components. There are 25955 configurations reachable from the initial state.