8 24 block solution

For the main case ($3\times 3\times 3$), here is a solution using 13 blocks:

 1 1 0   0 0 1   0 0 1
0 1 0   1 1 1   0 1 0
0 1 1   1 0 0   1 0 0


Update. : For the $4\times 4\times 4$ case, here is a solution using 25 only 24 blocks. This configuration includes the $3\times 3\times 3$ configuration above in one corner. (This may be a bit easier , which is optimal according to see if you look at the rightmost view that Joseph $\frac{3}{2}n^2-\frac 12$ lower bound provided of the 13 block solution.)by Douglas and Gjergji.

  0 1 1 1
0 1 0 0
1 1 0 0
1 0 0 0

1 0 0 0
1 1 1 1
0 0 1 0
0 0 1 0

1 0 0 0
0 1 0 0
0 0 1 0 1
0 1 1 0

1 0 0 0
0 1 0 0
0 0 1 0 1
0 0 1 1


It appears that we may still hope for a 24 block solution, according to Douglas's $\frac{3}{2}n^2-\frac 12$ lower bound.

(Click on the edit history for my previous answersolutions, which provided a used first 27 blocks, then 26block solution, as well as the bound $C_3(n)\ \leq \ 2(n^2-n)+\lfloor\frac{n}{2}\rfloor+1$then 25, which is and now supplanted by other answers.24.)

7 25 block solution in 4x4x4 case

For the main case ($3\times 3\times 3$), here is a solution that seems to work with using 13 cubesblocks:

Update. For the $4\times 4\times 4$ case, here is a solution using 25 blocks. This configuration includes the $3\times 3\times 3$ configuration above in one can seem to get by with 27 26 cubes corner. (thanks This may be a bit easier to ARupinski for see if you look at the improvement):rightmost view that Joseph provided of the 13 block solution.)

1 0 1 0 0 1 0 1 0 0 1 0 0 1 0 0 1 1 0 1 0 0 1 0 0 0 1 0 0 1 0 1 0 0

The idea is to use the complement of the diagonal on the bottom layer, and then place piles on top of the main diagonal on the higher layers1

It appears that we may still hope for a 24 block solution, using some extra cubes in the second layer to keep it connected. This idea generalizes according to the $n\times n\times n$ case by using $n^2-n$ cubes on the bottom layer, and then $n$ more cubes on each higher layer, arranged in piles above the main diagonal, plus an additional Douglas's $\lfloor\frac{n}{2}\rfloor+1$ on the second layer to to connect these piles to the bottom layer\frac{3}{2}n^2-\frac 12$lower bound.For example, in this second layer one could place every other cube (Click on the lower diagonaledit history for my previous answer, which would connect all the piles to the lower triangle of the bottom layer, plus one more provided a 26 block on the upper diagonal of the second layersolution, which would connect the the upper triangle as well (I suppose there are a variety of ways to achieve this). This arrangement gives as the bound $$C_3(n)\ C_3(n)\ \leq \ n^2-n+(n-1)n+\lfloor\frac{n}{2}\rfloor+1\ =\ 2(n^2-n)+\lfloor\frac{n}{2}\rfloor+1.$$ It seems that one may also reduce this 2(n^2-n)+\lfloor\frac{n}{2}\rfloor+1$, which is now supplanted by one as in ARupinski's suggestion.other answers.)

6 Implemented ARupinski's improvement; added 41 characters in body

For the main case ($3\times 3\times 3$), here is a solution that seems to work with 13 cubes:

 1 1 0   0 0 1   0 0 1
0 1 0   1 1 1   0 1 0
0 1 1   1 0 0   1 0 0


For the $4\times 4\times 4$ case, one can seem to get by with 27 26 cubes (which is slightly better than thanks to ARupinski for the bound provided in ARupinski's answer)improvement):

 0 1 1 1   1 0 0 0    1 0 0 0    1 0 0 0
1 0 0 1 1   1 1 1 0    0 1 0 0    0 1 0 0
1 1 0 1   0 0 1 0    0 0 1 0    0 0 1 0
1 1 1 0   0 0 1 1    0 0 0 1    0 0 0 1


The idea is to use the complement of the diagonal on the bottom layer, and then place piles on top of the main diagonal on the higher layers, using some extra cubes in the second layer to keep it connected. This idea generalizes to the $n\times n\times n$ case by using $n^2-n$ cubes on the bottom layer, and then $n$ more cubes on each higher layer, arranged in piles above the main diagonal, plus an additional $\lfloor\frac{n}{2}\rfloor+1$ on the second layer to to connect these piles to the bottom layer. For example, in this second layer one could place every other cube on the lower diagonal, which would connect all the piles to the lower triangle of the bottom layer, plus one more block on the upper diagonal of the second layer, which would connect the the upper triangle as well (I suppose there are a variety of ways to achieve this). This arrangement gives $$C_3(n)\ \leq \ n^2-n+(n-1)n+\lfloor\frac{n}{2}\rfloor+1\ =\ 2(n^2-n)+\lfloor\frac{n}{2}\rfloor+1.$$ It seems that one may also reduce this by one as in ARupinski's suggestion.

5 added 201 characters in body
4 Generalizations to higher n; added 14 characters in body; added 73 characters in body; added 1 characters in body
Post Undeleted by Joel David Hamkins
3 A new solution; added 56 characters in body
2 added 102 characters in body
Post Deleted by Joel David Hamkins
1