Constraint problems arise in many settings. Urban planning presents a particularly attractive challenge because it mixes geometry with logic. Your job in this puzzle is to lay out a town into city blocks under certain constraints.
In what follows, distance is measured in Manhattan distance: The distance between blocks A and B is the number of east-west streets plus the number of north-south streets between their nearest corners. Thus, if block B lies immediately due east of block A, the distance between them is 1. If B lies southwest of A and traveling from the northeast corner of block B to the southwest corner of block A requires crossing five east-west streets and two north-south streets, then the distance between the two blocks is seven.
Here are the constraints. The industrial zone (I) and every housing complex (H) should be at least eight blocks apart. Each office building (O) and each housing complex (H) should be between two and six blocks apart, inclusive. Every housing complex (H) should be within two blocks of some shopping center (S). Every shopping center (S) should be within one block of a warehouse (W). Each warehouse (W) should be within six blocks of the industrial zone (I). Each housing complex (H) should be within one block of a park (P). Unused lots can be laid out as vacant (X).
Each block contains only one activity. There are five blocks of housing complexes, two of shopping centers, one industrial, two warehouses, and three office buildings. You will decide on the number of parks you need.
If the town is to be laid out as a square, how many blocks on each side must the town have as a minimum?
Given the size determined from your answer to the first question, find a layout that leaves the largest possible (in area) rectangle of vacant blocks (X) or parkland (P). Your customers are thinking of building a stadium there. Show the layout.
If one constraint were eliminated, how many blocks on each side would this town need to be at a minimum, disregarding the stadium? Say which constraint should be eliminated and show the layout.
If the town is to be laid out as a square, how many blocks on each side must the town have as a minimum?
It has to be at least six by six, because of the minimum distance constraint between industrials and housing. Under that constraint, even five by five would be unacceptable for more than one housing unit. The constraint also implies that the industrial zone must be in one corner.
Given the size determined from your answer to the first question, find a layout that leaves the largest possible (in area) rectangle of vacant blocks (X) or parkland (P). Your customers are thinking of building a stadium there. Show the layout.
Figure 2-1 shows a possible layout. The stadium could be 3 by 5, hence could have an area of 15.
I | X | X | X | X | X |
X | X | X | O | O | O |
X | X | X | X | W | S |
X | X | X | W | P | H |
X | X | X | S | H | H |
X | X | P | H | H | P |
If one constraint were eliminated, how many blocks on each side would this town need to be at a minimum, disregarding the stadium? Say which constraint should be eliminated and show the layout.
If you eliminate the constraint separating industrial zones from housing, say by finding non-polluting industrials, then the town could fit into the lower right 4 by 4 square, shown in Figure 2-2. There could be a large belt of vacant land.
X | X | X | X | X | X |
X | X | X | X | X | X |
X | X | I | O | W | S |
X | X | O | W | P | H |
X | X | O | S | H | H |
X | X | P | H | H | P |