Proposed by Serdar Kadıoğlu, Özgür Akgün
A costas array is a pattern of n marks on an n∗n grid, one mark per row and one per column, in which the n∗(n−1)/2 vectors between the marks are all-different.
Such patterns are important as they provide a template for generating radar and sonar signals with ideal ambiguity functions.
A model for Costas Array Problem (CAP) is to define an array of variables X1,…,Xn which form a permutation. For each length l∈{1,…,n−1}, we add n−l more variables Xl1 1,…,Xln−1, whereby each of these variables is assigned the difference of Xi−Xi+l for i∈{1,…,n−l}. These additional variables form a difference triangle as shown in the figure below.
Each line of this difference triangle must not contain any value twice. That is, the CAP is simply a collection of all-different constraints on X1,…,Xn and Xl1…,Xln−l for all l∈{1,…,n−1}.
Costas arrays can be constructed using the generation methods based on the theory of finite fields for infinitely many n. However, there is no construction method for all n and it is, e.g., unknown whether there exists a Costas Array of order 32.
The problem description was taken from [kadioglu2009dialectic] with small adaptations.
Here is a website which contains some more information on the problem: http://datagenetics.com/blog/february22013
Helmut Simonis has slides on Costas Arrays here: http://4c.ucc.ie/~hsimonis/ELearning/costas/slides.pdf