Solve the knapsack problem.

…

…

But really, you are given a set of tiles (which all happen to be some subset of a 3x3) and a set of constraints–a MxN grid and how many of each tile to place. Count how many constraints are possible.

Tiles may be rotated and/or flipped.

Given a grid of solid @ and empty cells ., count how many solid cells have less than 4 neighbors.