I'm going to imagine a slightly simpler game. Let's say in this version, the requirement that all of the little turtles get to come home is relaxed (we might leave some oh darn).
Let's now imagine the game level as a graph that we are interested in traversing. The open doors are edges. But then, let's imagine that the buttons are like another passageway... that is, instead of the red button, there is a path to 'another universe' where one thing is different... this other universe is just a copy of the graph with a new edge to represent the door we just opened. In technical jargon, we have performed something called 'graph rewriting'. Graph rewriting btw is a super profound and fascinating subject that connects to computer science, AI and biology . Now, essentially, we can just find a valid path in this new, much larger level to our destination. However, it's not immediately obvious how we actually go about solving this in practice... but one thing I start to think about - as a person solving the puzzle - is that I can visualize essentially clusters of universes, and put them into a partial ordering, and then eliminate the ones that don't make sense, eventually constructing a valid set of moves for my agent to reach the destination. As an example from your game, there is a button at the end that opens some doors... obviously we can't walk through those doors before we have pressed that button, so in essence, we can eliminate walking through the alternate universe where those doors are open from the portion of our strategy leading up to us reaching that button [or a similar button in a alternate universe]. Basically we are just solving a maze at this point.
One of the interesting ideas that pops out of this, is we can offer players more radical challenges by doing more with the graph rewrite step. Like a simple example would be one door opens but another shuts. A more complex and fascinating option would be, some of the rooms take on a new arrangement. The challenge then becomes teaching the player how to handle these more extreme puzzles.