Mark Gritter (markgritter) wrote,
Mark Gritter

Yet More Algorithmic Solutions to Brain-Teasers

New Scientist Enigma 1712 asks for a set of squares that use each digit zero through nine, twice. The sum of the set of squares should be as small as possible, the squares are all distinct, and 0 is not a leading digit.

My thoughts on approaches to solving this algorithmically:

1) Cast as an optimization problem on N variables where N is the maximum number of squares to be considered.

MINIMIZE 1*x1 + 4*x4 + 9*x9 + ...
1*x1 + 1*x16 + 1*x81 + ... = 2
1*x25 + 1*x121 + ... = 2
all x* are binary.

Seems feasible but a pain to set up, and no particular reason to believe that ILP would do well. A little vigorous handwaving tell you that the search space is bounded by N <= 10000. Which is still enough variables that some better bound would be good.

2) Visit all sets of squares in numerical order, find the first set whose digits match the condition.

At first I thought that the order could be done just by binary counting, but because these are squares and not powers of two it is a bit more difficult to define the order than that. Lots of opportunities for branch-and-bound optimizations but it seemed a bit more involved than I wanted to get into.

3) Dynamic programming keyed by the digit count.

Build up a table: digit counts -> sum of squares cost. Then for each new square, add the new digit counts (and cost) to all the existing entries, and add the results back as new table entries. Replace any entries where we find a lower-cost solution. Throw out any sums of squares where any digit count exceeds 2.

The first time we visit [2, 2, 2, 2, 2, 2, 2, 2, 2, 2] might not be the minimal cost. We can stop searching, though, when the next square is greater than the best cost so far.

This was pretty easy to code up (85 lines of over-verbose Python) and works quite quickly. I estimate that somewhat more than half the run time is spent verifying the solution after it has been found for the first time. The table has only 12201 entries when the algorithm terminates.

I emailed in the solution for my chance at 15 GBP. :)

However, it occurs to me that my implementation may be incorrect. If the second time we hit a digit set has a smaller cost than the first one, any derived sets are now suspect--- I didn't take that into account. The table should be built row by row in order of sum(digit count.)
Tags: programming, puzzles
  • Post a new comment


    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.