Generate random colors interview query

Recently got this question from a FAANG interview.

Given the game Bejeweled, where 3 or more of the same color either up/down/left/right causes an explosion. The player will then swap adjacent colors to cause the explosion effect. Create a random generator to fill in the colors of the board.

I suggested to generate the board first then if the board doesn't have one possible way to swap for an explosion, we can create that by swapping some of the colors. That was OK.

Then he digs into the random gen part of the question, I then suggest a set and a while loop to generate each color. The set are the colors I don't want to generate. However, this would cause collisions and the random generator may go on forever since it has a non-deterministic time complexity. He wants me to make a random generator that has a deterministic time complexity but still random while avoiding the create of explosions on the board.

I got majorly stuck on this and there doesn't seem to be much material on this subject of random deterministic time complexity algorithms.