Consider a skyscraper problem on a 9x9 board. When a number is visible on the edge there will be some number of possible arrangements of buildings that could achieve this.

Find the number of possible arrangements of building if the edge number is each of {1,2,3,4,5,6,7,8,9}

For example on a 3x3 board there are three possibilities if a 2 is visible on the end (viewing from the left): (1,3,2), (2,3,1), (2,1,3)

(1,3,2), (2,3,1), (2,1,3)
What you would see:

To approach these "skyscraper" problems, to measure the complexity, I counted the number of variants for each PAIR of counts (left-right or top-bottom) for a 9x9 grid, i.e. for (1,1) to (9,9). Of these 81, 37 had no hits, and 44 had one or more.  There were 362,880 possible arrangements.  Adding the rows (or columns) gives:

040320

109584

118124

067284

022449

004536

000546

000036

000001

Posted by ed bottemiller on 2009-03-16 12:45:57