Given an N x N square grid what is the minimum number of overlapping squares you need to draw such that every line of the grid is covered by the side of a square.
The question can be rephrased as follows (which is how I arrived at the question):
A child wants to draw a NxN square grid in Paint by only drawing squares. Because he is lazy, he wants to draw as few squares as possible. Find the minimum number of squares he needs to draw.
N=1 : 1 You obviously only need one square.
N=2 : 3
One 1x1 square in the top left corner, one in the bottom right and a 2x2 square.
N=3 : 4
N=4 : 6?
N=5 : 8?
I hope you've understood what I mean by now. Is there any formula or algorithm for the general case? I thought about making a quick brute force algorithm but I realised how slow it would be and although it wouldn't be too complicated to write it's pretty tedious. It needs to do around $$\sum_{0 \le x \le n+1, 0 \le y \le n+1} 2^{min(n+1-x,n+1-y)}$$ operations. So before I try to write a brute force algorithm I thought I would ask this here in case anyone comes up with the solution or a more efficient algorithm.