This IS a very interesing and inventive simple idea! First time I let it generate for too long and got locked ... second time I thought oh this is kinda cool.
I believe you could add some disadvantages or things that limit or change the type of movement your player can make ... one that I thought out of a sudden was ... since its grid based, one of these modifierss could be like, "your piece moves like a knight in a chess board" ... it would make this even more challenging and with kinda infinite possibilities to compete in the craziest combinations of puzzle+mod