.99 for random access to all levels would be a no-brainer purchase. My other suggestion is to allow sub-optimal solutions, while letting the user know that they are sub-optimal. You could show the best solution so far, in blue if it's optimal.
If you're unaware of them, check out Lunar Lockout and/or Pete's Pike.
And I'll look into those!