Date: 10 Dec 1985 10:48:32 EST (Tue)
From: Dan Hoey <hoey at nrl-aic.ARPA>
To: Alan Bawden <ALAN at MIT-MC.ARPA>
Subject: Re: Attractive nuisances

  From ALAN@MIT-MC.ARPA Tue Dec 10 00:24:36 1985
  Date: Tue, 10 Dec 85 00:28:30 EST

  I was rather struck by the fact that the solutions for 7, 8, and 9
  spaces are unique.  I haven't seen the solutions for 11 and 12 spaces
  yet, I presume you have them?

The shortest 11-space ruler is unique: (2 4 18 5 11 3 12 13 7 1 9).
Took about an hour.  I haven't got any 12-space rulers, but I will run
it and get you the answer Friday, Grid willing.  If you have any other
particularly fruitful places where answers will help, I can get them.
But finding the 12-space rulers of length 107 might take a week.

    Then I have a neat cutoff for detecting that too many of the small
    distances have been used up, which I'll bore you with on request.

  This sounds very similar to an idea I was playing with for a while.

Not that similar, but yours is interesting.  I should have known I was
in for a wild new approach when I sent the note.

  I view the problem as one of placing the integers from 1 to N into
  (K^2+K)/2 bins arranged in a triangle ....

Neat!  If you put zeroes along the bottom of the triangle, then
ruler-nature is expressed by requiring that the sum of opposite corners
of each aligned parallelogram equal the sum of the other pair of
corners, like A+B=C+D and D=B+E below.

              .
            .   A
          .   .   .
        .   .   .   D
      .   C   .   .   E
    .   .   .   .   .   .
  .   .   .   B   .   .   .
    0   0   0   0   0   0

You continue,

  For example:

           17
         .   .
       13  A   .              .   .
     .   .   .   4
   .   .   .   .   X

  What values can A assume?  ... A can be no greater than 15 because we
  have to fit two -larger- numbers in the two spaces above it.

Here I think you mean A can be no greater than 14, since the two larger
numbers can't include 17.  The rest of the argument is right.

  Now perhaps a program that takes advantage of a whole batch of such
  trivial constraints before it takes any recursive search steps would be
  a winner.  You could even decide which cases to explore on the basis of
  what decision seems the most constrained in the current configuration.

  I have some ideas that might yield fruit, that I haven't implemented.
  For instance, suppose mark x has been selected, and marks x+d and x+2d
  are open.  Well, marks x+d and x+2d can't be both selected.  If x+3d is
  unavailable for some reason, then distance d is not available from mark
  x+2d.  If this elimination can be done enough times, we be able to
  eliminate mark x+2d from consideration.  This might speed things up if
  the bookkeeping isn't too slow.

  Just wanted to know you're not alone.  Let me know what you find.

Just when I thought I had abandoned this thing you remind me of it and here
I am getting inspired to think about it some more...