Build a top-front-side puzzle solver
Python: 5360 test-cases solved using 69519 blocks, 594 bytes

This should be the optimal values. 

Approach:

First I'll test if the test-case is actual solvable. I do this by initializing a list of length 64 by ones and set all positions to zero, if there the corresponding pixel of the three views is zero. 
Then I simple view at the puzzle from all 3 directions, and look if the views are the same as the input views. If there're equal, the puzzle is solvable (we already found the worst solution), otherwise it's unsolvable. 

Then I do a branch-and-bound approach for finding the optimal solution. 

Branching: I have a recursive function. The recursion depth tells how many values are fixed already. In each call of the function I call itself twice, if the value at the current index is 1 (this value can be 0 or 1 in the optimal solution), or once, if the value is 0 (it has to be zero in the optimal solution). 

Bounding: I use two different strategies here. 


I calculate the views from the 3 sides in each function call and look If they still match the input values. If they don't match, I don't call the function recursively. 
I keep the best solution in memory. It there already more fixed ones in the current branch than in the best solution, I can already close that branch. Additionally I can estimate a lower bound for the number of activated blocks, which are not fixed. And the condition becomes #number of activated fixed blocks + #lower bound of activated blocks (under the not fixed blocks) &lt; #number of activated blocks in the best solution.


Here's the Python code. It defines a function f which expects 3 lists containing 1s and 0s and returns either 0 (not solvable) or a list of 1s and 0s representing the optimal solution.

S=sum;r=range
def f(t,f,s):
 for i in r(4):s[4*i:4*i+4]=s[4*i:4*i+4][::-1]
 c=[min(t[i%16],f[(i//16)*4+i%4],s[i//4])for i in r(64)]
 m=lambda:([int(S(c[i::16])&gt;0)for i in r(16)],[int(S(c[i+j:i+j+16:4])&gt;0)for i in r(0,64,16)for j in r(4)],[int(S(c[i+j:i+j+4])&gt;0)for i in r(0,64,16)for j in r(0,16,4)])==(t,f,s)
 Z=[65,0];p=[]
 def g(k):
  if k&gt;63and S(c)&lt;Z[0]:Z[:]=[S(c),c[:]]
  if k&gt;63or S(c[:k])+p[k]&gt;=Z[0]:return
  if c[k]:c[k]=0;m()and g(k+1);c[k]=1
  m()and g(k+1)
 for i in r(64):h,R=(i//16)*4+4,(i//4)%4;p+=[max(S(f[h:]),S(s[h:]))+max((R&lt;1)*S(f[h+i%4-3:h]),S(s[h+R-3:h]))]
 g(0);return Z[1]


The code length is 596 bytes/chars. And here's the test framework:

from hashlib import md5
from time import time

N = 1000000
start=time();count=blocks=0
for n in range(N):
 bits = list(map(int,"{:048b}".format(int(md5("{:06}".format(n).encode("utf-8")).hexdigest()[:12], 16))))
 result = f(bits[:16], bits[16:32], bits[32:])
 if result:
  count += 1
  blocks += sum(result)
  print("Seed: {:06}, blocks: {}, cube: {}".format(n, sum(result), result))
print()
print("{} out of {} puzzles are solvable using {} blocks.".format(count, N, blocks))
print("Total time: {:.2f} seconds".format(time()-start))


You can find an ungolfed version of the program here. It's also a little bit faster. 

Results:

5360 out of 1000000 puzzles are solvable. In total we need 69519 blocks. The number of blocks varies from 6 blocks to 18 blocks. The hardest puzzle took about 1 second to solve. It's the puzzle with the seed "347177", which looks like 

Top:      Front:    Side:
x x . .   x x x x   x . x .
x x x x   x x x x   x x x x
x x x x   x x x x   x x x x
x x . x   x x x x   x . x x


and has an optimal solution with 18 cubes. The following is a few from top for each of the layers: 

Top 1:    Top 2:    Top 3:    Top 4:
. . . .   . x . .   . x . .   x . . .
. . x x   . . x .   x . . .   . x x .
. . . .   . . . x   x x x .   . . . .
x x . .   x . . .   . . . x   . . . x


The total running time for all test-cases was about 90 seconds. I used PyPy to execute the my program. CPython (the default Python interpreter) is a bit slower, but also solves all puzzles in only 7 minutes.

You can find the complete output here: The output is self-explanatory. E.g. the output for the puzzle above is: 

Seed: 347177, blocks: 18, cube: [0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1]