I have an idea for a puzzle-platform game where the levels would be randomly generated. Creating a random generation is relatively simple. What's not easy is checking that randomly generated level to see if it's possible to complete, or generating a level where completion is possible. I think there are a number of different ways to do this.
Are there any games that employ something like this? How is something like this typically done, if ever?
Since I don't know the way a level is implemented in your game, I will give a general answer.
Typically, the game has a set of known rules (constraints) by which it operates. You need to apply them in your validation algorithm.
My solution for a (I assume) complex game like yours would be, as follows.
After the level has been generated, run a simulation. If the simulation solved the puzzle, you're done. Otherwise, fix the existing level or generate a new one and start over.
A simple example of this can be seen here, where he first generates a world according to a few simple rules (making corridors), places his agents on map and runs simulation to validate the level. If simulation fails, he tries to fix the level. If simulation is still failing, he generates a whole new world and starts over.
Alternatively, you could avoid the expensive game simulation by using a search algorithm like the A* algorithm, which can serve as a puzzle solver directly on your data structures. Another option might be evolutionary algorithms, although they can be quite computationally expensive and cannot guarantee valid levels.
EDIT: As DMGregory noted in the comments, you're better off generating a valid level as you go, rather than fixing it after it's been generated. This will most probably produce better levels and will be computationally cheaper. However, the implementation is naturally harder, especially when you're after complex level generation.
To create a concrete solution, you need to understand the movement constraints (or more so, the movement flexibility) in the platformer without the puzzle elements first. Like DMGregory said, for instance, you need to randomly place platforms within a jumping distance from one another. You also need to define a "possible jump". This jump must not be obstructed in later steps by additional platforms or elements.
After you have a valid platforming level generator, you can throw in puzzle elements without disrupting the initial constraints. For instance, add buttons that open doors, cause platforms (that were initially hidden) to appear out of thin air and so forth.
In order to provide a more specific answer, I must say that you could probably generate the platforms for a LIMBO like game but it appears to me the "puzzles" if you can call them that, are obviously hand crafted in that design.
Procedural generation is good for creating fresh, riveting new combinations of existing elements. In that specific case, it appears that it's pretty linear (the combination is not so important) and the puzzles just appear one after the other.
