Number of possible positions for the Rush Hour puzzle

Question

I'm working on a 2-d Puzzle Rush Hour which is a six * six bored that can be filled with various items :

• 2 blocks length horizontally vertically oriented car - let's call it 1
• 3 blocks length horizontally oriented car ----------- 2
• 2 blocks length vertically oriented car -------------- 3
• 3 blocks length vertically oriented car -------------- 4
• 2 blocks length horizontally oriented target car --- 5
• 1 empty block. --------------------------------------- 6

each square on the board can only be filled from one of the above. What I'm trying to calculate is the number of possible combinations we could have for this puzzle.

My first thought was (6^36) since we have 36 field with 6 options for each ( just like coin flipping) but that is n * 10^28. which is a lot ! and far from accurate.

The solution is a partial set of that value because we have a lot of extra constrains on it, which are:

• 1 must come only after 1 (since the car is two blocks in length) and not at the end of the line ( location (1) % 6 != 5).
• same condition apply to 2 but this time 2 is repeated 3 times and (location (2) % 6 < 5)
• 5 must only be between (12 and 17) and follow 1 restrictions.
• 6 similar rules to 1 but applies vertically. .....

Now the question is how can I represent these limitations to write an equation that will give me the number of all possible outcomes.

Note I've read in this: Paper that the solution is around 10^10 . which is ridiculously lower than the first value (10^28). Note: I'm searching for an answer out of pure curiosity.

Answer 1

The point with such problems is that it quickly gets too complicated to solve with a few equations. It often comes down to counting all the possibilities. The challange is to find a smart way to let the computer count all possibilities, so that it can be done in seconds, instead of years.

I implemented an algorithm that does the trick. I used the programming languages Mathematica and C++. Mathematica because it lets you do a lot with little code. C++ because you can write efficient (fast) code with it. First, execute the following Mathematica code.

arrangements = Select[Tuples[{0, 1, 2}, 6], And @@ (Divisible[Length[#], #[[1]] + 1] & /@ Split[#]) &];
normalRowArrangements = arrangements /. (2 -> 1) // Tally // Sort;
targetRowArrangements = Flatten[ConstantArray[#, Count[#, 1]/2] & /@ arrangements, {1, 2}] /. (2 -> 1) // Tally // Sort;
columnArrangements = Function[l, {l, Select[arrangements, #*l == {0, 0, 0, 0, 0, 0} &] // Length}] /@ Tuples[{0, 1}, 6];

The values of normalRowArrangements, targetRowArrangements and columnArrangements will be inserted into C++ source code. The C++ program will do the rest of the calculation. I'll show the values of the variables and explain their meaning.

normalRowArrangements (21)
{0,0,0,0,0,0}   1
{0,0,0,0,1,1}   1
{0,0,0,1,1,0}   1
{0,0,0,1,1,1}   1
{0,0,1,1,0,0}   1
{0,0,1,1,1,0}   1
{0,0,1,1,1,1}   1
{0,1,1,0,0,0}   1
{0,1,1,0,1,1}   1
{0,1,1,1,0,0}   1
{0,1,1,1,1,0}   1
{0,1,1,1,1,1}   2
{1,1,0,0,0,0}   1
{1,1,0,0,1,1}   1
{1,1,0,1,1,0}   1
{1,1,0,1,1,1}   1
{1,1,1,0,0,0}   1
{1,1,1,0,1,1}   1
{1,1,1,1,0,0}   1
{1,1,1,1,1,0}   2
{1,1,1,1,1,1}   2

targetRowArrangements (16)
{0,0,0,0,1,1}   1
{0,0,0,1,1,0}   1
{0,0,1,1,0,0}   1
{0,0,1,1,1,1}   2
{0,1,1,0,0,0}   1
{0,1,1,0,1,1}   2
{0,1,1,1,1,0}   2
{0,1,1,1,1,1}   2
{1,1,0,0,0,0}   1
{1,1,0,0,1,1}   2
{1,1,0,1,1,0}   2
{1,1,0,1,1,1}   1
{1,1,1,0,1,1}   1
{1,1,1,1,0,0}   2
{1,1,1,1,1,0}   2
{1,1,1,1,1,1}   3

With a normal row I mean every row other than the third row. The third row must contain one target car and I will call that row the target row. Each row arrangement represents a way a row can be filled with horizontal cars. In the lists, 0 means free, 1 means occupied. Next to the list is a number that gives the number of different arrangements that have the same cells occupied. For example, the list {1,1,1,1,1,0} in normalRowArrangements has the number 2 next to it, because you can have first a 2-width car and then a 3-width car, or vice versa. And the list {1,1,1,1,1,1} in targetRowArrangements has the number 3 next to it. This row consists of three 2-width cars. One of the three must be the target car, hence the number 3.

columnArrangements (64)
{0,0,0,0,0,0}   24
{0,0,0,0,0,1}   13
{0,0,0,0,1,0}   7
{0,0,0,0,1,1}   7
{0,0,0,1,0,0}   8
{0,0,0,1,0,1}   4
{0,0,0,1,1,0}   4
{0,0,0,1,1,1}   4
{0,0,1,0,0,0}   8
{0,0,1,0,0,1}   4
{0,0,1,0,1,0}   2
{0,0,1,0,1,1}   2
{0,0,1,1,0,0}   4
{0,0,1,1,0,1}   2
{0,0,1,1,1,0}   2
{0,0,1,1,1,1}   2
{0,1,0,0,0,0}   7
{0,1,0,0,0,1}   4
{0,1,0,0,1,0}   2
{0,1,0,0,1,1}   2
{0,1,0,1,0,0}   2
{0,1,0,1,0,1}   1
{0,1,0,1,1,0}   1
{0,1,0,1,1,1}   1
{0,1,1,0,0,0}   4
{0,1,1,0,0,1}   2
{0,1,1,0,1,0}   1
{0,1,1,0,1,1}   1
{0,1,1,1,0,0}   2
{0,1,1,1,0,1}   1
{0,1,1,1,1,0}   1
{0,1,1,1,1,1}   1
{1,0,0,0,0,0}   13
{1,0,0,0,0,1}   7
{1,0,0,0,1,0}   4
{1,0,0,0,1,1}   4
{1,0,0,1,0,0}   4
{1,0,0,1,0,1}   2
{1,0,0,1,1,0}   2
{1,0,0,1,1,1}   2
{1,0,1,0,0,0}   4
{1,0,1,0,0,1}   2
{1,0,1,0,1,0}   1
{1,0,1,0,1,1}   1
{1,0,1,1,0,0}   2
{1,0,1,1,0,1}   1
{1,0,1,1,1,0}   1
{1,0,1,1,1,1}   1
{1,1,0,0,0,0}   7
{1,1,0,0,0,1}   4
{1,1,0,0,1,0}   2
{1,1,0,0,1,1}   2
{1,1,0,1,0,0}   2
{1,1,0,1,0,1}   1
{1,1,0,1,1,0}   1
{1,1,0,1,1,1}   1
{1,1,1,0,0,0}   4
{1,1,1,0,0,1}   2
{1,1,1,0,1,0}   1
{1,1,1,0,1,1}   1
{1,1,1,1,0,0}   2
{1,1,1,1,0,1}   1
{1,1,1,1,1,0}   1
{1,1,1,1,1,1}   1

The columnArrangements variable gives the number of different arrangements of vertical cars in a column, given which cells are already occupied by the horizontal cars. For example, the list {1,1,1,0,0,0} has 4 next to it. In the free space {0,0,0}, there can be one 3-height car, one 2-height car in two different ways or no vertical car at all, which sums up to 4.

Now the C++ code will iterate over all possible combinations of row arrangements, which are $21^5 \cdot 16 = 65345616$ combinations. For each combination, it will look for every column how many vertical arrangements are possible, these numbers will be multiplied to each other. Also, for every row the number will be multiplied to the number of arrangements that that row can have given the list of free/occupied cells. The code is:

#include <iostream>

int normalRowCount = 21;
bool normalRowArrangements[21][6] =
{
    {0,0,0,0,0,0}, {0,0,0,0,1,1}, {0,0,0,1,1,0}, {0,0,0,1,1,1}, {0,0,1,1,0,0}, {0,0,1,1,1,0}, {0,0,1,1,1,1},
    {0,1,1,0,0,0}, {0,1,1,0,1,1}, {0,1,1,1,0,0}, {0,1,1,1,1,0}, {0,1,1,1,1,1}, {1,1,0,0,0,0}, {1,1,0,0,1,1},
    {1,1,0,1,1,0}, {1,1,0,1,1,1}, {1,1,1,0,0,0}, {1,1,1,0,1,1}, {1,1,1,1,0,0}, {1,1,1,1,1,0}, {1,1,1,1,1,1}
};
int normalRowMultiply[21] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 2};

int targetRowCount = 16;
bool targetRowArrangements[16][6] =
{
    {0,0,0,0,1,1}, {0,0,0,1,1,0}, {0,0,1,1,0,0}, {0,0,1,1,1,1}, {0,1,1,0,0,0}, {0,1,1,0,1,1}, {0,1,1,1,1,0}, {0,1,1,1,1,1},
    {1,1,0,0,0,0}, {1,1,0,0,1,1}, {1,1,0,1,1,0}, {1,1,0,1,1,1}, {1,1,1,0,1,1}, {1,1,1,1,0,0}, {1,1,1,1,1,0}, {1,1,1,1,1,1}
};
int targetRowMultiply[16] = {1, 1, 1, 2, 1, 2, 2, 2, 1, 2, 2, 1, 1, 2, 2, 3};

int columnMultiply[64] =
{
    24, 13, 7, 7, 8, 4, 4, 4, 8, 4, 2, 2, 4, 2, 2, 2, 7, 4, 2, 2, 2, 1,
    1, 1, 4, 2, 1, 1, 2, 1, 1, 1, 13, 7, 4, 4, 4, 2, 2, 2, 4, 2, 1, 1, 2,
    1, 1, 1, 7, 4, 2, 2, 2, 1, 1, 1, 4, 2, 1, 1, 2, 1, 1, 1
};

long long count = 0;

void add (int y, long long multiply, const int* index)
{
    int newIndex[6];
    if (y == 6) {
        for (int x=0; x<6; x++) {
            multiply *= columnMultiply[index[x]];
        }
        count += multiply;
    }
    else if (y == 2) {
        for (int i=0; i<targetRowCount; i++) {
            for (int x=0; x<6; x++) {
                newIndex[x] = index[x] | (targetRowArrangements[i][x] << y);
            }
            add(y+1, multiply*targetRowMultiply[i], newIndex);
        }
    }
    else {
        for (int i=0; i<normalRowCount; i++) {
            for (int x=0; x<6; x++) {
                newIndex[x] = index[x] | (normalRowArrangements[i][x] << y);
            }
            add(y+1, multiply*normalRowMultiply[i], newIndex);
        }
    }
}

int main (int argc, char *argv[])
{
    int index[] = {0, 0, 0, 0, 0, 0};
    add(0, 1, index);
    std::cout << count << '\n'; // outputs 49425302142
}

The program outputs 49425302142, which is approximately $4.9 \cdot 10^{10}$. It only takes a few seconds to run the program.