# Perfect Zoning

Most people would prefer not to live next to a freight train station, but would like to be able to walk to their daily grocery markets (exceptions might include some Los Angelinos). The grocers in turn might not mind being next to warehouses, and warehouse managers might like the convenience of a nearby rail link. This puzzle embarks on a study of the mathematics of such neighborly desires and dislikes.

For simplicity, we will organize our imaginary city into a grid. Each grid block contains a number signifying its type (residential, transport, and so on). A block gains a ¿happiness point¿ for every neighboring block whose identifying number is higher or lower by exactly 1. Neighbors differing by 0 or 2 don't change a block¿s happiness score. Neighbors differing by 3 or more are bad because they make a block lose a happiness point. If all the neighbors of a cell contribute to its happiness, then the cell is "perfectly zoned."

Neighbors here are defined as blocks that are vertically or horizontally adjacent (we can ignore the diagonals). So, if a grid block 6 is next to a 5 or 7 on all four sides, then it gains 4 happiness points.

In the below figure, the surrounded 6 is neutral with respect to the 6 above it and the 8 below it, happier because of the 7 to its left (+1) and unhappier because of the 3 to its right (-1). Its net happiness is therefore 1 - 1 = 0.

Warm-up: Consider a 3-by-3 square and the numbers 1 through 9. What is the design that gives the greatest net happiness?

Solution to warm-up: The following gives a net happiness of eight points over all block positions.

5 6 7
4 3 8
1 2 9

Problems:

1. Suppose you have 36 numbers, in the same distribution as dice sums: one 2, two 3s, three 4s, four 5s, five 6s, six 7s, five 8s, four 9s, three 10s, two 11s, and one 12. Can you lay them out in a 6-by-6 square so that every neighbor of every grid cell increases the happiness of that block? That is, can you make every block perfectly zoned? If not, how close can you get?

2. If you have all 36 numbers from 1 to 36 in a 6-by-6 grid, is there a solution which leaves no grid block with a net negative happiness score?

3. For the 36 numbers from 1 to 36 in the 6-by-6 grid, is there a solution in which every neighbor of every grid block either adds to the block¿s happiness or is neutral? (This is a far harder test to meet than the one set by the previous question.)

4. For the 36 numbers from 1 to 36 in the 6-by-6 grid, the best solution I know of has a net total happiness over all grid blocks of 20. Can you do better?

Maybe you can come up with a nice layout algorithm for general shapes, population types, and likes and dislikes among those types. If so, there are some cities and suburbs that surely could use your help.

You must sign in or register as a ScientificAmerican.com member to submit a comment.