I want to calculate the probability of a special situation in match-three-tiles games I am new here and it is my first time asking a question. I'm making a match-three game, like Candy Crush or Bejewed. For people who do not know, basically there will be a game board, the size may vary, and within the grid there will be different types of tiles. You want to match three same tiles in a straight line to cancel them and score. And now I want to figure out how large my grid should be, as it will majorly be played on mobile devices, it is impossible to have a very large grid, or it will be hard for players to choose tiles. However, as the tiles are randomly generated, there will be a chance where in the board, there is no move to make any match. So I cannot make the grid very small either. So I want someone to help me make a formula that given the grid size x*y, and z types of tiles, what is the probability that there will be no possible move on the board? Thank you very much!

I will assume three-in-a-row diagonally won't count as a cancel; just horizontally and vertically. I will also assume that by "possible move" you mean swap the position of two horizontally or vertically adjacent tiles. I will set minimum rows, columns, and number of colors to 3.

I know this isn't very elegant, but I built a Monte Carlo Simulation. I get this as a practical result:

Probability = $ \frac{1}{1+10^{-\alpha}}$ where $ \alpha $ is given by: $$ 0.24 * \frac{Rows*Columns - |Rows-Columns|}{Colors - \sqrt{Colors}} -0.578 $$

It should hold true enough for most Color/Row/Column combinations you might expect to use in your game. (fails for many colors and few rows/columns or for too many rows or columns)