I then wrote several scripts that randomly tried to find a solution. I ran 3 of them in parallel, one of them finished in 74 minutes. Here's the program:

I used gnuplot to visualise the solutions. You can see a short video showing the solutions covering more than 14 dots here. The final solution is shown in the end. Note that the algorithm is really stupid, the fifth picture can be extended into the solution easily.

To generate the pictures, I used the following shell script:

#!/bin/bash
i=0
while read l ; do
    l=${l#*: }
    perl -pe 's/[^-\d.]+/(" ", "\n")[++$i % 2]/ge' <<< "$l" > 2
    gnuplot -e "out='$(printf %04d $i)'" 4x4-16.gpl
    echo "$l"
    ((++i))
done < <(sort -u 1)
[download]

and the following gnuplot script:

set xrange [-2:6]
set yrange [-2:6]
unset border
unset xtics
unset ytics
set term png
set output "4x4-16-" . out . ".png"
plot '2' using 1:2 with lines notitle, "4x4-16.grid" using 1:2:(0.1) w
+ith circles notitle
[download]

Where the "grid" file just contains all the coordinates of the points to connect.

Extra points for gnu plot and video!!! :)

But it's not solved yet: the challenge had three levels and you solved the easiest one.

And that to a very high cost. (75 min? Wow)

You seem to think that the vertices of the chain have to be at integer positions. (?)

That's not the case and crippling your solutions.

For the records:

Level 2: there is at least one solution with a real i.e. closed polygon! Or maybe more than one?

Level 3: what if the grid is bigger 5x5, 6x6 or even 6x5?

There doesn't seem to be much interest though and it might be a bit too challenging on the math level.

Cheers Rolf
_{(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery FootballPerl is like chess, only without the dice}

I can't follow. ..

Can you prove there is only one perfect solution?

Otherwise you need code to check them all.

If you know of better coding challenges feel free to post them. :)

Cheers Rolf
_{(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery FootballPerl is like chess, only without the dice}

Well looks similar to Traveling Salesman, don't you think?

Coding challenges usually come with a test suite and an API.

If you say "bigger grids", are they still equidistant and quadratic? I suppose n x m is still legit?

I forgot: Any language restrictions? Is Perl 6 ok?

A solution in JavaScript could also draw the polygon.

And if you want *all* solutions you might exclude symmetries by rotation or mirroring.

Good questions!!!

> Any deadline?

I'll share the level 2 solution end of June.

> Do you want one or all solutions?

At least one, the more the better.

> Anything besides "closed" polygons seems trivial.

Indeed.

> Coding challenges usually come with a test suite and an API.

Yes but I posted this w/o preparation to help bliako with his request.

See it rather as a mediation on a possible challenge.

But I'm starting to believe that it's too challenging on the mathematical side (though it's part of the curriculum of my 15 year old niece :-/ )

> If you say "bigger grids", are they still equidistant and quadratic? I suppose n x m is still legit?

Equidistant: yes

Quadratic: no

Disclaimer: But I'm not aware of higher level solutions yet.

> And if you want all solutions you might exclude symmetries by rotation or mirroring.

I think it should be obvious that you need to handle symmetries when trying to find all solutions.

The complexity of a branch and bound algorithm might explode otherwise.

> I forgot: Any language restrictions? Is Perl 6 ok?

Any Perl*

> A solution in JavaScript could also draw the polygon.

You are free to generate JS or SVG, but the algorithm has to be Perl.

BTW Haukex's WebPerl would do too.

Cheers Rolf
_{(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery FootballPerl is like chess, only without the dice}