Solved the problem with pure brute-force in 0.031 sec. BTW, my program works for much larger n's than in the problem statement.
I'm wondering whether there is more rigorous solution?

There rigorous algo exists. It has O(N^2) complexity and about 10 lines of code.

My solution is not much longer - about 20 lines of code. But complexity is O(2^(N/2)*(1/2*N^2)!). But works fast for almost any N =)

It means that you are very cool:D
For Petrozavodsk this problem was planned as solvable by brute force and some precalculation. Just for fun.

Thanks, but, probably, you could give some clue for algorithmic solution of the problem?

Try to arrange soldiers in vertices of regular n-polygon and mind geometrically.