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:
- You are assigned a designated starting square, somewhere in the room.
- From your square, you can move to an adjacent square on your left, right, up or down (but not diagonals).
- Once you leave a square, it will shift from blue to red.
- You can't go back to red squares.
- 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).
- 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)?