A legal placement of pebbles is one in which no two pebbles are placed on horizontally or vertically adjacent squares. (Diagonal adjacencies are OK.) The value of the placement is the sum of the integers corresponding to the squares that are covered by pebbles of that placement. Give the most efficient algorithm you can for computing a placement of maximum value.
Hint: You may use the fact that the number of legal patterns of pebbles that can occur in any one column is eight. You may also talk about two columns being consistent if they do not have pebbles in the same row.