18
$\begingroup$

In the puzzle game Pipes, a space-filling tree of pipes (which may have either one, two, or three neighboring connections each, but not four) is scrambled by a series of tile rotations, and the goal is to reconstruct the solution. To do so, you may rotate any tile, including the "source" tile (marked with a red circle), any multiple of 90°. (Note: "space-filling tree" means every tile/square must have a pipe part on it, and no loops are allowed)

Main puzzle statement: Is it possible for a Pipes puzzle to have multiple solutions (equivalently: is it possible to transform one tree into another via rotations)? What might be the smallest $N$ for which this can happen on an $N \times N$ grid?

Easier analogue: Pipes Lite is a fictional alternative in which pipes may have only one or two neighboring connections each. Is it possible for a Pipes Lite puzzle to have multiple solutions?

More difficult analogue: Is it possible for a Pipes puzzle to have no possible tile orientation deductions from the outset? That is to say, any individual tile has at least two orientations belonging to separate solutions?

                                enter image description here

$\endgroup$
2
  • $\begingroup$ I would accept either an answer to the "more difficult analogue" or "main statement"; the "easier analogue" is meant just to whet the appetite, although if nobody answers the other two after a while, I would accept the easier analogue's answer and then provide my own for the main statement. The answer to the more difficult analogue is currently unknown to me. $\endgroup$
    – Feryll
    Apr 10, 2021 at 0:45
  • $\begingroup$ Is it required that the grid be square? $\endgroup$
    – Deusovi
    Apr 10, 2021 at 3:01

2 Answers 2

17
$\begingroup$

Answer to the "more difficult" question:

I claim that

yes, it is possible

and here's why:

enter image description here
Here are two solutions to a Pipes puzzle where no pipe is in the same orientation in both solutions.

Easier analogue:

I claim that

No, it is not possible.

and here's why:

There is a single solution to any Pipes Lite, which can be found as follows:
Say that each tile is labelled with "straight", "turn", or "dead end".

enter image description here
We're going to mark each border between two segments with "wall" or "pipe" to reconstruct the solution:

Mark the edges all around the border with "wall". Then, for any straight tile, we can copy its marking to the other side; for any turn, we can copy the other marking to the other side.
enter image description here
Here, I've marked the walls on the left side, and then done the transfer for the first column.
And here, it's done for the second:
enter image description here

This can be repeated starting from all four directions, not doing transfers at dead ends:

enter image description here
And the solution is directly drawn out. (If the dead ends are in the same row or column, you may need to do transfers with the dead ends first - if all three sides are walls, draw a pipe in the remaining direction, otherwise draw a wall. Then you can continue as normal, and finish drawing the loop.)

Normal question:

It's possible to do with 4×4:
enter image description here

It's not possible to do with 3×3:
- If a corner piece changes, it must be a dead end; it forces the cell next to it to be a turn...
enter image description here
...and that forces the other corner to be a dead end. This continues around the whole board, and then the center is forced to be a +, which is disallowed.
So no corner pieces can change between solutions, so no edge pieces can change between solutions, so the middle cannot change between solutions.

$\endgroup$
4
  • $\begingroup$ Very well done! I am curious, how did you go about solving the more difficult analogue? Some clever candidate pruning? By hand or by machine? $\endgroup$
    – Feryll
    Apr 10, 2021 at 20:58
  • 1
    $\begingroup$ Oh, I see; you did it via finding an example of a puzzle with piece symmetry about a 180 degree rotation, not using any straights. $\endgroup$
    – Feryll
    Apr 10, 2021 at 21:01
  • 2
    $\begingroup$ @Feryll Yep! (And with none of the pieces matching their rotationally-symmetric counterpart.) I started by "proving" that an odd×odd grid wouldn't work (at least at the scales I was using), then I "proved" that an even×even grid wouldn't work. I then desperately tried to search for a mathematical proof that it was impossible, and failed to find anything. After that I "proved" that I would need at least two endpoints along an even edge (besides the forced ones in the corners), and a bit of trial and error led me to this. [...] $\endgroup$
    – Deusovi
    Apr 11, 2021 at 0:14
  • $\begingroup$ [...] (Read all instances of "proved" X in the above as "convinced myself after a lot of brute force that X probably didn't work as an option, and didn't particularly want to keep bashing.") $\endgroup$
    – Deusovi
    Apr 11, 2021 at 0:16
0
$\begingroup$

Here’s a solution that has only some non-unique pipes. My strategy is having that sort of outer parity loop, and filling in the middle in any way. This can be made for any odd square, and I believe the inner fill for a 5x5 is impossible using this strategy. Wouldn’t be shocked if you could do something similar with a 6x6, and I will look into it some more.

enter image description here

$\endgroup$
1
  • $\begingroup$ incidentally the rot13(jryy xabja fjnfgvxn flzoby pna or snpvat evtug be yrsg) on a 3x3 grid except it violates the rule of no pipe having four connections. Therefore it is not surprising there does exist example grids with multiple valid solutions (for larger grids obviously) $\endgroup$
    – happystar
    Apr 10, 2021 at 6:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.