Frame paving

TIP: I find this problem hard to think as a square frame. Much easier to make line from it. This way there will be 8 points where I need to break line to make square - 2 points for every corner. Decrement every point to make another 8 for the case when first cell is not filled up.

This approach creates linear and simple solution.