NP combination puzzle (Klotski)

Question

I've written a C++ program to solve sliding puzzles games such as UnblockMe and Car Parking. I'm quite happy about it, since it solves various schemes in less than a second. Recently I fed the game with Klotski schema (https://en.wikipedia.org/wiki/Klotski) that requires no less than 81 moves to solve it. My code respects the following algorithm:

Enqueue the current board
while Q not empty:
    Dequeue a board and examine it if not already examined
    can the big block escape?
        "solution found"
    it cant?
        for each possible board that can arise out of this one
            add board to END of Q

With my surprise things go well for about 45-50 moves, then the process is extremly slow. I know the game is NP-complex, but I have the suspect my code could be wrong. Considering all pieces different, how many permutation are possible? My code output the following in about one second:

step 1 new: 6 duplicated: 0
step 2 new: 14 duplicated: 14
step 3 new: 25 duplicated: 46
step 4 new: 38 duplicated: 112
step 5 new: 63 duplicated: 213
step 6 new: 107 duplicated: 378
step 7 new: 160 duplicated: 659
step 8 new: 239 duplicated: 1094
step 9 new: 332 duplicated: 1750
step 10 new: 491 duplicated: 2665
step 11 new: 668 duplicated: 4009
step 12 new: 804 duplicated: 5897
step 13 new: 853 duplicated: 8226
step 14 new: 869 duplicated: 10534
step 15 new: 869 duplicated: 12813
step 16 new: 918 duplicated: 14921
step 17 new: 955 duplicated: 17058
step 18 new: 1003 duplicated: 19174
step 19 new: 1097 duplicated: 21343
step 20 new: 1215 duplicated: 23674
step 21 new: 1267 duplicated: 26391
step 22 new: 1272 duplicated: 29299
step 23 new: 1493 duplicated: 32276
step 24 new: 1561 duplicated: 35949
step 25 new: 1624 duplicated: 39871
step 26 new: 1595 duplicated: 43830
step 27 new: 1693 duplicated: 47669
step 28 new: 1940 duplicated: 51725
step 29 new: 2280 duplicated: 56435
step 30 new: 2816 duplicated: 62037
step 31 new: 3166 duplicated: 69297
step 32 new: 3420 duplicated: 77335
step 33 new: 4166 duplicated: 85621
step 34 new: 5490 duplicated: 95771
step 35 new: 7398 duplicated: 109271
step 36 new: 9630 duplicated: 127499
step 37 new: 12538 duplicated: 151293
step 38 new: 16240 duplicated: 182497
step 39 new: 20068 duplicated: 223457

Last line i.e. step 39 new: 20068 duplicated: 223457 tells me that with 39 moves player can reach 223457 + 20068 possible disposition of pieces (but 223457 positions are already analized, so availabe also with less moves).

Are these numbers legit? Or I am missing something?

Answer 1

If you are considering all pieces distinct (even pieces of the same size), then sure, your number of possible arrangements seems reasonable, although it's hard to know for sure. What I can say is that you have four $1 \times 1$ pieces and four $2 \times 1$ pieces. If you make them all distinct, this could increase the number of possible boards by a large multiplicative factor. For example, just assuming you could permute the four $1 \times 1$ pieces for any board configuration, this would mean that the number of possible boards would be multiplied by 24. You'll probably be better off if you label the pieces lexicographically if you must label them (i.e., top-most $1 \times 1$ piece is labeled 1, next highest $1 \times 1$ piece is labeled 2, etc. where ties are broken by making the left-most piece come first. Then similarly do the same thing for the four $2 \times 1$ pieces, because in theory you may be able to get some permutations on them too, and if all permutations are possible, this would mean the overall multiplier on your number of boards would be $24^2$ in the worst case, which is considerably high compared to the number of boards you get after 39 moves.

Answer 2

Doubtful you're still working on your program, but I only just came across this because I'm presently writing a klotski solver program too and was also wondering if my numbers were, as you say, legit.

The magnitudes of the reachable positions shown in your output are close to my own program's, but the very first line of your output is curious. If I understand correctly, "step 1 new: 6 duplicated: 0" means that your algorithm found 6 new arrangements of the pieces by moving just one piece from the starting arrangement. It's easy to see that only the four smallest pieces can be moved in the very beginning. If each of these pieces is only permitted to move one space at a time, then only 4 new arrangements are possible. If additionally each of them is allowed to move two spaces in a row (such as moving the piece in the lower left corner two spaces to the right) while still counting as one "move", then I count a total of 8 possible new arrangements for the opening move. Indeed my program lists 8 reachable positions in the beginning. But your output says there are exactly 6 opening moves. Why 6?