As far as power goes, this technique strictly dominates the seam-carving method that took the 'net by storm last year. However, it can't top the simplicity (and hence elegance) of the seam-carving implementation. I doubt anyone but the original publishers will be able to get a good version of this going without significant effort. Which might be what they intend...
I think the basic idea of randomly trying patches, and hill-climbing around ones that fit fairly closely, is a simple technique - but potentially very slow, if there's a low probability of hitting potential matches that can be improved by hill-climbing. They might have heuristics to improve it: for selecting likely regions to try (i.e. a prior probability density over the image); for choosing which neighbouring regions to try to improve a match (direction & offset); and for various ratios and thresholds (such as when does a region "fit fairly closely" and tradeoffs between this converges "well enough" that we won't keep on looking.)
However, I have a feeling that that haven't tuned these heuristics perfectly. They've just come up with the basic idea, and got it working. Images that hill-climb well, and user-selected regions that match up well will be very fast with this technique - the cool thing is that that covers most images that humans like to look at, and the kinds of edits that humans want to do. You could construct special cases that this method would perform terribly at: e.g. a user-selected region that only matches exactly one other region like that in the image, and such that these two regions do not "almost match" when they are "almost aligned", but only match when they are perfectly aligned.
But I bet it works great for most actual images and edits in practice. A few times, my eyes didn't register all the changes that have been made, because they look so natural. It also looks like fun.
