Have you tried the find it game? For my dog I often hide food caches (a small collection of kibble, or a medium sized treat) around the apartment for her to find. It's a fun 'puzzle' and since you decide where to hide the rewards, the difficulty level is adjustable. As my dog has gotten better at finding the hidden treats I've had to come up with more advanced places to hide them (inside old shoe boxes, underneath her dog bed...etc.) If you try this technique and your dog is already a bit destructive you might want to be extra mindful of where you hide the treats (so you're not encouraging your dog to destroy or mess up anything else)
For a more high tech solution there are weird robot toys that play with your dog while you're away...something like this: http://goifetch.com/
GoodI want to add that one of the best ways to make your dog less restless while your away is to tire your dog out while you are around. A tired dog is more likely to want to lie around the house while you're away. Good luck :)