They must be generated. Hand designed levels probably wouldn't have things like pawns on the first rank, or four opposing rooks, or situations where the first move unavoidably loses points.

I had a similar thought, randomly generated in 'strength'/points and positions. Pawns on first row are impossible, and last row turn to Queens (or whatever).

There must be a 'relative position' though in the mix of the algorithm, because on some levels the pieces are scattered in the four corners and some others they are on 'perfect-knight-stepping-sequence' so I could take 5-6 pieces in 5-6 moves and then exit.