# How many $9\times 9$ squares can I cut from this figure (it's $38\times 40$ without some corners)

Can I cut 16 ones (along the grid)?
I've tried to paint some $15$ cells so that every $9\times 9$ square contain only $1$ painted cell (so I prove there can't be $16$), but to no avail.

The figure (bold):

EDIT: I can now prove "the reduced version", thanks to Dacian Bonta, that we can't "fit 4 9 x 9 squares in a 22 x 20 grid, given missing corner grid cells":

There are $7$ painted cells and every possible $9\times 9$ square covers at least $2$ of them. If $4\ 9\times 9$ squares would be possible, each covering at least $2$ painted cells, the total number of painted cells must be $\ge 8$, but we have $7$.

But I can't get to "expanded" version from this.

• 15 I see possible. 16 should be 4x4 arrangement. At a minimum 36x36. I don't see 16. – Dacian Bonta Dec 15 '15 at 2:22
• This grid is small enough to brute-force if someone is willing to put in the time to write a program to... – qwr Dec 15 '15 at 4:22
• @qwr Is it? Simple brute-force would take at least $896$ positions for the first square, $896-81$ for the second one and then resulting $\ge 2.3\cdot 10^{29}$ overall. – Alexey Burdin Dec 15 '15 at 4:28
• @AlexeyBurdin Well, maybe not that brute-force! I meant brute-force as in not a clever solution, but something like backtracking. – qwr Dec 15 '15 at 4:34

• Yep, much easier. Here's a proof that one can't fit $4$: i.imgur.com/UWbNqeb.png . There are 7 painted cells and every possible $9\times 9$ square covers at least $2$ of them. How can I get to OP from there? – Alexey Burdin Dec 15 '15 at 3:30