Level 3-1 is technically the first stage with multiple solutions, but it does not affect the next level. Level 4-2 is the first stage which really changes things.
oh yes I did see that trivial alternative for 3-1, I meant nontrivial multiple solutions, but you got that :). Thank you for confirming!
Out of curiosity, do you have a backend system for verifying solvability and solutions? If so, is it brute force, or something more elegant, even heuristics that cut down on the size of the possible solution space?
I do not have an automated solution. I do however have a couple of theories that checkout:
I know that in order to get a solution with crossed lines, you need at lest one tile with crossed lines.
I also know that a set of tiles can solve any puzzle if every line can reach every position (assuming the size of the puzzle is big enough). That's also why I slowly increase the puzzle size as the puzzles get more complicated.