How to optimise grid allocation according to some constraints

Problem:

Given a grid and elements with height 1 and width 2, 3 or 4, determine if a new element with given width (w) and position ((x1,y), (x2,y)) can be allocated so that the gri开发者_开发知识库d has (and will have) as less empty cells as possible between existing and future elements.

Constaints:

• You can't move the elements, you can only determine if an element with given position and width can be allocated
• An element with width j has k probability to be allocated in the future, width 2 (high), width 3 (medium), width 4 (low)
• You can't have more than 3 elements with the same x1 or x2
• Minimise the number of empty cells between elements along the x axis

Example of grid:

The tricky part is that I don't know what elements will be allocated, I can only predict how the grid will be filled based on the probability logic defined above.

I'm looking for an algorithm to solve this problem, any tips appreciated.

Thanks a lot!

Suppose Grid is a 2-dim-array, initialised with Empty-Values. A Solution in Python could be:

def fitsInGrid(x1,y,w): 
  return all([Grid[x1+x,y] is Empty for x in range(w)])