In Talos Principle, from time to time player has to solve a puzzle that looks like this:
This puzzle is already solved - the blue slots on the right are the list of the possible blocks the user could use. They were placed in the grid so that they don't overlap and all spaces are filled.
The goal is to create a random puzzle generator that assumes that the grid is 8x8 and lists available puzzles (16 letters as output). All blocks from Tetris are allowed (I, L, J, O, T, S and Z) and we assume that the player can rotate them. In the screenshot, the matrix is 4x7 and the program would say that the player has to use two I blocks, two T blocks, two Z blocks and one L block (rotated). The program should generate a puzzle in a reasonable time (let's say a minute on a 1Ghz processor with 8 gigabytes of RAM)
Winning Criteria : shortest source code and running within reasonable time, explained above.