One way would indeed be to try out the four possible moves for every tile (or rather the ones that have recently moved) and check for matches, then store them as hints. You wouldn't need to do this as often as you might think (especially if you only do it for tiles that have moved); you would only need to swap every tile twice since the one next to it would overlap its two other swaps. Like this:
Another way would be to check the surrounding tiles without simulating anything in the background. The best way to do that would be as follows.
Say you have a tile that just moved (center). Focus only on its color and the tiles that are occupied in this diagram:
Here are all possible matches for the four possible moves (6 blue, 6 red, 4 green):
However, you don't need to check for all of these. What you have is a decision tree; all you need to check are if the orange ones match your center tile. If they do, then you proceed to check the secondary ones. Here's a diagram that connects the orange tiles to their secondary tiles (notice how you only need to do four checks for the green matches and not 8 since the other 4 are the same):
Depending on what kind of data structure you store tile data in, these checks can be extremely fast to the point where you don't really need to do any significant optimization. I personally can't think of any other shortcuts.