# Distribute numbers 1,N on a grid as evenly as possible

I'm working on a complex engineering problem that I've essentially reduced to this problem:

I have a set of natural numbers $1,N$ and a grid (square or hexagonal) of exactly $N$ cells. I have to map each number to each cell so that the distribution (in a geometric sense) is as flat as possible. I'm still working on the definition of flat, but so far

1. The average of the numbers of a cell and its nearest neighbours must be as close to $N/2$ as possible, for every cell.

2. The average of the distance between a cell and each neighbour must be as large as possible.

If a cell has a number $n$ and its neighbour $m$ the distance between these neighbours is $min(|n-m|,N-|n-m|)$. It's essentially cyclical.

If $.$ represents a small number and # a large number I'm looking chessboard-like configurations like

.#.#.#.#
#.#.#.#.
.#.#.#.#


I need to find the best configuration (or a very good one) without using brute force.

Can you point me to some good algorithms that may be useful for this problem? I could only get above-average results on my own.

In my problem $N\approx~500$ and there is no runtime constraint.

• Random assignment probably gives a pretty good solution. – Yuval Filmus Jan 8 '16 at 17:51
• I've tried a random assignment but it's not good enough. After a solution is found I have to evaluate an engineering constraint that is pretty expensive to calculate. It's also not an option to feedback this evaluation to the distribution algorithm. So it's basically a (smart) trial and error. Not so lucky so far... – Fequi Jan 8 '16 at 18:19
• BTW, I've been doing an initial assignment (not random) and several types of sorting. – Fequi Jan 8 '16 at 18:21
• Do you already know how to solve the problem in the 1-dimensional case? (I understand that this is not the case that you would like to solve, but solving it for 1D first might help to understand better what kind of strategies might work for 2D.) – Jukka Suomela Jan 8 '16 at 19:17
• Your first step is you need to find a single objective function you are maximizing. You can't simultaneously optimize multiple metrics. So, you have two numbers that are both important. How do you want to combine them into a single number? The sum? Set a hard constraint on one and ask to optimize the other? Something else? Without that, "best" is not well-defined. – D.W. Jan 8 '16 at 19:46