You are a city planner tasked with the placement of unit-square-sized houses in a rectangular-grid allotment, the size of which is up to you but must be as small as possible to save money. The number of houses is of no concern, however.
The problem is, the prospective homeowners are very picky about the number and arrangement of neighbouring houses. It is up to you to satisfy at least one of each kind of homeowner:
- Some want no houses to the north, south, east, or west of their house
- Some want only one house to their north, some only one to the south, some only one to the east, some only one to the west
- Some want exactly two houses, to their north and east, north and south, north and west, south and east ... etc.
- Some want exactly three houses, to their north and east and south, to their ... etc.
- Some want to be surrounded by four houses, to their north south east and west
So in total, there are 16 unique kinds of homeowners (1 + 4 + 6 + 4 + 1).
As an example, consider this grid:
+---+ | o | o = house |ooo| grid: 3x3 | o | +---+
The above grid satisfies exactly 5 kinds of homeowners: all four of the kind that only want one neighbour, plus the one that wants four neighbours. The size of the grid is 3x3 = 9.
How can you arrange the houses, to satisfy at least one of all 16 kinds of homeowners, while minimising the size of the grid?