1. Only one solution (or path in this case) should exist
2. No loops (meaning the valid solution does not cross it-self)
3. The length of false path from correct path should not be more than 4
I like the definition proposed in the post - all possible mazes should be equally likely. A function could return the same maze each time and pass the criteria above.