IBM - Personal communication

This web page is devoted to my fortran programs for finding difference triangle sets by backtrack search. I also have programs dealing with Golomb rulers. Free fortran compilers for IBM PCs are available on the web.

dts2: Dts2 does an exhaustive backtrack search for difference triangle sets. It is based on the Golomb ruler exhaustive search program grs2. Dts2 usage instructions.
dts2x: Dts2x is a modified version of dts2 for use when a complete search would take too long. It allows the user to partition a complete search into numerous independent partial searches. Dts2x usage instructions.
dtsver: Dtsver independently verifies difference triangle sets found by above programs are correct. For usage see the instructions for dts2 or dts2x.

Instructions for dts2

Dts2 reads input variables n, k, nt (3i5 format) from the terminal (unit 5).

n is the number of marks per ruler
k is the maximum length allowed
nt is the number of rulers

Dts2 then finds all difference triangle sets consisting of nt rulers each having n marks and length at most k and with all differences distinct. Dts2 writes out the difference triangle sets as it finds them (up to a limit currently 10 determined by the nprint parameter) to the terminal (unit 6) and disk (unit 1). When it has completed the search it writes a summary to the terminal (unit 6). At this point the program may be given another search to do or be terminated by entering 0.

For example to find all golomb rulers with 13 marks and length 106 or less enter

   13  106    1

After a while dts2 will find a ruler

      0     7     8    17    21    36    47    63    69    81
    101   104   106

and then a bit later complete the search

 n= 13 k= 106 solutions=       1 time=           19.57 nodes=      49441242.

This may take a few hundred seconds on a slow machine. The program can now be terminated by entering

At this point disk unit 1 should contain the following

        13       106         1
     0     7     8    17    21    36    47    63    69    81
   101   104   106
         0         0

If dtsver is now run it will read unit 1 and verify that this is a difference triangle set. It will write to the terminal (unit 6).

        13       106         1
         0         0         0
          1 difference triangle sets verified

Instructions for dts2x

Dts2x reads input variables n, k, nt, nprune (4i5 format) from the terminal (unit 5).

n is the number of marks per ruler
k is the maximum ruler length allowed
nt is the number of rulers
nprune is the number of levels at which the search tree is pruned

Dts2x then reads nprune lines from the terminal (unit 5). Each contains variables ipos, ikeep and istart (3i10 format).

ipos is the level being pruned
ikeep is the pruning factor, keep every ikeep'th node
nstart determines which modulo class of nodes to keep

Dts2x then finds all difference triangle sets consisting of nt rulers each having n marks and length at most k and with all differences distinct in the pruned search tree. Dts2x writes out the difference triangle sets as it finds them (up to a limit currently 10 determined by the nprint parameter) to the terminal (unit 6) and disk (unit 1). When it has completed the search it writes a summary to the terminal (unit 6) and disk (unit 2). At this point the program may be given another search to do or be terminated by entering 0.

For example to do a partial search for golomb rulers with 13 marks and length 106 in which we do not extend half the nodes at level 3 of the search tree or half the remaining nodes at level 4 enter

   13  106    1    2

Then enter

         3         2         1
         4         2         0

After a while dts2x will find a ruler (we chose the appropriate modulo classes).

      0     7     8    17    21    36    47    63    69    81
    101   104   106

and then a bit later complete the search

 n= 13 k= 106 solutions=       1 time=       5.25 nodes=     12669479. 106
            0.          38.         866.        6829.       35521.      204292.
       492119.     1916285.     5206931.     4234111.      571267.        1218.
            2.

Note the output is bit different from that of dts2. The last number in the first line (here 106) is the best (shortest) difference triangle set found. Dts2x also outputs (lines 2-4 above) the number of nodes visited on each level (1-13) of the search. The total number of nodes visited is about 1/4 that for dts2 and the search should finish in about 1/4 the time. The program can now be terminated by entering

At this point disk unit 1 should contain the following

        13       106         1
     0     7     8    17    21    36    47    63    69    81
   101   104   106
         0         0

and disk unit 2 should contain the following

   13  106    1    2
         3         2         1
         4         2         0
 n= 13 k= 106 solutions=       1 time=       5.25 nodes=     12669479. 106
            0.          38.         866.        6829.       35521.      204292.
       492119.     1916285.     5206931.     4234111.      571267.        1218.
            2.

consisting of a copy of the input data and the search summary. If dtsver is now run it will read unit 1 and verify that this is a difference triangle set. It will write to the terminal (unit 6).

        13       106         1
         0         0         0
          1 difference triangle sets verified