Good versions (e.g., the aforementioned Taipei and Kyodai) construct the layout in such a way that it's always initially possible to win, although it might be extremely difficult (and still luck-based since you don't have complete information). Unfortunately, not all versions are good.
Most of these games are called "Mahjong" or some variant, which is wrong; their only connection to mahjong is that they're played with the same tiles, in the same way that bridge is played with the same cards as rummy. In both cases, the resemblance ends there. The name "Mahjong solitaire" is sometimes used as a generic name for this game.
There was some debate on the exact origins of the game. The official story is that it was invented by Brodie Lockard at the University of Illinois in 1981, but others say it was based off an older children's game called "Demolish the Turtle" from China.
Vegard Krog Peterson has a comprehensive guide to these games.