### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,158)
- misc (2)
- project euler (2)
- puzzle (40)
- site news (44)
- tantalizer (42)
- teaser (3)

### Site Stats

- 178,002 hits

Advertisements

Programming Enigma Puzzles

3 February 2014

Posted by on **From New Scientist #1311, 24th June 1982** [link]

This is a bird’s eye view of my present water store. I got 16 cuboids each 1′×1′, with lengths of 1′, 2′, …, 16′. I stacked them all on end on a level 4′×4′ base and glued them together in that position. As you can see the store’s capacity is 9 (cubic feet). My glue is strong enough to waterproof corner joints, e.g. between 4 and 7 or between 8 and 11. So 3 cu. ft. will stand on number 1, but any more will spill out over 4. And 6 cu. ft. will stand on number 2.

You will notice I could have achieved a bigger capacity with my 16 cuboids. In fact, I could have got 26 cu. ft. But I need something much bigger than that. So I am going to start again with a fresh supply of 64 cuboids, each 1′×1′ again of length 1′, 2′, 3′, …, 64′.

If I stack these on end on an 8′×8′ level base, so that they will hold as much water as possible when glued together, what will be the capacity in cubic feet? I don’t mind if the water is stored in one connected “tank” or (as with my present store) in more than one.

[enigma166]

Advertisements

%d bloggers like this:

I think this is a tough problem to solve programatically, so I’ve added it to the list of Challenging Puzzles.

I have coded up a Python program that finds a solution that agrees with the solution published in New Scientist, although I need to clean the program up a bit before putting it up here. I’m interested to hear about any programmatic approaches other people have tried.

Solution:The maximum capacity achievable on an 8’×8′ base is 946 cu. ft.Here is an example of a maximal solution:

The deep blue area provides the main tank with a volume of:

The four light blue areas provide an additional:

giving a total volume of 946 cu. ft.

The 24 deep blue squares can appear in any order, as can the 16 orange squares surrounding them, and the 12 white squares (which play no part in holding the water). The lighter blue and lighter orange squares are arranged to give the largest additional volume in the light blue areas.

Here’s my cleaned-up (and tweaked program). Unfortunately one of the tweaks makes it more correct, but means it does a lot more work. So while it displays a minimal solution in about 20 minutes, I think it will take a long time to run to completion and verify that it is indeed the best solution.

The algorithm starts with a specified region of the grid (initially for an 8×8 grid we specify the 6×6 central portion) and generates sub-regions of this initial region and considers each as a water holding tank. Then the procedure is applied recursively to any squares remaining from the initial region to add in the maximal volume made from those squares. The volume of the main tank is added to the maximal volume from the remaining squares to give an overall volume, and the maximum from these overall volumes is selected.

My original code just tried to fill in the remaining squares, rather than applying the procedure recursively to get a maximal solution. While this was quicker it was a less thorough search. Unfortunately the recursive call means the collection of regions is explored in a depth-first fashion (when a breadth-first search would probably find maximal solutions sooner).

The sub-regions are generated breadth-first in order of decreasing size. This means that, if a large main tank makes up the lions share of the volume, then a maximal solution will be found sooner, rather than later (but the code will still need to run to completion to make sure that the solution is maximal). A depth-first approach would be easier to program.

There are also a couple of fairly reasonable (I think) assumptions made:

The sub-regions are generated by nibbling away at the edges of the region. A square can be removed if it only has one neighbour, or if it has two neighbours and removing it wouldn’t disconnect them.

The calculation of volumes follows a “greedy” strategy. So the maximum volume of a region is made by using the smallest available values to make the internal squares of the region and the largest available values to make the external “wall” surrounding it. The grid that is output as a solution only contains partial information as to the placement of the blocks, so this strategy needs to be followed to reconstruct a maximal solution.

Overall this algorithm will work best for large single regions, or large single regions with a few extra tiny regions, it will get hopelessly bogged down on larger grids. Fortunately the solutions seems to follow the pattern that a large “main” tank plus some small extra tanks give a maximal solution.

Here are maximal solutions that I found for 3×3 to 7×7 grids:

To maximise the volume we are looking to enclose the maximum possible area with the smallest possible perimeter, so I suppose it makes sense that as the grids get larger the regions approximate to circles.

I derived the general formulae for larger odd and even grids which are the obvious extensions of the7x7 and 8×8 grids given.

I found that the total volumes in light blue squares are 29 and 70 for ALL odd and even squares respectively.

This is indeed a tough programming challenge, one that I am still thinking about! Congratulations on gettinng a programmmed solution that runs in a reasonable time. My initial thought is to start with the blocks 64 downwards on the outside cells except the corners and 1 upwards on the inside as a starting point and then see if swapping blocks can improve on this. But I haven’t convinced myself that swapping blocks will lead to a solution.

My program eventually completed after 17h26m (although it finds the solution in a few minutes, it just doesn’t know it’s maximal until it’s finished). I’m not sure if that counts as reasonable, but it reassured me that the published solution was probably correct. I need to tidy my program up a bit before publishing it though.

For what it’s worth I get a maximum volume of 488 for the 7×7 case in 2m32s. Which is the smallest size for which a single tank is not optimal.

Can someone please explain this puzzle to me? Surely the water can stand 4 ft deep in compartment no. 1 before it spills, and 8 ft deep in no. 2. Then each of the others can be full, so the total capacity is far greater. Am I just stupid, or is it very badly expressed? I rejected this one as incomprehensible when I found it in a bound volume of NS in the library ten years ago, and it still makes no sense to me after reading the solution and other comments.

Aha! I get it now. They’re solid blocks of the given height. I was assuming hollow rectangular containers of that depth. Silly me!

Yes, that’s right. The cuboids are solid blocks, not open at one end.