Under pressure, I suggested the following:

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.