Brute force away, it's much faster than you think.
Here are some back-of-the-envelope numbers:
First of all, given a band of 30 digits, there aren't going to be very many ways to choose a spot where all 9 digits are unique. But let's assume there are 30.
Adding a second such strip, and checking the sudoku squares constraint, the first digit will fit with 6/9 probability, the next one with 5/8, and the third with 4/7, so you have about one in four chance of matching the first square. Out of the 30 possible second strip positions, this leaves about 8, out of which there is a slim chance that any one will satisfy the squares constraints. Let's say that one always will. (EDIT: turns out there is exactly a 1 in 30 chance of a random valid sudoku row satisfying the square constraint with another random valid sudoku row, so our estimate was way too accurate for this kind of calculation.)
So, after the second band, we have performed about 900 checks, and we have about 30 candidates left
Checking the square constraint for the third band then, it is pretty much guaranteed that no position will fit. Since each square has its three numbers dictated by the square constraint, there are exactly 216 possible rows among the 362880 (nine factorial) valid sudoku rows, and the probability of a random one fitting is therefore 1 in 1680. So the third band isn't really going to fit unless the bands are designed with that property in mind, but for argument's sake, let's say we find one such combination for each candidate anyway.
After the third band, we have performed about 1800 checks, and we are left with 30 plausible configurations, since we were extremely generous.
From then on, each digit will also have to be different from the three digits on the earlier bands, so the probability of finding a valid position for the next band is going to fall even faster. This means that adding more bands to the mix doesn't add exponentially many new positions to check, instead the number of plausible candidates will start to decrease after each additional band, no matter how generous we are.
From these numbers, it would seem that a brute force check should be easily doable in an hour or less; given enough caffeine, it should be possible even manually.