Here’s an interesting little puzzle posted by Ryan Ng on Google+:

A 5 digit number is written on a whiteboard. Ron erases one of its digits and adds a newly constructed number to the original one. The result is 41751. What is the original number?

It can be easily solved with constraint programming and I’ll demonstrate how to do it using AMPL and Gecode. The model is very simple, it’s just a few lines of code:

`Digits`

is a set of digit positions starting from 0 for the least
significant digit. The digits themselves are represented by the variable `d`

.
As the name suggests, the variable `original`

holds the original number
that we are looking for. It is defined in the constraint `define_original`

using variables `d`

. And finally, `relation`

specifies that there should
exists a number obtained from the original one with one digit removed
which, when added to the original one, gives 41751.

We can use a free student version of AMPL to solve this model. The Windows version of AMPL is available from the download page on the AMPL website. Versions for other platforms are available from the AMPL repository on Netlib.

The model uses constraint programming (CP) features or, more specifically, logical constraints. So we need a CP solver such as Gecode to solve it. Gecode binaries for AMPL are available for download from the GoogleCode AMPL page.

Once AMPL and Gecode have been downloaded and extracted, and the model saved
to the file `puzzle.ampl`

, we can run `ampl`

and solve the the problem:

```
ampl: model puzzle.ampl;
ampl: option solver gecode;
ampl: solve;
gecode 3.7.3: feasible solution
63299 nodes, 31647 fails
ampl: print original;
37956
```

This gives the solution 37956. To see which digit was erased, subtract
`original`

from 41751.