Perfect Zoning

Most people would prefer not to live next to a train station,
but would like to be able to walk to their daily markets
(exceptions might include some Los Angelinos).
The markets in turn might not mind being next to warehouses
and those 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 city into grids.
Each grid block contains a number indicating the type
of block it is (residential, transport, and so on).
The block
gains a happiness point
for every neighboring grid whose number is 1 different
and loses
a happiness point for each neighboring number that is more than 2 different.
Neighbors that are 0 or 2 different don't change happiness.
To summarize, a difference
of 0 changes nothing, 1 is good, 2 changes nothing, and 3 or more are bad.
If all neighbors of a cell contributed happiness, then the cell
is "perfectly zoned."

Neighbors here are those that are vertically or horizontally adjacent.
So, if a grid block
6 is vertically next to a 5 or 7 on all four sides, then it
gains 4 happiness points.
In the figure 
http://cs.nyu.edu/cs/faculty/shasha/papers/zone1.doc,
the surrounded 6 is neutral regarding the 6 above it and
the 8 below it, happy regarding the 7 to the left and unhappy regarding
the 3 to the right.
So, its net happiness is 1 - 1 = 0.

Warm-up: Consider a 3 x 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
over all cell positions.

[SCIAM: please keep formatting]

 5 6 7
 4 3 8
 1 2 9

1. If you have 36 numbers distributed like 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 every neighbor
of every grid cell increases the happiness of that cell? 
That is, can you make every cell 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 cell with a 
net negative happiness score
in a 6 by 6 square?

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 cell
either adds to happiness or is neutral?
This is a far harder test to meet than the one given
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 total happiness over
all grid cells 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.

Solutions: 

1. The beautiful symmetrical design shown in figure 
http://cs.nyu.edu/cs/faculty/shasha/papers/zone2.doc 
gives 
the maximum possible happiness.
This is a perfect zoning for all cell.

2. Each cell has at most four neighbors.
Simply lay out the numbers in order, perhaps alternating
left to right with right to left.
That is, start as follows:

[SCIAM: please keep formatting]
 1  2   3   4   5   6
 12 11  10  9   8   7
 13 14  15  16  17  18
 24 23  22  21  20  19
 25 26  27  28  29  30
 36 35  34  33  32  31

Because each cell has at least two good cells and at most
two bad ones, its net happiness must be non-negative.

3. Consider a number in the middle.
Say it is X.
For it to have neighbors
that all make it happy, it must be surrounded by all four
of its numerical neighbors X-1, X-2, X+1, and X+2 as shown below.

[Sciam: please keep formatting]

       (X-2)
  (X-1) X (X+1) 
	(X+2)

But  now consider the situation of say X-1.
It should also be surrounded by its four numerical neighbors:
X-2, X-3, X, and X+1, but two of those (namely X+1 and X-1) are already
taken. 


4. 
Here is a design on all 36 numbers
that gives a net happiness of 20. I don't
know whether this is the best possible.
[SCIAM: please keep formatting]
 1 2   23 24 25 26
 3 4   21 22 27 28
 5 6   19 20 29 30
 7 8   17 18 31 32
 9 10  15 16 33 34
 11 12 13 14 35 36