One ping in every time step, one in every channel. Two pings are separated by a jump: so many steps across, so many channels up. Place them so no jump is ever repeated. The echo board shows every jump you have made, and turns red the moment one is used twice.
An arrangement with no repeated jump is a Costas array. Solomon Golomb's own definition, in the Encyclopedia of Mathematics, is the one you have been playing to: an n × n permutation matrix in which the n(n−1)/2 line segments connecting pairs of ones in the matrix are distinct as vectors, i.e., no two agree in both magnitude and slope.
Draw a line between any two pings on your board. No other pair is joined by a line of the same length at the same slope. Not one, among all 36 of them.
John P. Costas arrived at these patterns in 1965, looking for a frequency-hopping sonar pattern, by way of a problem that sounds like it has nothing to do with combinatorics. Ideally a sonar would match the returning echo against the transmitted pulse using the whole waveform, phase included, and read off the target's range from the time shift and its speed from the frequency shift. Konstantinos Drakakis's survey states why that fails, writing W for the transmitted waveform and R for the return: all real media are incoherent: phase delay varies with frequency, hence waveforms tend to spread while traveling in the medium, so that, by the time R reaches the receiver, it may look so different from W that coherent processing becomes inappropriate.
Costas's answer was to throw the unreliable part away and correlate on energy alone, which frequency was on and when. What is left of the pulse is a pattern of dots. Exactly your board.
And a pattern of dots has a specific weakness. Slide a copy of it over itself; wherever dots land on dots, that is a reading the receiver might believe. One coincidence is unavoidable, because any single pair of dots can always be made to sit on itself. Two coincidences at the same shift is a second answer for a target that has only one. It happens exactly when two different pairs are separated by the same jump. Golomb: For any non-zero shift parallel to the coordinate axes a Costas array has at most one "hit" (coincidence of a 1 with a 1), and thus gives the least ambiguous reading of the correct range and Doppler in the presence of noise.
That is the red cell you were avoiding.
So the echo board is not decoration. It is that sliding, drawn out: the array's discrete auto-ambiguity function, counting at each (time shift, channel shift) the ping pairs separated by exactly that jump. Drakakis puts the whole rule in one line, and it is the line the game is scored on: a board is Costas exactly when its auto-correlation range consists of exactly three values, namely {n, 1, 0}
. The bright centre is the n. Everything else must be a one or a zero. A two is a ghost.
One qualification, and it is Costas's own. The title of his 1984 paper says these waveforms have nearly ideal
range-Doppler ambiguity properties, not ideal. The "at most one" is exact for this board, the discrete overlay under whole-step shifts. The ambiguity surface of the real radio-frequency waveform only closely approximates the thumb-tack, and the combinatorics is what makes the approximation good. A page that dropped the word "nearly" would be quoting a stronger claim than the man made.
Every daily board is built from a named seed, then carved down only as far as it can go while staying solvable by two rules and nothing else: a time step with one legal channel must take it, and a channel legal in one time step must go there. No guessing, no trial and error, and exactly one completion. Not hoped for. Checked, before it ever reached you.
Counting instead of quoting is not ceremony, and here is what it caught. The standard survey of the field, Drakakis's Open problems in Costas arrays, prints the order-14 count in its Table 1 as 12,752, and the same figure appears in his lecture slides. The true value is 17,252: OEIS has it, Golomb's encyclopedia table has it, and this page's verifier counts it out one array at a time and arrives at 17,252 in about a minute. It is a transposed digit in an otherwise careful table, in the paper the field cites for its open problems, sitting there since 2011. Had we copied a number instead of computing one, we would have copied that.
The right-hand column is the reason no one finds these by guessing, and in 2023 the pattern in it became a theorem. Warnke, Correll and Swanson: There is a constant c > 0 so that the density C(n)/n! of n × n Costas arrays among n × n permutation matrices satisfies C(n)/n! ≤ e−cn for all n ≥ 3.
Before that, the best bound anyone had was of order 1/n.
The count also does not fade away smoothly, which is worth a second look. It peaks at order 16, falls hard to 56 at order 26, and then climbs again: 204 at 27, 712 at 28. The same paper notes what that costs the intuition: the values of C(17) and C(27) reveal that C(n) is neither monotone increasing nor unimodal.
The bump is the algebra arriving. The constructions below build arrays only at orders tied to a prime, p−1 for Welch and q−2 for Golomb, and 29 is prime, so it supplies order 28 and order 27 while nothing supplies 26. This page's own run of the two base constructions measures exactly that: nothing at all at order 26, 144 of the 204 at 27, 96 of the 712 at 28, and 64 of the 164 at 29.
Those are the base constructions only, each of which has trimmed variants, so the real algebraic share is higher. How much higher is the striking part, and it was expensive to learn. The enumeration of order 28 found that every one of its 712 arrays is accounted for by the Welch and Golomb methods, making 28 the first order above 5 with no unexplained array at all; it took the equivalent of 70 years of single-CPU time, and order 29 took 366.55. In the middle of the range it is the other way round. Drakakis: only 16 out of the 10240 Costas arrays of order 19 are algebraically constructed
. The arrays anyone can build run out slowly. The arrays nobody can explain run out fast: Sporadic Costas arrays of order n exist for 6 ≤ n ≤ 27
, and the single sporadic array of order 27 is currently the largest sporadic Costas array known
.
No order has ever been proved to have none, and Golomb and Taylor conjectured in 1984 that every order has one. Some orders have simply never yielded one. Golomb's encyclopedia entry, last edited 26 March 2023: No case of C(n) = 0 is yet known, but no examples of Costas arrays of orders 32, 33, or 43 have yet been found.
Drakakis's 2011 survey names the two smallest: The smallest values of n for which no Costas array of order n is currently known are n = 32 and 33
. Jedwab and Wodlinger date the gap and price the brute-force answer: The smallest order for which the existence of a Costas array is open is 32, and this has been the case since 1984. However, settling the existence question for this order through exhaustive search remains well out of computational reach, with an estimated search time of 45,000 processor years in 2011.
It was still open in 2023, when Warnke, Correll and Swanson wrote that it remains unknown if Costas arrays exist for order n = 32
. Double the largest board this page will hand you, and nobody knows whether the puzzle has an answer.
Most Costas arrays of any size are not found by searching. Two recipes build them out of finite fields, and Golomb states them like this. Welch: The Welch construction, for every prime p > 2, gives a Costas array of order p−1 by setting aij = 1 when j = gi (mod p), where g is a primitive root modulo p.
Golomb: In Golomb's construction, if α and β are any two primitive elements in GF(q), for q > 2, a Costas array of order q−2 is obtained by setting aij = 1 whenever αi + βj = 1.
Nothing here takes either on trust. In Free mode, finish a board and the page will check yours against both.