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.


I realized that the puzzle is bilaterally symmetrical, so if you just care about meaningful differences between positions, you can divide by two.

  • $\begingroup$ Questions of this general form are actually very hard and an active topic of research in combinatorics. I don't know any good references, though. $\endgroup$ – Qiaochu Yuan Jan 12 '11 at 15:45
  • 1
    $\begingroup$ You need to decide if you just want the number of ways to put the pieces in the box or the number of ways accessible from start. For the number of ways in the box, you could write a program that just puts the 2x2 in each location, then finds the possibilities for the 1x2s, etc. As Qiaochu says, I don't know any easy way. For accessible from start, maybe you can prove that they all are accessible, or maybe there is a parity argument (like the 14-15 puzzle). $\endgroup$ – Ross Millikan Jan 12 '11 at 17:01
  • $\begingroup$ Both are interesting questions. Part of the genesis of the question is that we were speculating about random arrangements of the pieces and wondering how many were legitimate states (e.g. accessible from the start). I quickly realized that it was not simple to answer either! $\endgroup$ – Will Glass Jan 12 '11 at 23:00
  • $\begingroup$ If you're counting total positions, it's not important to distinguish between the four small squares or between the four vertical dominoes, since the number of positions when they are distinguishable is just a constant factor (4!^2) greater than when they are indistinguishable. But if you're counting accessible positions, this may no longer be the case. $\endgroup$ – mjqxxxx Jan 13 '11 at 1:34

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.

  • $\begingroup$ Can you explain how you got that answer? What do you mean by a "straightforward search"? I'm looking for a little insight, too. $\endgroup$ – Will Glass Jan 13 '11 at 2:42
  • $\begingroup$ The search goes by first putting on of the pieces in some location, then the second piece in some location which does not overlap the first, etc. To find the number of reachable positions, you run a BFS/DFS from the initial position. $\endgroup$ – Yuval Filmus Jan 13 '11 at 3:14
  • $\begingroup$ I'm not sure what insight you're looking for. Given the board size and the piece, perhaps it is possible to find an asymptotic form for the number of solutions (e.g. given that the pieces are "small" and "small in number"). Then you might ask whether in this particular case, the asymptotic estimate is good or not. $\endgroup$ – Yuval Filmus Jan 13 '11 at 3:16
  • $\begingroup$ Thanks. Does that mean you wrote a computer program to solve this? Very cool. Or is there a existing program you used? By insight, I meant insight into how to solve this. (right now I'm just taking your word as an anonymous authority). $\endgroup$ – Will Glass Jan 14 '11 at 4:32
  • 1
    $\begingroup$ If you consider the graph where the vertices are all positions of the pieces, and the edges correspond to single moves, then the graph has 898 connected components. $\endgroup$ – Yuval Filmus Jan 14 '11 at 5:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.