Mh, maybe you can add a command which suggests the next move to the player. And to avoid abusing this, the player may have limited uses of it. This could be a solution, but I'm not a programmer, so I don't actually know how hard  implementing this would be. It's basically an AI who can solve the puzzle on its own but has limited moves.