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:
http://en.wikipedia.org/wiki/File:Hakoiri3.jpg
And an explanation here:
http://en.wikipedia.org/wiki/Klotski#Hua_Rong_Dao
The puzzle is a 4x5 grid with these pieces
- 2x2 square (1 piece)
- 1x2 vertical (4 pieces)
- 2x1 horizontal (1 piece)
- 1x1 square (4 pieces)
Though traditionally each type of piece will have different pictures, you can treat each of the 1x2's as identical and each of the 1x1's as identical.
The goal is to slide around the pieces (not removing them) until the 2x2 "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 2x2 can go in any of 3x4 = 12 squares
The 2x1 can go in any of 4x4 = 16 squares
The 1x2 can go in any of 3x5 = 15 squares
The 1x1 can go in any of 4x5 = 20 squares
If you place the pieces one at a time, subtracting out the used squares
place the 2x2 = 12 options
place each of the 2x1 = ((16 - 4) * (16 - 6) * (16 - 8) * (16 - 10)) / 4!
place the 1x2 = 15 - 6
place the 1x1 = (20-14) choose 4 = 15
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 2x1 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.