What is the optimal substructure for this greedy-algorithm solvable problem (Domino Piling)?
I think there's a slight misunderstanding in the question. The phrase is "optimal substructure", not "optimal substructures". It's not a matter of looking at the individual substructures (e.g., regions of the grid you're trying to tile) and saying, "This one's optimal", "This one's optimal", "This one isn't". Rather, it's a matter of looking at the structure and interactions of the subproblems and saying, "The substructures of this problem (i.e., the subproblems) interact in a way that lets me find an optimal solution easily."

I also don't think this is a great example for greedy algorithms, since greedy algorithms are naturally somewhat recursive and it's so easy to domino-tile a grid iteratively that it feels artificial to force it into a recursive solution. But here goes...

One example of optimal substructure is that, if you can divide your grid into rectangles $A$ and&nbsp;$B$ and you can perfectly tile&nbsp;$A$, then an optimal tiling of the whole grid can be made from the perfect tiling of&nbsp;$A$ along with an optimal tiling of&nbsp;$B$.  This gives the following greedy algorithm.

function tile (int width, int height, int startrow)
if (startrow &lt;= height-1)
    perfectly tile rows startrow and startrow+1 like this | | ... |
    tile (width, height, startrow+2)
else if (startrow == height) then
    tile the last row like this -- -- ... -- , with one empty square
    at the end if width is odd
/* else startrow &gt; height and there's nothing to do */


Note that this just produces tilings like this one for a $7\times3$ grid,

| | | | | | |
| | | | | | |
--- --- ---


which is exactly what you'd do iteratively.