Zoning

Dennis Shasha

Omniheurist Course

Computer Science


 

Description

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.


 5 6 7
 4 3 8
 1 2 9

In the solitaire version of the game, you are give n*n numbers (which may have duplicates) and a grid of size n by n and you try to generate the maximum happiness. In the competitive version, there are two player colors Red and Blue. In a move, each player puts down a number of those that are left somewhere on the grid. The number turns the color of the player. When the grid is filled, each player gets the net happiness of all numbers of that player's color.

Example: in the above grid, if the red player had put down 3, 8, 9, and 1 and the blue player all the rest, then Red would receive a net happiness of zero from the 3, one from the 8, zero from the 9, and zero from the 1. That would be a net happiness of 1. The Blue player would receive two from the 5, one from the 6, two from the 7, one from the 4, and one from the 2. Thus the Blue player would receive a net happiness of 7.

Other ideas

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? 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:

 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.


       (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.

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.

 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

Your Task

I will give you a multiset of numbers. You will put this into a square that maximizes happiness.

Architecture Team

Your job is to verify that the proposed zoning uses all the numbers and to render each player's output in a nice way (e.g. where numbers become icons).