### Random Post

### Recent Posts

- Enigma 1065: Cute cubes
- Enigma 444: Rows and rows
- Puzzle 50: Football and addition
- Enigma 1066: Members of the clubs
- Enigma 443: The bells they are a-changing
- Tantalizer 455: Ballistico
- Tantalizer 456: Square deal
- Enigma 1067: Bye!
- Enigma 442b: Oh yes I did! Oh no you didn’t!
- Puzzle 51: A multiplication

### Recent Comments

Brian Gladman on Enigma 1065: Cute cubes | |

Jim Randell on Enigma 1065: Cute cubes | |

geoffrounce on Enigma 444: Rows and rows | |

Jim Randell on Enigma 444: Rows and rows | |

geoffrounce on Enigma 1611: Three sister… |

### Archives

### Categories

- article (11)
- enigma (1,167)
- misc (2)
- project euler (2)
- puzzle (42)
- site news (45)
- tantalizer (45)
- teaser (3)

### Site Stats

- 180,599 hits

Advertisements

I think the setter intends for us to assume that the cubes in the boxes are all the same size.

I originally solved this puzzle by considering increasing square numbers and decomposing them into sets of 5 distinct integers, but it is more efficient to examine the neighbourhoods of the cube numbers.

This Python program runs in 34ms.

Solution:The boxes contain 103, 104, 105, 107 and 110 cubes.Together the 529 cubes in the five boxes can be used to make a large square with 23 cubes along each edge, but no pair of boxes can make a large cube with 6 cubes along each side, as this requires 216 component cubes, and the number of cubes made by pairing up the boxes are: 207, 208, 209, 210, 211, 212, 213, 214, 215 and 217.

I didn’t think it was worth speeding this up so I stuck with your original approach.

I did try to write a MiniZinc model to solve this one. The model seems quite straightforward, but when I run it it doesn’t seem to enforce the constraint that the total number of cubes is a perfect square, so it produces incorrect answers (along with the correct answer if the

-aflag is specified).I don’t know if this is a problem with my model, or a problem with MiniZinc itself.

And here’s what happens when I run it…

I am very new to MiniZinc but I can’t see anything wrong with your model. The model compiles but gives no output on the Windows version of MiniZinc, which is different, so it might be a MiniZinc issue of some kind.

I checked Jim’s MiniZinc model and found some issues:

1) The constraint that doesn’t work seems to be a bug in G12/fd. The Gecode solver (http://gecode.org/) just show the single solution as does most of the other FlatZinc solver I tested. Some solvers throws “integer overflow” error (even when the domains are smaller, see below).

2) I recommend to use as small domains as possible instead of “var int”. This was one of the problem with Brian running on Windows using the MiniZincIDE: G12/fd throws an integer overflow error with “var int” but the message wasn’t visible in the IDE.

3) I modified Jim’s model somewhat with smaller domain and a search strategy which makes the model runs faster: 75ms compared to 2.7s with “solve satisfy”. This is the time for a fairly fast Linux Ubuntu machine. Here’s the model: http://hakank.org/minizinc/enigma_1257_boxing_clever_jim_randell2.mzn

Thanks to Hakan for looking at this (and for providing advice on using MiniZinc with other solvers). I installed Gecode x64 on Windows and it solves the problem (with Hakan’s optimisations) as follows:

Compiling jr2.mzn

Running jr2.mzn

boxes=[103, 104, 105, 107, 110], n2=23, n3=6: true

———-

Finished in 69msec

Thanks for the tips hakank. I downloaded the Gecode solver and using

mzn-gecodeon my original model does indeed give the right answer.(This is running on my laptop under OS X 10.10.2).

I liked that fact that I didn’t have to impose arbitrary limits on the search space in the MiniZinc model.

Jim: Yes, sometimes “var int” don’t matter and it’s great feature when writing the first version of the model. But for larger problems or one want to tweak the time, it’s important. As is testing different search strategies (instead of the standard “solve satisfy”).

A picky note: What I can see you just tested for the first solution. To “prove” that it is a unique solution, add either the “-a” or “-n 0” (or “-n 2”) parameter to mzn-gecode. The solution will presented by a “==========” before the statistics, which is the indication that the solver has checked all solutions. For this problem it took 41ms and 7ms respectively (on my fastest computer).

Whenever I have a larger problem, I test it with as many FlatZinc solver as possible, and often with Opturion CPX which can be quite fast: http://www.opturion.com/cpx.html . It has an academic license, but what I know it should apply to this kind of recreational programming. One feature of CPX is the “free” (-f parameter) might boost the performance. On this problem it’s a little slower than Gecode: 406ms and 57ms respectively.