My Constraint Programming Blog

The last week I have solved some (more) of New Scientist's Enigma problems. Note: You may have to be a subscriber to read all the articles, however there is a grace period with some free peeks (7 it seems to be).

Enigma problems

Here are the new models of Enigma problems. All are written in MiniZinc.

• enigma_counting_pennies.mzn: Enigma Counting pennies (from 2005)
  Here all the 24 ways of permuting a list of 4 items are needed. Instead of calculating them, I simply listed all the variants and used them later as index.
• enigma_843.mzn: Enigma How many are whole? (#843)
  In this model there was problem using the following type of reifications:

    square(ONE) /\ ( square(TWO) \/ square(THREE) \/ square(FOUR)) % /\ ..
    % or
    (square(ONE) /\ ( bool2int(square(TWO)) + bool2int(square(THREE)) + bool2int(square(FOUR)) = 1) % /\ ...
  

  where square is defined as:

  predicate square(var int: y) =
    let {
       var 1..ceil(sqrt(int2float(ub(y)))): z
    } in
     z*z = y;
  

  In some of the later versions of MiniZinc (probably 1.0.2), the handling of reification was changed. My fix was to add a boolean matrix which handled the boolean constraints. It is not beatiful:

     % In the list ONE TWO THREE FOUR just the first and one other are perfect squares.
     square(ONE) /\ 
     [bools[1,j] | j in 1..4] = [square(ONE),square(TWO),square(THREE),square(FOUR)] /\
     sum([bool2int(bools[1,j]) | j in 1..4]) = 2 /\
     % ...
  

• enigma_1530.mzn: Enigma Tom Daley (#1530)
  A simple alphametic puzzle.
• enigma_1535.mzn: Enigma Back to front (#1535)
  Magic square with some more constraints.
• enigma_1555.mzn: Enigma Not a square (#1555)
  Another alphametic puzzle on a grid.
• enigma_1557.mzn: Enigma Reverse Division (#1557)
  Division and reversing some numbers.
• enigma_1568.mzn: Enigma Odd puzzle (#1568)
  Long multipication alphametic puzzle.
• enigma_1570.mzn: Enigma Set of cubes (#1570)
  Pandigital problem over at set of cubes. Here I simply listed the cubes between 0^3 and 1000^3 instead of calculating them. This may be consider cheating...
• enigma_1575.mzn: Enigma All our days (#1575)
  Another alphametic puzzle with some more constraints.

Some of these problem may have been better solved using other means, e.g. pure (or not so pure) mathematics, but this is after all a blog about constraint programming, and modellng them is good exercise. And fun.

I have also solved - or at least modeled - some of the open problems: 1573, 1574, 1576, and 1577, but will not publish the models until they are closed. I "accidentally" published problem #1574 the other day before I realized it was still open, but so be it.

Some other models/data files

Here are two simple new problems taken from Choco's (forthcoming site ) example distribution:

• candles.mzn: Birthday Candles
• how_old_am_i.mzn: How old am I

Also, a new data file for the Bridge and Torch model: bridge_and_torch_problem8.dzn, which is, as I understand it, the same as Choco's U2planning problem.

Birthdays 2010 puzzle

Last, here is a very simple puzzle of my own based on a coincidence of birth years of me and my brother and the current year:

This year (2010) my older brother Anders will be the same age as the year I was born in the last century, and I will be the same age as the year he was born in the last century. My brother is four years older than me. How old are we this year?

A (unnecessary complex) MiniZinc model of this problem is birthdays_2010.mzn. Of course, it can be solved much easier with the simple equation: {H+A=110,A-H=4} (link to Wolfram Alpha), or in MiniZinc:

constraint H+A = 110 /\ A-H = 4;

But this latter version is not very declarative, and I - in general - prefer the declarative way.

Update: Added link to Wolfram Alpha for the simple equation above.