Do you need a story in the first place? I mean, if it's puzzle players probably would not care anyway. Note that not all games require story (Tetris does not for example ).
Also skeleton stories might work here. Like no text, but you see a kitten on the other side of the river, when you reach the animal the level is completed (story being obvious here).