3 ms·

That's a cool puzzle! It's the same as the Bridges of Königsberg, right? If each square is a node, connected by edges to adjacent squares, then it's only solvab

That's a cool puzzle! It's the same as the Bridges of Königsberg, right? If each square is a node, connected by edges to adjacent squares, then it's only solvable if there are at most two squares with an odd number of edges. Think about it like this: except for the squares where you start and finish, you must use one edge to enter and another to leave. I guess the Zelda puzzle is different because in Königsberg you can revisit islands, just not recross bridges. But that feels like something you can finesse somehow. . . . Ah, just swap nodes & edges, right? Squares : bridges :: sides : islands. Indeed, that lines up not just the restriction but the goal too. EDIT: Oh your second link is a much nicer solution. But still it feels like there is a relationship to Königsberg.

vikingerik 5y ago
The Zelda puzzle isn't the same as Königsberg because in Königsberg the goal is to traverse every edge, while the Zelda puzzle doesn't care about that. Think about the rows of tiles along the edges of the room - the Zelda room has dozens of tiles with 3 edges each, but it's no problem walking across them exactly once. You enter each tile from one edge and leave by a second, and it doesn't matter if you never traverse the third edge. Swapping nodes and edges doesn't work, because many of the Zelda nodes have 3 or 4 edges, but an edge is defined as 2 endpoints. It doesn't make sense to talk about an edge with 3 or 4 ends. The proof of non-solution to the Zelda puzzle is a simple checkerboard argument. The room's dimensions are 13 x 9, both odd, so all the corners are the same color (call it black) and there is one more black square than white. And the prize square replaces a white square. So there are two more black squares than white squares, making the problem unsolvable, since you must always alternate visiting white and black squares. The statues are a red herring - there are two on each color and so they don't affect this proof.

vikingerik 5y ago

The Zelda puzzle isn't the same as Königsberg because in Königsberg the goal is to traverse every edge, while the Zelda puzzle doesn't care about that. Think about the rows of tiles along the edges of the room - the Zelda room has dozens of tiles with 3 edges each, but it's no problem walking across them exactly once. You enter each tile from one edge and leave by a second, and it doesn't matter if you never traverse the third edge. Swapping nodes and edges doesn't work, because many of the Zelda nodes have 3 or 4 edges, but an edge is defined as 2 endpoints. It doesn't make sense to talk about an edge with 3 or 4 ends. The proof of non-solution to the Zelda puzzle is a simple checkerboard argument. The room's dimensions are 13 x 9, both odd, so all the corners are the same color (call it black) and there is one more black square than white. And the prize square replaces a white square. So there are two more black squares than white squares, making the problem unsolvable, since you must always alternate visiting white and black squares. The statues are a red herring - there are two on each color and so they don't affect this proof.