# Given 4 tile types, what are the chances that there are no sets of 3 in a 6x6 array?

I know this question seems arbitrary, but it actually applies to a matching game that I'm writing.

I randomly typed the following letters and created a 6x6 array using the letters A, S, D, and F.

ASDASD
FDASAS
DFDASD
FDAFSD

Note that there are many ways to match 3 or more tiles (allowing matches in all 8 directions). For example, let's hide all letters in that array to show only A's.

.A....
A..A..
..A.A.
...A..
..A...
A...A.

I can easily draw a line between 5 of those 9 A's.

I've found that I can randomly generate numerous random 6x6 arrays using 4 tile types and I never end up with an array with no matches of 3 or more adjacent tiles.

Yet, it is possible. If I very carefully lay things out I can create an array with no matches.

ASASAS
DFDFDF
ASASAS
DFDFDF
ASASAS
DFDFDF

So, what are the odds that I can randomly generate a 6x6 array like this and end up with no matches of 3 or more?

I would like to know for 2 reasons. I want to know if it's necessary to add something to my game to automatically prevent a matchless board from occurring. If the odds are low enough I can simply allow the player to give up if they work themselves into a corner with no matches.

The other reason is that I want to know how many tile types I can put into an array of size WxH and still have very low odds of no matches. If I have an 8x8 array, how many tile types can I have and still have the odds be less than 1 in a billion?

If I can answer the second question then I can set up the game to allow lots of different sizes of boards with lots of sets of tiles without me needing to play test every possible variant.

-
I'm not sure what exactly you mean by "I randomly typed the following letters", but I'd be willing to bet against great odds that that array of letters is not the result of uniformly randomly drawing letters from among those four -- the chance that there wouldn't be any horizontally adjacent identical letters is rather small. – joriki May 12 '13 at 20:51
You're right. I simply typed them without attempting any order and therefore they're not random in the same way that the pseudo random number generator used in the game is random. I just wanted to create an example. – HappyEngineer May 12 '13 at 21:13
The probability question is going to depend on the dimensions of the board, and is probably a mess. This is not an answer to your question, but you could simply perform breadth-first search on each tile, to check that no matches are left. You can quit at 3, as well, so you're only looking at 15 comparisons (8 neighbors + 7 new neighbors) per tile in the worst case. This is extremely efficient. – Eric Tressler May 12 '13 at 21:33
Also note that even an answer to the question will not be terribly helpful, because after a match is made and the tiles presumably removed, the remaining tiles are no longer i.i.d. random variables. – Eric Tressler May 12 '13 at 21:36
Yes, after a match is made the probabilities of a match would change, but I've been assuming that this actually increases the likelihood of matches because you just reduced the number of tile types in that area by one. In any case, I was hoping that this question matched up with a well known area of math. I don't really need precise results. I've heard of the "four color theorem" and this problem sort of feels like it'd be in that genre of questions. – HappyEngineer May 12 '13 at 22:16