match 3 Shuffling

I'm interested in hearing about to implement similar functionality to Candy Crush's shuffling. I have an algorithm to determine if there are any matches available and if there aren't, I want to shuffle the board ensuring there aren't any matches immediately after reshuffling but there is at least one potential match. I have some ideas in mind but I'm interested to see if there are any more efficient ways of doing it.

Thanks

Check:

1. Loop over all tiles and check for matches (first loop over all rows horizontally and check for 3 in a row then check vertically same way).
2. If no matches found - shuffle, else - exit.

Shuffle:

1. Make a list of all available items.
2. Loop over all positions, for each position assign a random item from the list ensuring that no condition is violated (in this case no match is made).
3. If you can´t find a valid item restart the algorithm.
4. Run the check algorithm for finding potential matches if none found rerun shuffle.
5. (Optional) If more than a certain number of shuffles have occurred clear the field and restart with different items.
• That could be really performance intensive though, what if it doesn't find a match over a large number of iterations? Jul 3 '14 at 10:03
• Could be most likely won't be. Most of these games will easily find a good solution unless you have a very large or small number of items. (this should work without any noticeable lag with up to 20 items or as little as 3 on a 20 by 20 board). Jul 3 '14 at 11:05
• I tend to be uncomfortable with solutions that will most likely not be expensive. I'd rather use a solution with more expense but is guaranteed to be at a certain level of expense, rather than variable. Jul 3 '14 at 12:30
• This algorithm will on average in n*m step and only very rarely will it have repeat (a 20*20 field with 6 types has a less then 5% chance of having to repeat). Because of it's relation with the knapsack problem, this means that just a 10 by 10 field is not going to be solved before the heat death of the universe, you choice of course. Jul 3 '14 at 15:41
• @Lucas I think you should re-evaluate that sentiment. Stochastic algorithms are used in many places, even performance-critical ones (e.g. generating a random unit 3D vector). Sure it's theoretically possible for this algorithm to never terminate, just as it is theoretically possible to flip heads on a coin 100 times in a row, but that's less likely than being struck by lightning thrice. At some point you'll have to say "this is statistically impossible" and leave it at that. Jul 4 '14 at 1:13

I'm currently experimenting with a similar game-concept and what I do is the following:

1. Iterate through columns (vertical) and check for 3 consecutive items of the same type. If that occurs, replace the last item of the match with a random, but different item. If one item has been changed, set a changed flag.
2. Do the same for rows (horizontal). Also set the changed flag if any item was changed.
3. Repeat the above two steps as log as the changed flag is set.

This could also potentially result in lots of iterations but is quite unlikely. Certainly it will be more efficient than re-shuffling your whole board every time.

Addendum: Please don't refer to these kinds of games as "Candy Crush". Match-3 would be the neutral wording.. or "Bejeweled" if you have to use brand-names ;)