Zelda - Oracle of Ages tiles rooms puzzles: how can you prove if there are/aren't solutions?

Question

In the Oracle games of Legend of Zelda, there are some puzzle rooms of this kind:

You are the green character on the bottom left. As you enter the room, all tiles (except for one, in yellow) are blue. The rules are:

1. You are assigned a designated starting square, somewhere in the room.
2. From your square, you can move to an adjacent square on your left, right, up or down (but not diagonals).
3. Once you leave a square, it will shift from blue to red.
4. You can't go back to red squares.
5. In the initial configuration, some squares will be 'forbidden'. In the screenshot, those are the ones with statues. You can't hop into them, but you also don't need to change their color (they can also be interpreted as 'holes' in the ground).
6. You solve the puzzle if you finish your path on the yellow square after changing every tile from blue to red.

If this set of rules is not properly defined, I apologize. The following gif from IGN of one of these rooms being solved may help visualize it better:

Through the game, these puzzles are you usually somewhat simple and have multiple solutions. However, the very last one, has this configuration:

As it turns out, it doesn't seems to be possible to 'solve' this room. No matter what path you try, you will eventually leave one blue tile *(I'm not claiming this as a fact, as i haven't seem a proof of this. But, considering the game, this seems to be what developers were aiming for: there is an in-game mechanic where you use an item to manually paint a single square as red - here is the intended solution:

.

The question is them: assuming you are given a rectangular room of some given size, with some set of (i) initial square, (ii) forbidden squares and (iii) ending square, is there a way (better than to try all possible paths) to be sure that no tile filling path exists? If so, is there a way to tell what would be the "best" result (in the sense of the path that leaves the smallest number of blue squares)?

Or, maybe if the general question is too broad, at least: how could the developers be sure that the last puzzle has no solution (apparently)?

Answer 1

For the "impossible room", recolour the blue squares and yellow goal square black and white in a chessboard pattern, such that the upper-left square is white. Then

• there is one more white square than black square
• you start on a white square
• the goal square is coloured black

If it were possible to solve the puzzle without using the Cane of Somaria, since every step goes from a white square to black and vice versa yet there is one more white square than black, you would have to end on a white square – i.e. the goal square would have to be white. But we coloured the goal square black, so we have to use the item.

When this puzzle is generalised to arbitrary graphs, this is the Hamiltonian path problem, which is NP-complete. Parity simply provides a way to quickly prove that there is no Hamiltonian path.