The level generation is indeed random. No level should be impossible however: they are generated by building a solution to them (some are very difficult to solve, however, as you may have to perform complex combinations of moves of the enemies and of the player character).
Also, in case of emergency (I may have mad a mistake in the validity check of the random levels) there is a reset button that allows to get a fresh new level at any time. I don't remember which button it was as I made the game quite some time ago, but you can find it in the tuto,