Puzzles for Programmers and Pros

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