Maximal number of unmarked cells with at least 3 marked neighboring cells in the n X n kings' graph

Time complexity: \(O(m 2^{3n})\)
There is a solution in \(O(nm 2^{2n+3})\) The resulting sequences for \(N\times N\) grids and \(N\times(N+1)\) grids can be found at ??? and ???