### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,115)
- misc (2)
- project euler (2)
- puzzle (29)
- site news (43)
- tantalizer (29)
- teaser (3)

### Site Stats

- 166,357 hits

Programming Enigma Puzzles

8 February 2015

Posted by on **From New Scientist #2413, 20th September 2003** [link]

Triangulo, the world-famous Cuban cubist, has created five boxes, each of which contains a number of cubes of the same colour, but with a different colour in each box.

At a master class, he tries to construct a particular size of cube using all the cubes from just two boxes. But whichever pair he selects, he finds that at least one pair has too many pieces and all the other pairs have too few.

Each different pair of boxes gives a different total of cubes and the largest total is 10 more than the smallest.

With a stoke of genius, using all the cubes together, he creates instead a flat square, multi-coloured masterpiece!

How many cubes (in ascending order) are there in each box?

This puzzle is **Enigma 1257** and the previous puzzle I published was **Enigma 256**, so there are now 1,000 puzzles left to publish (ignoring for the moment that sometimes multiple puzzles are published under the same number, and that I’ve already published **Enigma 1095**). Which means just under 44% of all *Enigma* puzzles are now available on the site.

[enigma1257]

Advertisements

%d bloggers like this:

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.