3✕n chessboard with holes - maximum number of knights not attacking each other
Use dynamic programming to calculate the maximum number of non-attacking knights on the left $3\times m$ part of your board with holes, given the placement of knights in the last two columns of this part of the board.