# 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


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)$$.