Partially tiling a square with parallelograms

I found the following puzzle on reddit, and am struggling to find the solution:

You have an $n\times n$ square, and a supply of parallelogram tiles with side lengths $1$ and $\sqrt{2}$ and angle $45$°. What is the largest number of non-overlapping tiles you can place in the square? Assume that the tiles must be placed so their vertices have integer coordinates.

It seems like the answer is $n(n-1)$, using $n$ rows of $(n-1)$ tiles.

I am stuck proving this is optimal. I think the following idea might be helpful. Divide the square into an $n\times n$ array of square cells, and partition these cells into groups so that whenever a tile touches two cells, those two cells are in the same group. The groups will be snaking paths resembling the example below. At the end of each path are two uncovered triangles. Therefore, we need only show the $n\times n$ grid cannot be partitioned into fewer than $n$ such paths.

X X X X
      X X
        X
        X X
          X X

Solution 1:

Assume the top left corner is filled without any gaps. The only way to do this is shown below. In fact, the solution you've given is equivalent to filling the top right corner - this can be shown with a reflection. I've constructed each parallelogram from 2 right triangles.

We could then tile each parallelogram on the outer "shell" without leaving any gaps, as in the following figure. Then either the tiling continues until it reaches a corner, as in the bottom left, and we have 1 missing triangle. Or at some point the tiling reverses and another corner (the top right) is filled out, in which case, we would have 2 missing triangles in the top row but get one back in the next row. NB: we could have the tiling reverse and not fill out the top right corner but this would lose us 3 triangles of area. The crux of this is that tiling a shell loses us at least 2 triangles (1 unit) of space. Alternatively, if the top left corner of a shell weren't filled, it would lose us at least 1.5 units of space.

So if the same is true for each subsequent shell, we'd have $(n-1)+1$ units of lost space, counting over $n-1$ shells and an extra unit in the bottom right. Then our total filled area is at most $n(n-1)$.