Distribute numbers 1,N on a grid as evenly as possible
Simulated Annealing might work well for this problem.

The idea is to introduce a "temperature" component to your heuristic function to avoid getting stuck at local optima. Temperature corresponds to how willing the heuristic function is to accept an inferior arrangement. With simulated annealing, temperature starts off high and decreases until an optimal solution is found. 

Here is solution to the Travelling Salesman Problem using simulated annealing

You can tinker with the starting temperature and its rate of change to try and find an optimal arrangement.