4
$\begingroup$

You are managing the construction of 4 water pipes on a 8x8 grid. The rules are the following:

  • Each section of a pipe uses a whole grid cell. Pipes are composed of multiple sections connected orthogonally (horizontally or vertically).
  • Pipes can touch, but they cannot overlap (intersect). They must stay inside the cells of the grid.
  • Each pipe has a starting and an ending cell. You select those two cells for each pipe at once and the workers will place the sections of all the pipes. They will place them in a way that obeys the above rules and minimizes the total number of sections used.

Which starting and ending cells will produce 4 pipes with the most number of sections used?

$\endgroup$
5
  • $\begingroup$ I don't think I fully understand. Any way you can include a picture showing a simple example? The pipes cannot overlap, right? $\endgroup$
    – JLee
    Jun 11, 2022 at 11:23
  • $\begingroup$ pipes cannot cross or overlap $\endgroup$ Jun 11, 2022 at 11:25
  • $\begingroup$ I feel that a picture may give away the solution... $\endgroup$ Jun 11, 2022 at 11:26
  • $\begingroup$ Ok, makes sense. I think most of my confusion was thinking that it was a 4x4 grid, but now I see that the puzzle clearly says 8x8. Also, I now realize that the pipes do not have to start or end at the edge of the grid, but can start or end in any cell, right? $\endgroup$
    – JLee
    Jun 11, 2022 at 11:28
  • 1
    $\begingroup$ Maybe a picture that shows a really bad example solution? (so with each starting and ending cell next to each other, and a total length of 8) $\endgroup$
    – sqek
    Jun 11, 2022 at 11:31

2 Answers 2

7
$\begingroup$

Assuming you pick all 8 start/end points and then all the pipes get laid:

I think I've got

all 64 cells

but not sure if I can prove it's the shortest possible route, with these starting points:


╔══════╗
║╔════╗║
║║╔══╗║║
║║║╔1║║║
║║║║2╝║║
║║║║3═╝║
║║║║4══╝
432╚═══1

$\endgroup$
2
  • $\begingroup$ You got it! Well done. Nice ASCII diagram too. $\endgroup$ Jun 11, 2022 at 12:48
  • 1
    $\begingroup$ I confirmed via integer linear programming that this set of four pairs requires using all 64 cells. $\endgroup$
    – RobPratt
    Jun 18, 2022 at 21:39
0
$\begingroup$

Do you need to select all four pairs of cells before the workers start, then they pick paths that minimize the total number of sections used across all four pipes? Or can you select one pair, they pick a path for that pair (without splitting the empty squares into two or more disconnected sections), then you can select the next pair?

Either way, you can do at least this well:

A1-H8 B1-H7 C1-H6 D1-H5 which requires 48 squares.

If you can select the second pair after they pick a path for the first, then you can do at least this well:

1) A1-G7. Without loss of generality, assume that the path includes A2, in which case it can't include B1. Requires 13 squares. 2) H1-B1. Requires 21 squares. 3) B2-F5. Requires 8 squares. Let's assume the workers are trying to minimize how bad #4 can be, so they build this path through C2. 4) B3-G2. Requires 13 squares. (If they had gone through B3 on #3, then you could pick B6-C2 which would require 14 squares.) This uses a total of 55 squares.

$\endgroup$

Your Answer

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

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