combinatorial matrix

Question

I have a matrix like this:

X marks the blank spot

A A A A
B B B B
C C C C
D D D X

How many rearrangement are possible ? And is there a formula? [this part answered].

If you follow the link, it says 24964 cells. I do not understand how he get this number ? walking distance heuristic

For a matrix like this :[15 puzzle]

 1  2  3  4
 5  6  7  8
 9 10 11 12
13 14 15  X

there is 16! possibility to rearrange them

Answer 1

Notice that there is a direct bijection between a matrix of the form $\begin{bmatrix}a_1&a_2&a_3&a_4\\a_5&a_6&a_7&a_8\\\vdots&&\ddots&\\\vdots&&&\ddots\end{bmatrix}$ and a string of the form $a_1a_2a_3a_4a_5a_6a_7a_8\dots$

Your question becomes "How many rearrangements of the string AAAABBBBCCCCDDDX exist?"

This is counted directly using Multinomial Coefficients as being:

$$\binom{16}{4,4,4,3,1} = \frac{16!}{4!4!4!3!1!} = 252252000$$

Note: this counts the number of arrangements, not the number of orbits of the puzzle, i.e. the number of arrangements which can't be transformed into one another via a sequence of moves such as sliding tiles.

Answer 2

To obtain 24964, do not distinguish between matrices which can be obtained from each other by permuting elements in the same row. So, for example, the following matrices are all equivalent:

A A A B      A B A A      B A A A
B B B A      B A B B      A B B B
C D C D      D D C C      C C D D
D C C x      C x C D      D x C C

Then 24964 is the number of equivalence classes of such 4x4 matrices, with 4 'A' elements, 4 'B' elements, 4 'C' elements, 3 'D' elements and one 'x' element. The permutation of elements in the same row is irrelevant; it only matters how many are there elements of each type in a given row.

See also this answer on Code Review Stack Exchange which mentions the walking distance heuristic.