Urban Planning


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.

  1. If the town is to be laid out as a square, how many blocks on each side must the town have as a minimum?

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

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

Solution to Urban Planning

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

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

Open table as spreadsheet


Figure 2-1: I is an industrial block, O is an office block, W is a warehouse block, S a shopping block, H a housing block, P a park, and X vacant. The industrial zone must be far from the housing.

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

Open table as spreadsheet


Figure 2-2: Because the industry is clean, the industrial zone can be folded among the other uses, yielding a 4 by 4 square.




Puzzles for Programmers and Pros
Puzzles for Programmers and Pros
ISBN: 0470121688
EAN: 2147483647
Year: 2007
Pages: 81
Authors: Dennis Shasha

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net