I’m wondering if the solution isn’t vaguely related to dynamic programming. IE, you can’t brute force the whole board, but you can easily brute force a small sh

I’m wondering if the solution isn’t vaguely related to dynamic programming. IE, you can’t brute force the whole board, but you can easily brute force a small shape into a set of possible moves to fill it. You could then roll up these smaller shape move sequences into larger move sequences to optimize filling larger blocks. With simple counting of vertical / horizontal moves required, you can easily fill the entire board with 1x1 filled squares. At that point you just need to optimize for filling squares while leaving the largest possible area open (to reduc me the new square counter) as well as optimize the order of which squares zero and clear first.