### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

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

### Site Stats

- 168,282 hits

Programming Enigma Puzzles

22 August 2012

Posted by on **From New Scientist #2879, 25th August 2012** [link]

Find the set of perfect squares that between them use each of the digits 0 to 9 exactly twice and whose sum is as small as possible. Your squares must all be different, and 0 may not be a leading digit.

What is the sum of your set of squares?

[enigma1712]

Advertisements

%d bloggers like this:

This struck me as being somewhat similar to Enigma 1536, so I attacked it in a similar way. It runs in 285ms.

Solution:The sum of the set of squares is 2439.The chunking is a bit over the top – it’s much easier to compute the next square then it is the next prime, so it would be cleaner to just go up one square at a time.

Here’s some code that lets you specify the digit count pattern you are looking for, and it keeps a record of the smallest sum it’s found for each digit count as it goes along. So, to solve the original puzzle you would specify the digit count as 2222222222 (which is the default).

You can use it to determine that the minimum sum using each of the digits 0-9 three times is 6714 and using each of the digits four times the minimum sum is 12528. And (if you have the patience and the RAM) that using each of the digits five times the minimum sum is 17685.

Brian further improved this algorithm by encoding the digit count in hexadecimal, rather than decimal, and then using a neat bit of coding to check for overallocation of digits allows the elimination of superfluous intermediate results. So once the sum and largest square is found it becomes viable to re-run the algorithm with a modified digit count to find the next largest square, and so on until the required sequence of squares is determined.

Here is the result of our combined efforts:

Note that this algorithm will fail when the count of an individual digit exceeds 7, but as the algorithm is quite memory hungry it is more likely that it will run out of memory before this becomes a problem. Particularly when the program is being used to find solutions with homogeneous digit counts (such as required by the original puzzle).

After quite a bit of messing around here is what will probably be the final version of this algorithm.

This version packs the digit count into an integer using as few bits as possible, and also includes some tweaks to discard squares where the digit count exceeds the maximum digit count we are looking for. As the main routine is only interested in finding the smallest square for a specific digit count it no longer drags all the squares around, but just records the one for the digit count we’re looking for. And it provides the updates to the dictionary for each pass as a separate dictionary and merges them in at the end of the pass to ensure it doesn’t use a square twice.

It’s still however something of a memory hungry algorithm.

It takes command line arguments so you can specify the number of each digit you want to look for (e.g. as “9876543210” if you want each digit to appear its own number of times) and you can optionally specify the maximum square it should look for as a second argument.

Any of these general algorithms can also be used to provide solutions for Enigma 1518.

This one runs a bit slower, but gets the same answer as Jim

A faster version:

Here is my version:

If you’re short on time or RAM, and you have PyMathProg installed you can program up a solver to use GLPK to solve this Enigma. The following Python code (similar to my GLPK solution to

Enigma 1536) can find solutions for squares using each digit from 1 to 10 times in under 500ms.Here is a version of 1712 using the technique of my recursive solution to 1536.

This one constructs the optimal search sequence of digits in code (the sequence being the increasing frequency of the digit in the list of squares).

The performance is improved significantly by the converting the “containingsingle” and “containingdouble” entries to lists, so that smaller numbers are used first.

The program runs in about 90 ms