Programming Project

The problem (which is said to have many practical applications including sensor placements for x-ray crystallography and radio astronomy) is to find a set of n integers 0 = a_1 < a_2 < ... < a_n such that the n(n-1)/2 differences a_j - a_i, 1 <= i < j <= n are distinct.

The project is to program:

• first in pure Prolog (for instance GNU Prolog without any fd_ predicate) a program providing such a set for any given n, and able to check a provided answer;
• then, using Finite Domains constraints, to find optimal sets (i.e. with minimal a_n) for a given n.

The result of the project should be a prolog file (if possible GNU-Prolog-compatible) with commented code for the two parts and a short text file providing indications on the use of the program and its results.

Finding solutions should be very fast for problems up to n = 50. Finding optimal solutions should give an answer in a reasonable time for n smaller than 10.

The time necessary to carry out this work should be from 30 min if you're a seasoned GNU Prolog programmer to 10 hours maximum if you need to get used to Prolog, CLP, etc.

The two files have to reach Sylvain.Soliman@inria.fr before October 10th, 11:00:00 AM CET (late submissions will be dismissed, and since e-mail is not reliable, it seems better to send your project before the 10th and to wait for a confirmation).

Any question about the project should be sent to Sylvain.Soliman@inria.fr